C++ 實作 AVL 樹：輸入整數動態建立平衡二叉樹

AVL 樹是自平衡二叉搜尋樹，插入節點後透過旋轉維持高度平衡。本文提供完整的 C++ 實作，支援讀取 1-3 位整數並動態輸出樹狀結構。

核心功能

• 節點定義：包含鍵值、高度、左右子節點指標。
• 右旋、左旋、左右旋、右左旋四種旋轉操作。
• 插入函式：遞歸插入並更新高度、檢查平衡因子、執行對應旋轉。
• 中序列印：驗證樹的有序性；層序列印：視覺化樹的結構。

程式碼架構

struct Node { int key, height; Node *left, *right; };
Node* rightRotate(Node* y);
Node* leftRotate(Node* x);
int getBalance(Node* n);
Node* insert(Node* node, int key);
void printInOrder(Node* root);
void printLevelOrder(Node* root);

主程式迴圈讀取整數，呼叫 insert 後列印樹狀圖，直到輸入非數字結束。完整可編譯代碼請參考原文連結的部落格文章。