Project 4: Create a binary tree and make the preorder traversal. (?????????? 1:

Question

Project 4: Create a binary tree and make the preorder traversal. (?????????? 1: Introduction Problem description and (if any) e of the algorithms Description According to the preorder traversal, values. Use binary linked list structure to store the binary tree, and output each node's value and depth, according to the preorder traversal (?????????????????? ?????????????????,? ?????????????????? input the sequence of each node Input: Input several data sets. For each set of testing data, input each node's value according to preorder traversal, with # being the empty node (???????,???????? ??????????????????, # ??????) Output: The sequence of binary tree nodes values in preorder traversal, output the depth of tree immediately after each node (???????????,??????? ?????????) Sample Input ABD##E##C## Sample Output A(1)B(2)D3)E (3)C(2) 2: Algorithm Specification Description (pseudo-code preferred) of all the algorithms involved for solving the problem, including specifications of main data structures.

Explanation / Answer

#include<iostream>

using namespace std;

struct node
{
node *left;
node *right;
char data;
} ;
class BST
{
node *root;
public:
BST()
{
  root=NULL;
}
int isempty()
{
  return(root==NULL);
}
void insert(char item);
        int getLevel(int data);
        int getLevelNode(struct node *node,int data, int level);
void preordertrav();
void preorder(node *);
};
void BST::insert(char item)
{
node *p=new node;
node *parent;
p->data=item;
p->left=NULL;
p->right=NULL;
parent=NULL;
if(isempty())
  root=p;
else
{
  node *ptr;
  ptr=root;
  while(ptr!=NULL)
  {
   parent=ptr;
   if(item>ptr->data)  
    ptr=ptr->right;
   else
    ptr=ptr->left;
  }
  if(item<parent->data)
   parent->left=p;
  else
   parent->right=p;
}
}

void BST::preordertrav()
{
preorder(root);
}
void BST::preorder(node *ptr)
{
if(ptr!=NULL)
{
                int a = getLevel(ptr->data);
                if (ptr->data != '#'){
      cout<<" "<<ptr->data<<"(" << a << ")";
                }
  preorder(ptr->left);
  preorder(ptr->right);
}
}

int BST::getLevelNode(struct node *node,int data, int level)
{
    if (node == NULL)
        return 0;

    if (node->data == data)
        return level;

    int downlevel = getLevelNode(node->left, data, level+1);
    if (downlevel != 0)
        return downlevel;

    downlevel = getLevelNode(node->right, data, level+1);
    return downlevel;
}

int BST::getLevel(int data)
{
    return getLevelNode(root,data,1);
}

int main()
{
BST b;
b.insert('A');
b.insert('B');
b.insert('D');
b.insert('#');
b.insert('#');
b.insert('E');
b.insert('#');
b.insert('#');
b.insert('C');
b.insert('#');
b.insert('#');

b.preordertrav();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.