二分木の2次走査を実装するC++プログラム

これは、バイナリツリーの2次走査を実装するためのC++プログラムです。

Double Order Traversalでは、サブツリーのルートが2回トラバースされます。

アルゴリズム

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

サンプルコード

# 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;
      }
   }
}

出力

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