[标程]: 二叉搜索树和平衡二叉搜索树

水深无声 2022-07-13 12:44 191阅读 0赞

贴一个二叉搜索树(BST)和平衡二叉搜索树的标程(BBST).

\#include <iostream> \#include <algorithm> using namespace std; /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/ /\*二叉搜索树标程 \*/ /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/ struct BSTNode\{ int data; BSTNode\* left; BSTNode\* right; \}; typedef BSTNode\* BSTree; //p返回访问的最后一个节点 //father为传入的当前树的父节点 bool SearchBST(BSTree tree, int t, BSTree father, BSTree& p) \{ if(!tree) \{ p = father; return false; \} else if(t == tree->data) \{ p = tree; return true; \} else if(t < tree->data) return SearchBST(tree->left, t, tree, p); else return SearchBST(tree->right, t, tree, p); \} bool InsertBST(BSTree& tree, int t) \{ BSTree p, new\_node; if(!SearchBST(tree, t, NULL, p)) //当树中没有此节点时,插入 \{ new\_node = new BSTNode; new\_node->data = t; new\_node->left = new\_node->right = NULL; if(!p) //空树 tree = new\_node; else if(t < p->data) p->left = new\_node; else p->right = new\_node; return true; \} return false; \} bool Delete(BSTree& p) \{ BSTree tmp; if(!p->right) \{ tmp = p; p = p->left; delete tmp; \} else if(!p->left) \{ tmp = p; p = p->right; delete tmp; \} else \{ tmp = p->left; BSTree father = p; while (tmp->right) \{ father = tmp; tmp = tmp->right; \} p->data = tmp->data; if(p != father) father->right = tmp->left; else p->left = tmp->left; delete tmp; \} return true; \} bool DeleteBST(BSTree& tree, int t, BSTree father) \{ if(!tree) return false; else if(t < tree->data) return DeleteBST(tree->left, t, tree); else if(t > tree->data) return DeleteBST(tree->right, t, tree); else return Delete(tree); \} void Travel(BSTree tree) \{ if(tree) \{ Travel(tree->left); cout << tree->data << ' '; Travel(tree->right); \} \} /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/ /\*二叉平衡搜索树标程 \*/ /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/ typedef struct BBSTNode\{ int data; int bf; BBSTNode\* lchild, \*rchild; \}\*BBSTree; void RightRotate(BBSTree& p) //右旋 \{ BBSTree tmp = p->lchild; p->lchild = tmp->rchild; tmp->rchild = p; p = tmp; \} void LeftRotate(BBSTree& p) //左旋 \{ BBSTree tmp = p->rchild; p->rchild = tmp->lchild; tmp->lchild = p; p = tmp; \} \#define LH 1 \#define EH 0 \#define RH -1 void LeftBalance(BBSTree& p) //平衡左树 \{ BBSTree tmp = p->lchild; switch(tmp->bf) \{ case LH: p->bf = tmp->bf = EH; RightRotate(p); break; case RH: BBSTree tmp2 = tmp->rchild; switch(tmp2->bf) \{ case LH: tmp->bf = EH; p->bf = RH; break; case EH: p->bf = tmp->bf = EH; break; case RH: tmp->bf = LH; p->bf = EH; break; \} tmp2->bf = EH; LeftRotate(tmp); RightRotate(p); break; \} \} void RightBalance(BBSTree& p) //平衡右树 \{ BBSTree tmp = p->rchild; switch(tmp->bf) \{ case RH: p->bf = tmp->bf = EH; LeftRotate(p); break; case LH: BBSTree tmp2 = tmp->lchild; switch(tmp2->bf) \{ case LH: p->bf = EH; tmp->bf = RH; break; case EH: p->bf = tmp->bf = EH; break; case RH: p->bf = LH; tmp->bf = EH; break; \} tmp2->bf = EH; RightRotate(tmp); LeftRotate(p); break; \} \} bool InsertAVL(BBSTree& p, int t, bool &taller) //将值插入AVL树 \{ if(!p) \{ p = new BBSTNode; p->data = t; p->lchild = p->rchild = NULL; p->bf = EH; taller = true; \} else \{ if(t == p->data) \{ taller = false; return false; \} else if(t < p->data) \{ if(!InsertAVL(p->lchild, t, taller)) return false; if(taller) \{ switch(p->bf) \{ case LH: LeftBalance(p); taller = false; break; case EH: p->bf = LH; taller = true; break; case RH: p->bf = EH; taller = false; break; \} \} \} else \{ if(!InsertAVL(p->rchild, t, taller)) return false; if(taller) \{ switch(p->bf) \{ case LH: p->bf = EH; taller = false; break; case EH: p->bf = RH; taller = true; break; case RH: RightBalance(p); taller = false; break; \} \} \} \} return true; \} int main() \{ //BSTree test \{ BSTree tree = NULL; int arr\[\] = \{0,1,2,3,4,5,6,7,8,9\}; random\_shuffle(arr, arr+10); for(int i = 0; i < 10; ++i) InsertBST(tree, arr\[i\]); Travel(tree);cout << endl; for (int i = 2; i < 7; ++i) DeleteBST(tree, arr\[i\], NULL); Travel(tree);cout << endl; \} \{ BSTree tree = NULL; int arr\[\] = \{45,12,53,3,37,100,24,61,90,78\}; for(int i = 0; i < 10; ++i) InsertBST(tree, arr\[i\]); Travel(tree);cout << endl; DeleteBST(tree, arr\[2\], NULL); Travel(tree);cout << endl; \} //AVL tree test //... return 0; \}