BSTで操作を実行するC++プログラム

二分探索木は、すべてのノードが次のプロパティを持つソートされた二分木です-

• ノードの右側のサブツリーには、その親ノードのキーよりも大きいキーがあります。

• ノードの左側のサブツリーには、親ノードのキーよりも小さいキーがあります。

• すべての重要な値は異なります。

• 各ノードに3つ以上の子を含めることはできません。

クラスの説明：

Begin
   class BST to declare following functions:
      search() = To search an item in BST.
      initialize temp = root;
      while(temp != NULL)
         Increase depth
         if(temp→info == data)
         print data and depth
         else if(temp→info > data)
            temp = temp→l;
         else
            temp = temp→r;
         insert() = To insert items in the tree:
            if tree is empty insert data as root.
            if tree is not empty
            if data < root
            Insert data as left child.
         else
            Insert data as right child.
   del() = To delete an item from tree.
      casea() = Called from del() if l = r = null.
      caseb() = Called from del() if l != null, r = null.
      caseb() = Called from del() if l = null, r != null.
      casec() = Called from del() if l != null, r != null.
   inorder() to traverse the node as inorder as:
      left – root – right.
   preorder() to traverse the node as preorder as:
      root – Left – right.
   postorder() to traverse the node as preorder as:
      left – right – root
End

サンプルコード

