此版本是在数据结构（6）的基础上改造的。实现了构建平衡二叉树功能。
//BinTree.h #ifndef BINTREE_H_ #define BINTREE_H_ #define ElemType int typedef struct _PNode { ElemType data; _PNode *left; _PNode *right; int height; }PNode; class BinTree { private: PNode *root; public: BinTree(); ~BinTree(); PNode* GetRoot(); //获得根节点 void SetRoot(PNode *p) { root = p; } //设置根节点 PNode* Find(ElemType x , PNode *p); //查找元素x所在位置 PNode* FindMin(PNode *p); //查找二叉搜索树的最小值 PNode* FindMax(PNode *p); //查找二叉搜索树的最大值 PNode* Insert(ElemType x, PNode *p); //构建二叉搜索树，所插入的元素按二叉搜索树排列 PNode* Delete(ElemType x, PNode *p); //删除二叉搜索树的元素 //遍历二叉树 void PreOrder(PNode *p); //先序遍历 void CenOrder(PNode *p); //中序遍历 void Trave(PNode *p); //层次遍历 int GetHeight(PNode *p); PNode* AVL_Insertion(ElemType x, PNode *p); PNode* SingleLeftRotation(PNode *p); //左单旋 PNode* DoubleLeftRightRotation(PNode *p); //左右双旋 PNode* SingleRightRotation(PNode *p); //右单旋 PNode* DoubleRightLeftRotation(PNode *p); //右左双旋 int Max(int a, int b); //求最大值 }; #endif ///////////////////////////////////////////////////////////////////// //BinTree.cpp #include "BinTree.h" #include <iostream> #include <queue> BinTree::BinTree() { root = NULL; } BinTree::~BinTree(){} PNode* BinTree::GetRoot() { return root; } PNode* BinTree::Find(ElemType x, PNode *p) { /* //尾递归实现 if (p == NULL) return NULL; if (x > p->data) return Find(x, p->right); else if (x < p->data) return Find(x, p->left); else return p;*/ while (p != NULL) { if (x > p->data) p = p->right; else if (x < p->data) p = p->left; else return p; } return NULL; } PNode* BinTree::FindMin(PNode *p) { //递归查找 if (p == NULL) return NULL; else if (p->left == NULL) return p; else return FindMin(p->left); } PNode* BinTree::FindMax(PNode *p) { if (p != NULL) while (p->right != NULL) p = p->right; return p; } //遍历二叉树 void BinTree::PreOrder(PNode *p) { if (p == NULL) return; std::cout << p->data << " "; PreOrder(p->left); PreOrder(p->right); } void BinTree::CenOrder(PNode *p) { if (p == NULL) return; CenOrder(p->left); std::cout << p->data << " "; CenOrder(p->right); } PNode* BinTree::Insert(ElemType x, PNode *p) { if (p == NULL) { p = new PNode(); p->data = x; p->left = p->right = NULL; } else { if (x < p->data) p->left = Insert(x, p->left); else if (x > p->data) p->right = Insert(x, p->right); } return p; } PNode* BinTree::Delete(ElemType x, PNode *p) { PNode *tmp; if (p == NULL) std::cout << "要删除的元素未找到" << std::endl; else if (x < p->data) //查找要删除的节点 p->left = Delete(x, p->left); else if (x > p->data) p->right = Delete(x, p->right); else { //删除的元素左右节点都在,删除右子树的最小节点 if (p->left != NULL && p->right != NULL) { tmp = FindMin(p->right); //查找右子树的最小节点 p->data = tmp->data; //将右字数的最小值与当前节点的值互换 p->right = Delete(p->data, p->right); //删除右字数最小节点 } else {//删除的元素只有左节点，或只有右节点，或是叶子节点 tmp = p; if (p->left == NULL) //只有右节点，直接用右节点替换要删除节点 p = p->right; else if(p->right == NULL) //只有左节点，直接用左节点替换要删除节点 p = p->left; delete tmp; //如果删除节点是叶子节点，直接删除当前节点 } } return p; } void BinTree::Trave(PNode *p) //层次遍历 { std::queue<PNode*> q; q.push(p); while (!q.empty()) { PNode *s = q.front(); std::cout << s->data << " "; if (s->left != NULL) q.push(s->left); if (s->right != NULL) q.push(s->right); q.pop(); } } int BinTree::GetHeight(PNode *p) { int hl; int hr; int maxh; if (p) { hl = GetHeight(p->left); hr = GetHeight(p->right); maxh = (hl > hr) ? hl : hr; return (maxh + 1); } else return -1; } PNode* BinTree::AVL_Insertion(ElemType x, PNode *p) { //将x插入AVL树T中，并且返回调整后的AVL树 if (p == NULL) //如果插入空树，则新建包含一个节点的树 { p = new PNode(); p->data = x; p->height = 0; p->left = p->right = NULL; } else if (x < p->data) //插入T的左子树 { p->left = AVL_Insertion(x, p->left); if (GetHeight(p->left) - GetHeight(p->right) == 2) if (x < p->left->data) //需要左旋 p = SingleLeftRotation(p); //左单旋 else p = DoubleLeftRightRotation(p); //左右双旋 } //插入左子树结束 else if (x > p->data) { p->right = AVL_Insertion(x, p->right); if (GetHeight(p->right) - GetHeight(p->left) == 2) if (x > p->right->data) //需要又旋 p = SingleRightRotation(p); //右单旋 else p = DoubleRightLeftRotation(p); //右左双旋 } //x == p->data无需插入 p->height = Max(GetHeight(p->left), GetHeight(p->right)) + 1; return p; } int BinTree::Max(int a, int b) { return (a > b ? a : b); } PNode* BinTree::SingleLeftRotation(PNode *A) //左单旋 { //注意，A必须有一个左子结点 PNode *B = A->left; A->left = B->right; B->right = A; A->height = Max(GetHeight(A->left), GetHeight(A->right)) + 1; B->height = Max(GetHeight(B->left), GetHeight(A->right)) + 1; return B; } PNode* BinTree::DoubleLeftRightRotation(PNode *A) //左右双旋 { A->left = SingleRightRotation(A->left); return SingleLeftRotation(A); } PNode* BinTree::SingleRightRotation(PNode *A) //右单旋 { PNode *B = A->right; A->right = B->left; B->left = A; A->height = Max(GetHeight(A->left), GetHeight(A->right)) + 1; B->height = Max(GetHeight(B->left), GetHeight(A->right)) + 1; return B; } PNode* BinTree::DoubleRightLeftRotation(PNode *A) //右左双旋 { A->right = SingleLeftRotation(A->right); return SingleRightRotation(A); } //////////////////////////////////////////////////////// //测试 #include <iostream> #include "BinTree.h" using namespace std; int main() { BinTree bt; //构造二分查找树 bt.SetRoot(bt.AVL_Insertion(2, bt.GetRoot())); //注意跟新根节点 bt.SetRoot(bt.AVL_Insertion(3, bt.GetRoot())); bt.SetRoot(bt.AVL_Insertion(4, bt.GetRoot())); bt.SetRoot(bt.AVL_Insertion(5, bt.GetRoot())); bt.SetRoot(bt.AVL_Insertion(6, bt.GetRoot())); bt.SetRoot(bt.AVL_Insertion(8, bt.GetRoot())); bt.SetRoot(bt.AVL_Insertion(2, bt.GetRoot())); bt.SetRoot(bt.AVL_Insertion(1, bt.GetRoot())); cout << bt.GetHeight(bt.GetRoot()) << endl; cout << "先序遍历: " << endl; bt.PreOrder(bt.GetRoot()); cout << endl; cout << "中序遍历: " << endl; bt.CenOrder(bt.GetRoot()); cout << endl; cout << "层次遍历：" << endl; bt.Trave(bt.GetRoot()); cout << endl; cout << "最小值:" << bt.FindMin(bt.GetRoot())->data << endl; cout << "最大值:" << bt.FindMax(bt.GetRoot())->data << endl; /////////////////////////////////////////////////////////////////// //cout << endl << "删除节点 5 " << endl; //bt.Delete(4, bt.GetRoot()); cout << "先序遍历: " << endl; bt.PreOrder(bt.GetRoot()); cout << endl; cout << "中序遍历: " << endl; bt.CenOrder(bt.GetRoot()); cout << endl; cout << "层次遍历：" << endl; bt.Trave(bt.GetRoot()); cout << endl; cout << "最小值:" << bt.FindMin(bt.GetRoot())->data << endl; cout << "最大值:" << bt.FindMax(bt.GetRoot())->data << endl; system("pause"); return 0; }