实现伸展树的 C++ 程序

2023-06-20 10:39:13 73

这是一个实现SplayTree的C++程序。

班级说明：

Begin
   class SplayTree has the functions:
      Create a function Splay() to implement top-down splay tree.
      Herehead.rchpoints to the Left tree andhead.lchpoints to the right tree.
      Create a link to Right tree.
      Create a link to Left tree.
      Assemble left, middle and right tree.
   Create a function Insert() to insert nodes into the tree.
      If root->k >= all keys will be the root→lch
      Else if
      root->k <=all keys will be the root→rch
      Else
      Return root.
End

类描述和伪代码：

Begin
   Create a structure s to declare variable k and left child pointer lch and right child pointer rch.
   Create a class SplayTree :
      Create a function RR_Rotate to rotate to the right.
      Create a function LL_Rotate to rotate to the left.
      Create a function Splay to implement top-down splay tree.
      Herehead.rchpoints to the Left tree and head.lch
      points to the right tree.
      Create a link to Right tree.
      Create a link to Left tree.
      Assemble left, middle and right tree.
   Create a function New_Node() to create nodes in the tree.
   Create a function Insert() to insert nodes into the tree.
      If root→k >= all keys will be the root→lch
      Else if
      root->k >=all keys will be the root→rch
      Else
      Return root.
   Create a function Delete() to delete nodes from the tree.
   Create a function Search() to search the nodes in the tree.
   Create a function InOrder() for InOrder traversal of the tree.
   Create a function main(), and perform selective function calls as per choice.
End

示例代码

#include 
#include 
#include 
using namespace std;
struct s//节点声明
{
   int k;  
   s* lch;
   s* rch;
};
class SplayTree
{
   public:
   s* RR_Rotate(s* k2)
   {
      s* k1 = k2->lch;
      k2->lch = k1->rch;
      k1->rch = k2;
      return k1;
   }
   s* LL_Rotate(s* k2)
   {
      s* k1 = k2->rch;
      k2->rch = k1->lch;
      k1->lch = k2;
      return k1;
   }
   s* Splay(int key, s* root)
   {
      if (!root)
      return NULL;
      s header;
      header.lch=header.rch= NULL;
      s* LeftTreeMax = &header;
      s* RightTreeMin = &header;
      while (1)
      {
         if (key < root->k)
         {
            if (!root->lch)
            break;
            if (key< root->lch->k)
            {
               root = RR_Rotate(root);
               if (!root->lch)
               break;
            }
            RightTreeMin->lch= root;
            RightTreeMin = RightTreeMin->lch;
            root = root->lch;
            RightTreeMin->lch = NULL;
         }
         else if (key> root->k)
         {
            if (!root->rch)
            break;
            if (key > root->rch->k)
            {
               root = LL_Rotate(root);
               if (!root->rch)
               break;
            }
            LeftTreeMax->rch= root;
            LeftTreeMax = LeftTreeMax->rch;
            root = root->rch;
            LeftTreeMax->rch = NULL;
         }
         else
         break;
      }
      LeftTreeMax→rch = root->lch;
      RightTreeMin→lch = root->rch;
      root->lch = header.rch;
      root->rch = header.lch;
      return root;
   }
   s* New_Node(int key)
   {
      s* p_node = new s;
      if (!p_node)
      {
         fprintf(stderr, "Out of memory!\n");
         exit(1);
      }
      p_node->k = key;
      p_node->lch = p_node->rch = NULL;
      return p_node;
   }
   s* Insert(int key, s* root)
   {
      static s* p_node = NULL;
      if (!p_node)
      p_node = New_Node(key);
      else
      p_node->k = key;
      if (!root)
      {
         root = p_node;
         p_node = NULL;
         return root;
      }
      root = Splay(key, root);
      if (key < root->k)
      {
         p_node->lch= root->lch;
         p_node->rch = root;
         root->lch = NULL;
         root = p_node;
      }
      else if (key > root->k)
      {
         p_node->rch = root->rch;
         p_node->lch = root;
         root->rch = NULL;
         root = p_node;
      }
      else
      return root;
      p_node = NULL;
      return root;
   }
   s* Delete(int key, s* root)//删除节点
   {
      s* temp;
      if (!root)//如果树是空的
      return NULL;
      root = Splay(key, root);
      if (key != root->k)//如果树有一项
      return root;
      else
      {
         if (!root->lch)
         {
            temp = root;
            root = root->rch;
         }
         else
         {
            temp = root;
            root = Splay(key, root->lch);
            root->rch = temp->rch;
         }
         free(temp);
         return root;
      }
   }
   s* Search(int key, s* root)//seraching
   {
      return Splay(key, root);
   }
   void InOrder(s* root)//中序遍历
   {
      if (root)
      {
         InOrder(root->lch);
         cout<< "key: " <k;
         if(root->lch)
         cout<< " | left child: "<< root->lch->k;
         if(root->rch)
         cout << " | right child: " << root->rch->k;
         cout<< "\n";
         InOrder(root->rch);
      }
   }
};
int main()
{
   SplayTree st;
   s *root;
   root = NULL;
   st.InOrder(root);
   int i, c;
   while(1)
   {
      cout<<"1. Insert "<>c;
      switch©//执行开关操作
      {
         case 1:
            cout<<"输入要插入的值： ";
            cin>>i;
            root = st.Insert(i, root);
            cout<<"\nAfter Insert: "<>i;
            root = st.Delete(i, root);
            cout<<"\nAfter Delete: "<>i;
            root = st.Search(i, root);
            cout<<"\nAfter Search "<输出结果1. Insert
2. Delete
3. Search
4. Exit
输入您的选择： 1
输入要插入的值： 7
After Insert: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
输入您的选择： 1
输入要插入的值： 6
After Insert: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
输入您的选择： 1
输入要插入的值： 4
After Insert: 4
key: 4 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
输入您的选择： 1
输入要插入的值： 5
After Insert: 5
key: 4
key: 5 | left child: 4 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
输入您的选择： 1
输入要插入的值： 3
After Insert: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
输入您的选择： 1
输入要插入的值： 2
After Insert: 2
key: 2 | right child: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
输入您的选择： 3
输入要搜索的值： 2
After Search 2
key: 2 | right child: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
输入您的选择： 2
输入要删除的值： 3
After Delete: 3
key: 2 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
输入您的选择： 4

实现伸展树的 C++ 程序

班级说明：

类描述和伪代码：

示例代码

热门推荐

随机推荐