# include <iostream>
# include <cstdlib>
using namespace std;
struct nod//node declaration
{
   int info;
   struct nod *l;
   struct nod *r;
}*r;
class BST
{
   public://functions declaration
   void search(nod *, int);
   void find(int, nod **, nod **);
   void insert(nod *, nod *);
   void del(int);
   void casea(nod *,nod *);
   void caseb(nod *,nod *);
   void casec(nod *,nod *);
   void preorder(nod *);
   void inorder(nod *);
   void postorder(nod *);
   void show(nod *, int);
   BST()
   {
      r = NULL;
   }
};
void BST::find(int i, nod **par, nod **loc)//find the position of the item
{
   nod *ptr, *ptrsave;
   if (r == NULL)
   {
      *loc = NULL;
      *par = NULL;
      return;
   }
   if (i == r→info)
   {
      *loc = r;
      *par = NULL;
      return;
   }
   if (i < r→info)
   ptr = r→l;
   else
   ptr = r→r;
   ptrsave = r;
   while (ptr != NULL)
   {
      if (i == ptr→info)
      {
         *loc = ptr;
         *par = ptrsave;
         return;
      }
      ptrsave = ptr;
      if (i < ptr→info)
      ptr = ptr→l;
      else
      ptr = ptr→r;
   }
   *loc = NULL;
   *par = ptrsave;
}
void BST::search(nod *root, int data) //searching
{
   int depth = 0;
   nod *temp = new nod;
   temp = root;
   while(temp != NULL)
   {
      depth++;
      if(temp→info == data)
      {
         cout<<"\nData found at depth: "<<depth<<endl;
         return;
      }
      else if(temp→info > data)
      temp = temp→l;
      else
      temp = temp→r;
   }
   cout<<"\n Data not found"<<endl;
   return;
}
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::del(int i)
{
   nod *par, *loc;
   if (r == NULL)
   {
      cout<<"Tree empty"<<endl;
      return;
   }
   find(i, &par, &loc);
   if (loc == NULL)
   {
      cout<<"Item not present in tree"<<endl;
      return;
   }
   if (loc→l == NULL && loc→r == NULL)
   {
      casea(par, loc);
      cout<<"item deleted"<<endl;
   }
   if (loc→l!= NULL && loc→r == NULL)
   {
      caseb(par, loc);
      cout<<"item deleted"<<endl;
   }
   if (loc→l== NULL && loc→r != NULL)
   {
      caseb(par, loc);
      cout<<"item deleted"<<endl;
   }
   if (loc→l != NULL && loc→r != NULL)
   {
      casec(par, loc);
      cout<<"item deleted"<<endl;
   }
   free(loc);
}
void BST::casea(nod *par, nod *loc )
{
   if (par == NULL)
{
   r= NULL;
}
else
{
   if (loc == par→l)
   par→l = NULL;
   else
   par→r = NULL;
   }
}
void BST::caseb(nod *par, nod *loc)
{
   nod *child;
   if (loc→l!= NULL)
      child = loc→l;
   else
      child = loc→r;
   if (par == NULL)
   {
      r = child;
   }
   else
   {
      if (loc == par→l)
         par→l = child;
      else
         par→r = child;
   }
}
void BST::casec(nod *par, nod *loc)
{
   nod *ptr, *ptrsave, *suc, *parsuc;
   ptrsave = loc;
   ptr = loc→r;
   while (ptr→l!= NULL)
   {
      ptrsave = ptr;
      ptr = ptr→l;
   }
   suc = ptr;
   parsuc = ptrsave;
   if (suc→l == NULL && suc→r == NULL)
      casea(parsuc, suc);
   else
      caseb(parsuc, suc);
   if (par == NULL)
   {
      r = suc;
   }
   else
   {
      if (loc == par→l)
         par→l = suc;
      else
         par→r= suc;
   }
   suc→l = loc→l;
   suc→r= loc→r;
}
void BST::preorder(nod *ptr)
{
   if (r == NULL)
   {
      cout<<"Tree is empty"<<endl;
      return;
   }
   if (ptr != NULL)
   {
      cout<<ptr→info<<" ";
      preorder(ptr→l);
      preorder(ptr→r);
   }
}
void BST::inorder(nod *ptr)//inorder traversal
{
   if (r == NULL)
   {
      cout<<"Tree is empty"<<endl;
      return;
   }
   if (ptr != NULL)
   {
      inorder(ptr→l);
      cout<<ptr→info<<" ";
      inorder(ptr→r);
   }
}
void BST::postorder(nod *ptr)//postorder traversal
{
   if (r == NULL)
   {
      cout<<"Tree is empty"<<endl;
      return;
   }
   if (ptr != NULL)
   {
      postorder(ptr→l);
      postorder(ptr→r);
      cout<<ptr→info<<" ";
   }
}
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,item;
   BST bst;
   nod *t;
   while (1)
   {
      cout<<"1.Insert Element "<<endl;
      cout<<"2.Delete Element "<<endl;
      cout<<"3.Search Element"<<endl;
      cout<<"4.Inorder Traversal"<<endl;
      cout<<"5.Preorder Traversal"<<endl;
      cout<<"6.Postorder Traversal"<<endl;
      cout<<"7.Display the tree"<<endl;
      cout<<"8.Quit"<<endl;
      cout<<"Enter your choice : ";
      cin>>c;
      switch(c)
      {
         case 1:
            t = new nod;
            cout<<"Enter the number to be inserted : ";
            cin>>t→info;
            bst.insert(r, t);
            break;
         case 2:
            if (r == NULL)
            {
               cout<<"Tree is empty, nothing to delete"<<endl;
               continue;
            }
            cout<<"Enter the number to be deleted : ";
            cin>>n;
            bst.del(n);
            break;
         case 3:
            cout<<"Search:"<<endl;
            cin>>item;
            bst.search(r,item);
            break;
         case 4:
            cout<<"Inorder Traversal of BST:"<<endl;
            bst.inorder(r);
            cout<<endl;
            break;
         case 5:
            cout<<"Preorder Traversal of BST:"<<endl;
            bst.preorder(r);
            cout<<endl;
            break;
         case 6:
            cout<<"Postorder Traversal of BST:"<<endl;
            bst.postorder(r);
            cout<<endl;
            break;
         case 7:
            cout<<"Display BST:"<<endl;
            bst.show(r,1);
            cout<<endl;
            break;
         case 8:
            exit(1);
         default:
            cout<<"Wrong choice"<<endl;
      }
   }
}

出力

1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 1
Enter the number to be inserted : 6
Root Node is Added
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 1
Enter the number to be inserted : 7
Node Added To Right
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 1
Enter the number to be inserted : 5
Node Added To Left
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 1
Enter the number to be inserted : 4
Node Added To Left
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 3
Search:
7
Data found at depth: 2
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 3
Search:
1
Data not found
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 4
Inorder Traversal of BST:
4 5 6 7
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 5
Preorder Traversal of BST:
6 5 4 7
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 6
Postorder Traversal of BST:
4 5 7 6
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 7
Display BST:
7
Root→: 6
5
4
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 2
Enter the number to be deleted : 1
Item not present in tree
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 5
Preorder Traversal of BST:
6 5 4 7
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 2
Enter the number to be deleted : 5
item deleted
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 7
Display BST:
7
Root→: 6
4
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 8