Chương trình C ++ để thực hiện truyền qua thứ tự kép của cây nhị phân

Đây là một chương trình C ++ để thực hiện truyền qua thứ tự kép của cây nhị phân.

Trong Double Order Traversal, gốc của cây con là sẽ được duyệt hai lần.

Thuật toán

Begin
   class BST has following functions:
      insert() = to insert items in the tree:
         Enter the root.
         Enter the value of the node, if it is greater than root then entered as right otherwise left.
         doubleOrder() = To perform inorder:
      If root = null
         Print tree is empty
         Otherwise perform:
         Visit root of (sub)tree.
         Visit left sub-tree.
         Revisit root of (sub)tree.
         Visit right sub-tree.
End

Mã mẫu

# include <iostream>
# include <cstdlib>
using namespace std;

struct nod//node declaration {
   int info;
   struct nod *l;
   struct nod *r;
}*r;

class BST {
   public://declaration of functions
   void insert(nod *, nod *);
   void doubleOrder(nod *);
   void show(nod *, int);
   BST() {
      r = NULL;
   }
};

void BST::insert(nod *tree, nod *newnode) {
   if (r == NULL) {
      r = new nod;
      r->info = newnode->info;
      r->l = NULL;
      r->r = NULL;
      cout<<"Root Node is Added"<<endl;
      return;
   }
   if (tree->info == newnode->info) {
      cout<<"Element already in the tree"<<endl;
      return;
   }
   if (tree->info >newnode->info) {
      if (tree->l != NULL) {
         insert(tree->l, newnode);
      } else {
         tree->l= newnode;
         (tree->l)->l = NULL;
         (tree->l)->r= NULL;
         cout<<"Node Added To Left"<<endl;
         return;
      }
   } else {
      if (tree->r != NULL) {
         insert(tree->r, newnode);
      } else {
         tree->r = newnode;
         (tree->r)->l= NULL;
         (tree->r)->r = NULL;
         cout<<"Node Added To Right"<<endl;
         return;
      }
   }
}

void BST::doubleOrder(nod *ptr) {
   if (r == NULL) {
      cout << "Tree is empty" << endl;
      return;
   }
   if (ptr != NULL) {
      cout << ptr->info << " ";
      doubleOrder(ptr->l);
      cout << ptr->info << " ";
      doubleOrder(ptr->r);
   }
}

void BST::show(nod *ptr, int level)// print the tree {
   int i;
   if (ptr != NULL) {
      show(ptr->r, level + 1);
      cout << endl;
      if (ptr == r)
         cout << "Root->: ";
      else {
         for (i = 0; i < level; i++)
            cout << " ";
      }
      cout << ptr->info;
      show(ptr->l, level + 1);
   }
}

int main() {
   int c, n;
   BST bst;
   nod *t;
   while (1)//perform switch operation {
      cout << "1.Insert Element " << endl;
      cout << "2.Double-Order Traversal" << endl;
      cout << "3.Show" << endl;
      cout << "4.Quit" << endl;
      cout << "Enter your choice : ";
      cin >>c;
      switch (c)//perform switch operation {
         case 1:
            t = new nod;
            cout << "Enter the number to be inserted : ";
            cin >>t->info;
            bst.insert(r, t);
         break;
         case 2:
            cout << "Double-Order Traversal of BST:" << endl;
            bst.doubleOrder(r);
            cout << endl;
         break;
         case 3:
            cout << "Print BST:" << endl;
            bst.show(r, 1);
            cout << endl;
         break;
         case 4:
            exit(1);
         default:
            cout << "Wrong choice" << endl;
      }
   }
}

Đầu ra

1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted :
7
Root Node is Added
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 6
Node Added To Left
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 4
Node Added To Left
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 2
Node Added To Left
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 10
Node Added To Right
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 3
Print BST:
10
Root->: 7
6
4
2
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 2
Double-Order Traversal of BST:
7 6 4 2 2 4 6 7 10 10
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 4