BTNode root = NULL;    root = insert(root, 21);    root = insert(root, 4);    root = insert(root, 9);    root = insert(root, 13);    root = insert(root, 31);    root = insert(root, 25);    root = insert(root, 23);    root = insert(root, 22);    root = insert(root, 33);

構造平衡二叉樹

情形一較為簡單，對應程式碼為註釋中情形一的地方。

BTNode deleteNode(BTNode root, int key){     if (root == NULL)        return root;     if (key < root->_data)        root->_left = deleteNode(root->_left, key);     else if (key > root->_data)        root->_right = deleteNode(root->_right, key);     else    {        if ((root->_left == NULL) || (root->_right == NULL))        {            BTNode temp = root->_left ? root->_left : root->_right;             if (temp == NULL) //情形一，刪除葉子節點            {                temp = root;                root = NULL;            }            else                *root = *temp;//情形二、情形三            free(temp);        }        else//情形四        {            BTNode temp = minValueNode(root->_right);             root->_data = temp->_data;             root->_right = deleteNode(root->_right, temp->_data);        }    }      if (root == NULL)        return root;  //重新計算高度    root->_nodeHeight = 1 + max(getHeight(root->_left), getHeight(root->_right));  //重新計算平衡度    int balance = getBalance(root);   //如不平衡則旋轉    if (balance > 1 && getBalance(root->_left) >= 0) //LL型        return ll_rotate(root);      if (balance > 1 && getBalance(root->_left) < 0) //LR型    {        root->_left = rr_rotate(root->_left);        return ll_rotate(root);    }     if (balance < -1 && getBalance(root->_right) <= 0) //RR型        return rr_rotate(root);     if (balance < -1 && getBalance(root->_right) > 0)  //RL型    {        root->_right = ll_rotate(root->_right);        return rr_rotate(root);    }     return root;}

刪除結點31，符合情形二，刪除左子樹為空，右子樹不為空的節點：

按照三步曲：

找到節點31；

然後判斷節點33、25、21是否平衡，如不平衡則旋轉。

對應程式碼為註釋中情形二、三的地方

按照三步曲：

找到節點23；

然後判斷節點22、25、21是否平衡，如不平衡則旋轉。

對應程式碼為註釋中情形二、三的地方

按照三步曲：

找到節點25；

然後判斷節點31、21是否平衡，如不平衡則旋轉。

對應程式碼為註釋中情形四的地方。