C ++程序在BST中执行操作

2024-04-23 11:11:08 20

二进制搜索树是排序的二进制树，其中所有节点将具有以下属性-

节点的右子树的键大于其父节点的键。

节点的左子树的键小于其父节点的键。

所有键值都是不同的。

每个节点不能有两个以上的子节点。

类说明：

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<<"BST的有序遍历："<<endl;
            bst.inorder(r);
            cout<<endl;
            break;
         case 5:
            cout<<"BST的预遍历："<<endl;
            bst.preorder(r);
            cout<<endl;
            break;
         case 6:
            cout<<"BST的事后遍历："<<endl;
            bst.postorder(r);
            cout<<endl;
            break;
         case 7:
            cout<<"显示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
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
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
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
显示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
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
显示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

C ++程序在BST中执行操作

类说明：

范例程式码

热门推荐

随机推荐