AVL高度
左右子樹的高度不能超過1
AVL樹左子樹與右子樹相減高度不能超過1，要小於等於1。
取得高度
左子樹為null，傳回0，否則傳回左子樹高度。
右子樹為null，傳回0，否則傳回右子樹高度。
+1，是加上根節點本身的高度。
1
2
3
4
public int height() {
return Math.max(left == null ? 0 : left.height(),
right == null ? 0 : right.height()) + 1;
}
左右子樹高度
此處沒加1，是不含根節點本身的高度，只有子樹的高度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int leftHeight() {
if (left == null) {
return 0;
} else {
return left.height();
}
}
public int rightHeight() {
if (right == null) {
return 0;
} else {
return right.height();
}
}
完整程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
public class avlTree {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
int[] arr = {10, 5, 11, 12, 13, 14};
for (int i = 0; i < arr.length; i++) {
bst.add(new Node(arr[i]));
}
int h = bst.root.height();
System.out.println(h);
int left_h = bst.root.leftHeight();
System.out.println(left_h);
int right_h = bst.root.rightHeight();
System.out.println(right_h);
}
}
class BinarySearchTree {
public Node root;
public void add(Node node) {
if (root == null) {
// 如果是空樹，就把root設為node
root = node;
} else {
// 如果不是空樹，就去找子樹，可新增的位罝
root.add(node);
}
}
public void inOrder() {
if (root != null) {
root.inOrder();
}
}
}
class Node {
Node left;
Node right;
int value;
public Node(int value) {
this.value = value;
}
public int height() {
return Math.max(left == null ? 0 : left.height(),
right == null ? 0 : right.height()) + 1;
}
public int leftHeight() {
if (left == null) {
return 0;
} else {
return left.height();
}
}
public int rightHeight() {
if (right == null) {
return 0;
} else {
return right.height();
}
}
public void inOrder() {
if (this.left != null) {
this.left.inOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.inOrder();
}
}
public void add(Node node) {
if (node == null) return;
// 小於目前節點，新增在左子樹
if (node.value < this.value) {
// 左子樹是葉子節點，才新增
if (this.left == null) {
this.left = node;
} else { // 不是葉子，就繼續往左子樹找
this.left.add(node);
}
} else {
// 大於、等於目前節點，新增在右子樹
// 右子樹是葉子節點，才新增
if (this.right == null) {
this.right = node;
} else { // 不是葉子，就繼續往右子樹找
this.right.add(node);
}
}
}
}