实现伸展树的 C++ 程序
这是一个实现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