本文共 4294 字，大约阅读时间需要 14 分钟。
最近面试被问到平衡二叉树的性质及手撕构建平衡二叉树。当时无从下手，翻看牛客网面经，发现是一个常考点。虽然代码量相对较多，但确实是必须要掌握的知识。记录如下：
性质：
1、平衡二叉树其左右子树都为平衡二叉树，且树的深度的绝对值不会超过1； 2、将平衡因子（BF）定义为，其左子树的深度减去右子树的深度，则只会有-1,0,1三种情况； 3、平衡二叉树属于二叉搜索树（BST），也满足二叉搜索树的一些性质：左子树和右子树都是二叉搜索树。左子树所有节点值都小于等于其根节点值，右子树所有节点的值都大于等于其根节点的值；引出平衡二叉树的原因是想让树的深度尽可能的小，并将查询时间复杂度稳定控制在logn，避免因节点全在树的一边，导致树的深度为n，从而导致的查询时间复杂度为n；
代码实现：
#include#include using namespace std;constexpr auto RH = 1;constexpr auto EH = 0;constexpr auto LH = -1;struct tree { int val; int bf; tree* left; tree* right; tree(int n) { val = n; bf = 0; left = nullptr; right = nullptr; }};typedef tree* TreeNode;void R_Roate(TreeNode& P) { TreeNode L = P->left; P->left = L->right; L->right = P; P = L;}void L_Roate(TreeNode& P) { TreeNode R = P->right; P->right = R->left; R->left = P; P = R;}void LeftBalance(TreeNode& T) { TreeNode L = T->left; switch(L->bf) { case LH: T->bf = L->bf = EH; R_Roate(T); break; case RH: TreeNode Lr = L->right; switch (Lr->bf) { case LH: T->bf = RH; Lr->bf = EH; break; case EH: T->bf = Lr->bf = EH; break; case RH: T->bf = EH; Lr->bf = LH; break; } Lr->bf = EH; L_Roate(T->left); R_Roate(T); break; }}void RightBalance(TreeNode& T) { TreeNode R = T->right; switch (R->bf) { case RH: T->bf = R->bf = EH; L_Roate(T); break; case LH: TreeNode Rl = R->left; switch (Rl->bf) { case LH: T->bf = EH; Rl->bf = RH; break; case EH: T->bf = Rl->bf = EH; break; case RH: T->bf = LH; Rl->bf = EH; break; } Rl->bf = EH; R_Roate(T->right); L_Roate(T); break; }}bool InsertAVL(TreeNode& T, int e, bool& taller) { if (T == nullptr) { T = new tree(e); taller = true; } else { if (e == T->val) { taller = false; return false; } if (e < T->val) { if (!InsertAVL(T->left, e, taller)) return false; if (taller) { switch (T->bf) { case LH: LeftBalance(T); taller = false; break; case EH: T->bf = LH; taller = true; break; case RH: T->bf = EH; taller = false; break; } } } else { if (!InsertAVL(T->right, e, taller)) return false; if (taller) { switch (T->bf) { case RH: RightBalance(T); taller = false; break; case EH: T->bf = RH; taller = true; break; case LH: T->bf = EH; taller = false; break; } } } } return true;}void preTraver(TreeNode& root) { if (root == nullptr) return; cout << root->val << " "; preTraver(root->left); preTraver(root->right); return;}void preTraverCru(TreeNode& root) { stack data; data.push(root); while (!data.empty()) { TreeNode temp = data.top(); data.pop(); cout << temp->val << " "; if (temp->right) data.push(temp->right); if (temp->left) data.push(temp->left); } cout << endl; return;}void midTraver(TreeNode& root) { if (root == nullptr) return; midTraver(root->left); cout << root->val << " "; midTraver(root->right); return;}void midTraverCru(TreeNode& root) { TreeNode cur = root; stack data; while (!data.empty() || cur != nullptr) { while (cur!=nullptr) { data.push(cur); cur = cur->left; } cur = data.top(); data.pop(); cout << cur->val << " "; cur = cur->right; } cout << endl; return;}void posTraver(TreeNode& root) { if (root == nullptr) return; posTraver(root->left); posTraver(root->right); cout << root->val << " "; return;}void posTraverCru(TreeNode& root) { stack data1; stack data2; data1.push(root); while (!data1.empty()) { TreeNode temp = data1.top(); data1.pop(); data2.push(temp); if(temp->left)data1.push(temp->left); if(temp->right)data1.push(temp->right); } while (!data2.empty()) { TreeNode temp = data2.top(); data2.pop(); cout << temp->val << " "; } cout << endl; return;}int main() { int data[] = { 3,2,1,4,5,6,7,10,9,8 }; TreeNode root = nullptr; bool taller; for (int i = 0; i < 10; i++) InsertAVL(root, data[i], taller); cout << "Preorder traversal:" << endl; preTraver(root); cout << endl; preTraverCru(root); cout << "Inorder traversal:" << endl; midTraver(root); cout << endl; midTraverCru(root); cout << "Postorder traversal:" << endl; posTraver(root); cout << endl; posTraverCru(root); return 0;}
转载地址：http://dtyci.baihongyu.com/