Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình C ++ để thực hiện các hoạt động trong một BST

Cây tìm kiếm nhị phân là một cây nhị phân được sắp xếp trong đó tất cả các nút sẽ có các thuộc tính sau đây−

  • Cây con bên phải của một nút có khóa lớn hơn khóa của nút cha của nó.

  • Cây con bên trái của một nút có khóa nhỏ hơn khóa của nút cha của nó.

  • Tất cả các giá trị chính đều khác biệt.

  • Mỗi nút không được có nhiều hơn hai nút con.

Mô tả lớp học:

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

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://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;
      }
   }
}

Đầu ra

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