AVL樹的介紹
AVL樹是高度平衡的而二叉樹。它的特點是：AVL樹中任何節點的兩個子樹的高度最大差别為1。
上面的兩張圖檔，左邊的是AVL樹，它的任何節點的兩個子樹的高度差别都<=1；而右邊的不是AVL樹，因為7的兩顆子樹的高度相差為2(以2為根節點的樹的高度是3，而以8為根節點的樹的高度是1)。
AVL樹的Java實作
1. 節點
1.1 節點定義
public class AVLTree<T extends Comparable<T>> {
private AVLTreeNode<T> mRoot; // 根結點
// AVL樹的節點(内部類)
class AVLTreeNode<T extends Comparable<T>> {
T key; // 關鍵字(鍵值)
int height; // 高度
AVLTreeNode<T> left; // 左孩子
AVLTreeNode<T> right; // 右孩子
public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
this.key = key;
this.left = left;
this.right = right;
this.height = 0;
}
}
......
}
AVLTree是AVL樹對應的類，而AVLTreeNode是AVL樹節點，它是AVLTree的内部類。AVLTree包含了AVL樹的根節點，AVL樹的基本操作也定義在AVL樹中。AVLTreeNode包括的幾個組成對象:
(01) key -- 是關鍵字，是用來對AVL樹的節點進行排序的。
(02) left -- 是左孩子。
(03) right -- 是右孩子。
(04) height -- 是高度。
1.2 樹的高度
/*
* 擷取樹的高度
*/
private int height(AVLTreeNode<T> tree) {
if (tree != null)
return tree.height;
return 0;
}
public int height() {
return height(mRoot);
}
關于高度，有的地方将"空二叉樹的高度是-1"，而本文采用維基百科上的定義：樹的高度為最大層次。即空的二叉樹的高度是0，非空樹的高度等于它的最大層次(根的層次為1，根的子節點為第2層，依次類推)。
1.3 比較大小
/*
* 比較兩個值的大小
*/
private int max(int a, int b) {
return a>b ? a : b;
}
2. 旋轉
如果在AVL樹中進行插入或删除節點後，可能導緻AVL樹失去平衡。這種失去平衡的可以概括為4種姿态：LL(左左)，LR(左右)，RR(右右)和RL(右左)。下面給出它們的示意圖：
上圖中的4棵樹都是"失去平衡的AVL樹"，從左往右的情況依次是：LL、LR、RL、RR。除了上面的情況之外，還有其它的失去平衡的AVL樹，如下圖：
上面的兩張圖都是為了便于了解，而列舉的關于"失去平衡的AVL樹"的例子。總的來說，AVL樹失去平衡時的情況一定是LL、LR、RL、RR這4種之一，它們都由各自的定義：
(1) LL：LeftLeft，也稱為"左左"。插入或删除一個節點後，根節點的左子樹的左子樹還有非空子節點，導緻"根的左子樹的高度"比"根的右子樹的高度"大2，導緻AVL樹失去了平衡。
例如，在上面LL情況中，由于"根節點(8)的左子樹(4)的左子樹(2)還有非空子節點"，而"根節點(8)的右子樹(12)沒有子節點"；導緻"根節點(8)的左子樹(4)高度"比"根節點(8)的右子樹(12)"高2。
(2) LR：LeftRight，也稱為"左右"。插入或删除一個節點後，根節點的左子樹的右子樹還有非空子節點，導緻"根的左子樹的高度"比"根的右子樹的高度"大2，導緻AVL樹失去了平衡。
例如，在上面LR情況中，由于"根節點(8)的左子樹(4)的左子樹(6)還有非空子節點"，而"根節點(8)的右子樹(12)沒有子節點"；導緻"根節點(8)的左子樹(4)高度"比"根節點(8)的右子樹(12)"高2。
(3) RL：RightLeft，稱為"右左"。插入或删除一個節點後，根節點的右子樹的左子樹還有非空子節點，導緻"根的右子樹的高度"比"根的左子樹的高度"大2，導緻AVL樹失去了平衡。
例如，在上面RL情況中，由于"根節點(8)的右子樹(12)的左子樹(10)還有非空子節點"，而"根節點(8)的左子樹(4)沒有子節點"；導緻"根節點(8)的右子樹(12)高度"比"根節點(8)的左子樹(4)"高2。
(4) RR：RightRight，稱為"右右"。插入或删除一個節點後，根節點的右子樹的右子樹還有非空子節點，導緻"根的右子樹的高度"比"根的左子樹的高度"大2，導緻AVL樹失去了平衡。
例如，在上面RR情況中，由于"根節點(8)的右子樹(12)的右子樹(14)還有非空子節點"，而"根節點(8)的左子樹(4)沒有子節點"；導緻"根節點(8)的右子樹(12)高度"比"根節點(8)的左子樹(4)"高2。
如果在AVL樹中進行插入或删除節點後，可能導緻AVL樹失去平衡。AVL失去平衡之後，可以通過旋轉使其恢複平衡，下面分别介紹"LL(左左)，LR(左右)，RR(右右)和RL(右左)"這4種情況對應的旋轉方法。
2.1 LL的旋轉
LL失去平衡的情況，可以通過一次旋轉讓AVL樹恢複平衡。如下圖：
圖中左邊是旋轉之前的樹，右邊是旋轉之後的樹。從中可以發現，旋轉之後的樹又變成了AVL樹，而且該旋轉隻需要一次即可完成。
對于LL旋轉，你可以這樣了解為：LL旋轉是圍繞"失去平衡的AVL根節點"進行的，也就是節點k2；而且由于是LL情況，即左左情況，就用手抓着"左孩子，即k1"使勁搖。将k1變成根節點，k2變成k1的右子樹，"k1的右子樹"變成"k2的左子樹"。
LL的旋轉代碼
/*
* LL：左左對應的情況(左單旋轉)。
*
* 傳回值：旋轉後的根節點
*/
private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {
AVLTreeNode<T> k1;
k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height(k2.left), height(k2.right)) + 1;
k1.height = max( height(k1.left), k2.height) + 1;
return k1;
}
2.2 RR的旋轉
了解了LL之後，RR就相當容易了解了。RR是與LL對稱的情況！RR恢複平衡的旋轉方法如下：
圖中左邊是旋轉之前的樹，右邊是旋轉之後的樹。RR旋轉也隻需要一次即可完成。
RR的旋轉代碼
/*
* RR：右右對應的情況(右單旋轉)。
*
* 傳回值：旋轉後的根節點
*/
private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {
AVLTreeNode<T> k2;
k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height(k1.left), height(k1.right)) + 1;
k2.height = max( height(k2.right), k1.height) + 1;
return k2;
}
2.3 LR的旋轉
LR失去平衡的情況，需要經過兩次旋轉才能讓AVL樹恢複平衡。如下圖：
第一次旋轉是圍繞"k1"進行的"RR旋轉"，第二次是圍繞"k3"進行的"LL旋轉"。
LR的旋轉代碼
/*
* LR：左右對應的情況(左雙旋轉)。
*
* 傳回值：旋轉後的根節點
*/
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {
k3.left = rightRightRotation(k3.left);
return leftLeftRotation(k3);
}
2.4 RL的旋轉
RL是與LR的對稱情況！RL恢複平衡的旋轉方法如下：
第一次旋轉是圍繞"k3"進行的"LL旋轉"，第二次是圍繞"k1"進行的"RR旋轉"。
RL的旋轉代碼
/*
* RL：右左對應的情況(右雙旋轉)。
*
* 傳回值：旋轉後的根節點
*/
private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {
k1.right = leftLeftRotation(k1.right);
return rightRightRotation(k1);
}
3. 插入
插入節點的代碼
/*
* 将結點插入到AVL樹中，并傳回根節點
*
* 參數說明：
* tree AVL樹的根結點
* key 插入的結點的鍵值
* 傳回值：
* 根節點
*/
private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
if (tree == null) {
// 建立節點
tree = new AVLTreeNode<T>(key, null, null);
if (tree==null) {
System.out.println("ERROR: create avltree node failed!");
return null;
}
} else {
int cmp = key.compareTo(tree.key);
if (cmp < 0) { // 應該将key插入到"tree的左子樹"的情況
tree.left = insert(tree.left, key);
// 插入節點後，若AVL樹失去平衡，則進行相應的調節。
if (height(tree.left) - height(tree.right) == 2) {
if (key.compareTo(tree.left.key) < 0)
tree = leftLeftRotation(tree);
else
tree = leftRightRotation(tree);
}
} else if (cmp > 0) { // 應該将key插入到"tree的右子樹"的情況
tree.right = insert(tree.right, key);
// 插入節點後，若AVL樹失去平衡，則進行相應的調節。
if (height(tree.right) - height(tree.left) == 2) {
if (key.compareTo(tree.right.key) > 0)
tree = rightRightRotation(tree);
else
tree = rightLeftRotation(tree);
}
} else { // cmp==0
System.out.println("添加失敗：不允許添加相同的節點！");
}
}
tree.height = max( height(tree.left), height(tree.right)) + 1;
return tree;
}
public void insert(T key) {
mRoot = insert(mRoot, key);
}
4. 删除
删除節點的代碼
/*
* 删除結點(z)，傳回根節點
*
* 參數說明：
* tree AVL樹的根結點
* z 待删除的結點
* 傳回值：
* 根節點
*/
private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {
// 根為空 或者 沒有要删除的節點，直接傳回null。
if (tree==null || z==null)
return null;
int cmp = z.key.compareTo(tree.key);
if (cmp < 0) { // 待删除的節點在"tree的左子樹"中
tree.left = remove(tree.left, z);
// 删除節點後，若AVL樹失去平衡，則進行相應的調節。
if (height(tree.right) - height(tree.left) == 2) {
AVLTreeNode<T> r = tree.right;
if (height(r.left) > height(r.right))
tree = rightLeftRotation(tree);
else
tree = rightRightRotation(tree);
}
} else if (cmp > 0) { // 待删除的節點在"tree的右子樹"中
tree.right = remove(tree.right, z);
// 删除節點後，若AVL樹失去平衡，則進行相應的調節。
if (height(tree.left) - height(tree.right) == 2) {
AVLTreeNode<T> l = tree.left;
if (height(l.right) > height(l.left))
tree = leftRightRotation(tree);
else
tree = leftLeftRotation(tree);
}
} else { // tree是對應要删除的節點。
// tree的左右孩子都非空
if ((tree.left!=null) && (tree.right!=null)) {
if (height(tree.left) > height(tree.right)) {
// 如果tree的左子樹比右子樹高；
// 則(01)找出tree的左子樹中的最大節點
// (02)将該最大節點的值指派給tree。
// (03)删除該最大節點。
// 這類似于用"tree的左子樹中最大節點"做"tree"的替身；
// 采用這種方式的好處是：删除"tree的左子樹中最大節點"之後，AVL樹仍然是平衡的。
AVLTreeNode<T> max = maximum(tree.left);
tree.key = max.key;
tree.left = remove(tree.left, max);
} else {
// 如果tree的左子樹不比右子樹高(即它們相等，或右子樹比左子樹高1)
// 則(01)找出tree的右子樹中的最小節點
// (02)将該最小節點的值指派給tree。
// (03)删除該最小節點。
// 這類似于用"tree的右子樹中最小節點"做"tree"的替身；
// 采用這種方式的好處是：删除"tree的右子樹中最小節點"之後，AVL樹仍然是平衡的。
AVLTreeNode<T> min = maximum(tree.right);
tree.key = min.key;
tree.right = remove(tree.right, min);
}
} else {
AVLTreeNode<T> tmp = tree;
tree = (tree.left!=null) ? tree.left : tree.right;
tmp = null;
}
}
return tree;
}
public void remove(T key) {
AVLTreeNode<T> z;
if ((z = search(mRoot, key)) != null)
mRoot = remove(mRoot, z);
}
完整的實作代碼AVL樹的實作檔案(AVRTree.java)
/**
* Java 語言: AVL樹
*
* @author skywang
* @date 2013/11/07
*/
public class AVLTree<T extends Comparable<T>> {
private AVLTreeNode<T> mRoot; // 根結點
// AVL樹的節點(内部類)
class AVLTreeNode<T extends Comparable<T>> {
T key; // 關鍵字(鍵值)
int height; // 高度
AVLTreeNode<T> left; // 左孩子
AVLTreeNode<T> right; // 右孩子
public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
this.key = key;
this.left = left;
this.right = right;
this.height = 0;
}
}
// 構造函數
public AVLTree() {
mRoot = null;
}
/*
* 擷取樹的高度
*/
private int height(AVLTreeNode<T> tree) {
if (tree != null)
return tree.height;
return 0;
}
public int height() {
return height(mRoot);
}
/*
* 比較兩個值的大小
*/
private int max(int a, int b) {
return a>b ? a : b;
}
/*
* 前序周遊"AVL樹"
*/
private void preOrder(AVLTreeNode<T> tree) {
if(tree != null) {
System.out.print(tree.key+" ");
preOrder(tree.left);
preOrder(tree.right);
}
}
public void preOrder() {
preOrder(mRoot);
}
/*
* 中序周遊"AVL樹"
*/
private void inOrder(AVLTreeNode<T> tree) {
if(tree != null)
{
inOrder(tree.left);
System.out.print(tree.key+" ");
inOrder(tree.right);
}
}
public void inOrder() {
inOrder(mRoot);
}
/*
* 後序周遊"AVL樹"
*/
private void postOrder(AVLTreeNode<T> tree) {
if(tree != null) {
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.key+" ");
}
}
public void postOrder() {
postOrder(mRoot);
}
/*
* (遞歸實作)查找"AVL樹x"中鍵值為key的節點
*/
private AVLTreeNode<T> search(AVLTreeNode<T> x, T key) {
if (x==null)
return x;
int cmp = key.compareTo(x.key);
if (cmp < 0)
return search(x.left, key);
else if (cmp > 0)
return search(x.right, key);
else
return x;
}
public AVLTreeNode<T> search(T key) {
return search(mRoot, key);
}
/*
* (非遞歸實作)查找"AVL樹x"中鍵值為key的節點
*/
private AVLTreeNode<T> iterativeSearch(AVLTreeNode<T> x, T key) {
while (x!=null) {
int cmp = key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else if (cmp > 0)
x = x.right;
else
return x;
}
return x;
}
public AVLTreeNode<T> iterativeSearch(T key) {
return iterativeSearch(mRoot, key);
}
/*
* 查找最小結點：傳回tree為根結點的AVL樹的最小結點。
*/
private AVLTreeNode<T> minimum(AVLTreeNode<T> tree) {
if (tree == null)
return null;
while(tree.left != null)
tree = tree.left;
return tree;
}
public T minimum() {
AVLTreeNode<T> p = minimum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
* 查找最大結點：傳回tree為根結點的AVL樹的最大結點。
*/
private AVLTreeNode<T> maximum(AVLTreeNode<T> tree) {
if (tree == null)
return null;
while(tree.right != null)
tree = tree.right;
return tree;
}
public T maximum() {
AVLTreeNode<T> p = maximum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
* LL：左左對應的情況(左單旋轉)。
*
* 傳回值：旋轉後的根節點
*/
private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {
AVLTreeNode<T> k1;
k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height(k2.left), height(k2.right)) + 1;
k1.height = max( height(k1.left), k2.height) + 1;
return k1;
}
/*
* RR：右右對應的情況(右單旋轉)。
*
* 傳回值：旋轉後的根節點
*/
private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {
AVLTreeNode<T> k2;
k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height(k1.left), height(k1.right)) + 1;
k2.height = max( height(k2.right), k1.height) + 1;
return k2;
}
/*
* LR：左右對應的情況(左雙旋轉)。
*
* 傳回值：旋轉後的根節點
*/
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {
k3.left = rightRightRotation(k3.left);
return leftLeftRotation(k3);
}
/*
* RL：右左對應的情況(右雙旋轉)。
*
* 傳回值：旋轉後的根節點
*/
private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {
k1.right = leftLeftRotation(k1.right);
return rightRightRotation(k1);
}
/*
* 将結點插入到AVL樹中，并傳回根節點
*
* 參數說明：
* tree AVL樹的根結點
* key 插入的結點的鍵值
* 傳回值：
* 根節點
*/
private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
if (tree == null) {
// 建立節點
tree = new AVLTreeNode<T>(key, null, null);
if (tree==null) {
System.out.println("ERROR: create avltree node failed!");
return null;
}
} else {
int cmp = key.compareTo(tree.key);
if (cmp < 0) { // 應該将key插入到"tree的左子樹"的情況
tree.left = insert(tree.left, key);
// 插入節點後，若AVL樹失去平衡，則進行相應的調節。
if (height(tree.left) - height(tree.right) == 2) {
if (key.compareTo(tree.left.key) < 0)
tree = leftLeftRotation(tree);
else
tree = leftRightRotation(tree);
}
} else if (cmp > 0) { // 應該将key插入到"tree的右子樹"的情況
tree.right = insert(tree.right, key);
// 插入節點後，若AVL樹失去平衡，則進行相應的調節。
if (height(tree.right) - height(tree.left) == 2) {
if (key.compareTo(tree.right.key) > 0)
tree = rightRightRotation(tree);
else
tree = rightLeftRotation(tree);
}
} else { // cmp==0
System.out.println("添加失敗：不允許添加相同的節點！");
}
}
tree.height = max( height(tree.left), height(tree.right)) + 1;
return tree;
}
public void insert(T key) {
mRoot = insert(mRoot, key);
}
/*
* 删除結點(z)，傳回根節點
*
* 參數說明：
* tree AVL樹的根結點
* z 待删除的結點
* 傳回值：
* 根節點
*/
private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {
// 根為空 或者 沒有要删除的節點，直接傳回null。
if (tree==null || z==null)
return null;
int cmp = z.key.compareTo(tree.key);
if (cmp < 0) { // 待删除的節點在"tree的左子樹"中
tree.left = remove(tree.left, z);
// 删除節點後，若AVL樹失去平衡，則進行相應的調節。
if (height(tree.right) - height(tree.left) == 2) {
AVLTreeNode<T> r = tree.right;
if (height(r.left) > height(r.right))
tree = rightLeftRotation(tree);
else
tree = rightRightRotation(tree);
}
} else if (cmp > 0) { // 待删除的節點在"tree的右子樹"中
tree.right = remove(tree.right, z);
// 删除節點後，若AVL樹失去平衡，則進行相應的調節。
if (height(tree.left) - height(tree.right) == 2) {
AVLTreeNode<T> l = tree.left;
if (height(l.right) > height(l.left))
tree = leftRightRotation(tree);
else
tree = leftLeftRotation(tree);
}
} else { // tree是對應要删除的節點。
// tree的左右孩子都非空
if ((tree.left!=null) && (tree.right!=null)) {
if (height(tree.left) > height(tree.right)) {
// 如果tree的左子樹比右子樹高；
// 則(01)找出tree的左子樹中的最大節點
// (02)将該最大節點的值指派給tree。
// (03)删除該最大節點。
// 這類似于用"tree的左子樹中最大節點"做"tree"的替身；
// 采用這種方式的好處是：删除"tree的左子樹中最大節點"之後，AVL樹仍然是平衡的。
AVLTreeNode<T> max = maximum(tree.left);
tree.key = max.key;
tree.left = remove(tree.left, max);
} else {
// 如果tree的左子樹不比右子樹高(即它們相等，或右子樹比左子樹高1)
// 則(01)找出tree的右子樹中的最小節點
// (02)将該最小節點的值指派給tree。
// (03)删除該最小節點。
// 這類似于用"tree的右子樹中最小節點"做"tree"的替身；
// 采用這種方式的好處是：删除"tree的右子樹中最小節點"之後，AVL樹仍然是平衡的。
AVLTreeNode<T> min = maximum(tree.right);
tree.key = min.key;
tree.right = remove(tree.right, min);
}
} else {
AVLTreeNode<T> tmp = tree;
tree = (tree.left!=null) ? tree.left : tree.right;
tmp = null;
}
}
return tree;
}
public void remove(T key) {
AVLTreeNode<T> z;
if ((z = search(mRoot, key)) != null)
mRoot = remove(mRoot, z);
}
/*
* 銷毀AVL樹
*/
private void destroy(AVLTreeNode<T> tree) {
if (tree==null)
return ;
if (tree.left != null)
destroy(tree.left);
if (tree.right != null)
destroy(tree.right);
tree = null;
}
public void destroy() {
destroy(mRoot);
}
/*
* 列印"二叉查找樹"
*
* key -- 節點的鍵值
* direction -- 0，表示該節點是根節點;
* -1，表示該節點是它的父結點的左孩子;
* 1，表示該節點是它的父結點的右孩子。
*/
private void print(AVLTreeNode<T> tree, T key, int direction) {
if(tree != null) {
if(direction==0) // tree是根節點
System.out.printf("%2d is root\n", tree.key, key);
else // tree是分支節點
System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");
print(tree.left, tree.key, -1);
print(tree.right,tree.key, 1);
}
}
public void print() {
if (mRoot != null)
print(mRoot, mRoot.key, 0);
}
}
/**
* Java 語言: AVL樹
*
* @author skywang
* @date 2013/11/07
*/
public class AVLTreeTest {
private static int arr[]= {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
public static void main(String[] args) {
int i;
AVLTree<Integer> tree = new AVLTree<Integer>();
System.out.printf("== 依次添加: ");
for(i=0; i<arr.length; i++) {
System.out.printf("%d ", arr[i]);
tree.insert(arr[i]);
}
System.out.printf("\n== 前序周遊: ");
tree.preOrder();
System.out.printf("\n== 中序周遊: ");
tree.inOrder();
System.out.printf("\n== 後序周遊: ");
tree.postOrder();
System.out.printf("\n");
System.out.printf("== 高度: %d\n", tree.height());
System.out.printf("== 最小值: %d\n", tree.minimum());
System.out.printf("== 最大值: %d\n", tree.maximum());
System.out.printf("== 樹的詳細資訊: \n");
tree.print();
i = 8;
System.out.printf("\n== 删除根節點: %d", i);
tree.remove(i);
System.out.printf("\n== 高度: %d", tree.height());
System.out.printf("\n== 中序周遊: ");
tree.inOrder();
System.out.printf("\n== 樹的詳細資訊: \n");
tree.print();
// 銷毀二叉樹
tree.destroy();
}
}
AVL樹的Java測試
AVL樹的測試程式運作結果如下：
== 依次添加: 3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9
== 前序周遊: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16
== 中序周遊: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
== 後序周遊: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7
== 高度: 5
== 最小值: 1
== 最大值: 16
== 樹的詳細資訊:
is root
is 7's left child
is 4's left child
is 2's left child
is 2's right child
is 4's right child
is 6's left child
is 7's right child
is 13's left child
is 11's left child
is 9's left child
is 9's right child
is 11's right child
is 13's right child
is 15's left child
is 15's right child
== 删除根節點: 8
== 高度: 5
== 中序周遊: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16
== 樹的詳細資訊:
is root
is 7's left child
is 4's left child
is 2's left child
is 2's right child
is 4's right child
is 6's left child
is 7's right child
is 13's left child
is 11's left child
is 9's right child
is 11's right child
is 13's right child
is 15's left child
is 15's right child