0%

数据结构与算法 树.md

一、预备知识

树叶: 没有儿子节点的叫做树叶(leaf)。
深度: 对任意节点n,n的深度(depth)为从根到n的唯一路径长。因此根的深度为0。
高度: 对任意节点n,n的高度是从n到一片树叶的最长路径的长。

二、树的实现

相比顺序结构如:链表、数组。树的结构使其每一个节点除了数据以外还需要有一些指针,使得该节点的每一个儿子都有一个指针指向它。
以二叉树为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class TreeNode {
public int value;
public TreeNode left;
public TreeNode right;
public int height;

public TreeNode(int value) {
this.value = value;
}

@Override
public String toString() {
return "TreeNode{" +
"value=" + value +
'}';
}
}

三、树的遍历及应用

树有很多应用。比如文件系统、省市区搜索框等。

3.1 先序遍历

对节点的处理在它的儿子之前叫做先序遍历。

1
2
3
4
5
6
7
8
9
10
/**
* 先序打印
* parent -> left -> right
*/
public static void printPreorder(TreeNode head) {
if (head == null) return;
System.out.print(head.value + ",");
printPreorder(head.left);
printPreorder(head.right);
}

3.2 中序遍历

1
2
3
4
5
6
7
8
9
10
/**
* 中序打印
* left -> parent -> right
*/
public static void printInorder(TreeNode head) {
if (head == null) return;
printInorder(head.left);
System.out.print(head.value + ",");
printInorder(head.right);
}

3.3 后序遍历

对节点的处理在它的儿子之后叫做后序遍历。

1
2
3
4
5
6
7
8
9
10
/**
* 后序打印
* left -> right -> parent
*/
public static void printPostorder(TreeNode head) {
if (head == null) return;
printPostorder(head.left);
printPostorder(head.right);
System.out.print(head.value + ",");
}

四、二叉树

定义:每一个节点最多拥有两个儿子。

4.1 二叉查找树

定义:对于任意一个节点X,它的左子树所有关键字都小于X的关键字,而它的右子树中所有的关键字都大于X的关键字

4.1.1 Find

查找非常的简单,相当于折半查找,只是用了递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static TreeNode find(TreeNode node, int val) {
if (node == null) {
return null;
}

if (val < node.value) {
return find(node.left, val);
} else if (val > node.value) {
return find(node.right, val);
} else {
return node;
}
}

4.1.2 Insert

Find差不多,只是Find是返回,Insert是创建。

1
2
3
4
5
6
7
8
9
10
11
12
public static TreeNode insert(TreeNode head, int k) {
if (head == null) {
head = new TreeNode(k);
}
if (k < head.value) {
head.left = insert(head.left, k);
} else if (k > head.value) {
head.right = insert(head.right, k);
}

return head;
}

4.1.3 FindMin

以二叉查找树的定义,根节点最左边的儿子就是最小值。

1
2
3
4
public static TreeNode findMin(TreeNode node) {
if (node.left == null) return node;
return findMin(node.left);
}

4.1.4 Delete

一般删除策略只是替换删除的节点。

  • 1.该节点为树叶节点
    树叶节点可以直接删除。
  • 2.该节点只有左/右儿子
    使用左/右儿子进行替换。
  • 3.该节点都存在左右儿子
    删除策略是用其右字树的最左的节点的数据代替删除的节点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public static TreeNode delete(TreeNode node, int k) {
    if (k < node.value) {
    node.left = delete(node.left, k);
    } else if (k > node.value) {
    node.right = delete(node.right, k);
    } else if (node.left != null && node.right != null) {
    // 一般删除策略是用其右字树的最小的数据代替删除的那个节点
    TreeNode minNode = findMin(node.right);
    node.value = minNode.value;
    node.right = delete(node.right, node.value);
    } else if (node.left == null) {
    node = node.right;
    } else {
    node = node.left;
    }
    return node;
    }

4.1.5 二叉树应用

如:4.99 * 1.06 + 5.99 + 6.99 * 1.06
现实中常用的表达式,称为中缀表达式。一般计算表达式使用中缀转后缀,有两种常用方法:

  1. 二叉树

以二叉树为例

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
93
/**
* @author JiHongYuan
* @date 2021/6/18 14:34
*/
public class ExpressTree {
public static void main(String[] args) {
String expression = "4.99 * 1.06 + 5.99 + 6.99 * 1.06";
List<String> stringList = SuffixCalc.infixTransformSuffix(expression);


Stack<Node<String>> stack = new Stack<>();
for (String str : stringList) {
if (SuffixCalc.SymbolEnum.getSymbolEnumByString(str) != SuffixCalc.SymbolEnum.NONE) {
Node<String> parent = new Node<>(str, stack.pop(), stack.pop());
stack.push(parent);
} else {
stack.push(new Node<>(str, null, null));
}
}

Node<String> root = stack.pop();
printInorder(root);
System.out.println();
System.out.println(calc(root).toString());
}

public static <E> void printInorder(Node<E> head) {
if (head == null) return;
System.out.print("( ");
printInorder(head.left);
System.out.print(head.item + " ");
printInorder(head.right);
System.out.print(" ) ");
}

public static <E> E calc(Node<E> node) {
if (node == null) return null;

SuffixCalc.SymbolEnum symbol = SuffixCalc.SymbolEnum.getSymbolEnumByString(node.item.toString());

if (symbol != SuffixCalc.SymbolEnum.NONE) {
BigDecimal n1 = new BigDecimal(calc(node.left).toString());
BigDecimal n2 = new BigDecimal(calc(node.right).toString());

BigDecimal result;
switch (symbol) {
case ADD:
result = n1.add(n2);
break;
case SUB:
result = n1.subtract(n2);
break;
case MUL:
result = n1.multiply(n2);
break;
case DIV:
result = n1.divide(n2);
break;
default:
result = BigDecimal.ZERO;
}
node.item = (E) result.toString();
}

return node.item;
}

private static class Node<E> {
E item;
Node<E> left;
Node<E> right;


public Node(E item, Node<E> left, Node<E> right) {
this.item = item;
this.left = left;
this.right = right;
}


@Override
public String toString() {
return "Node{" +
"item=" + item +
", left=" + left +
", right=" + right +
'}';
}

}

}

4.2 AVL树

定义:AVL树是带有平衡条件的二叉查找树,每个节点的左子树和右子树的高度最多差1。
我们把必须重新平衡的节点叫做a。由于任意节点最多有两个儿子,英雌高度不平衡是,a点的两个字数的高度差2。这种不平衡的可能出现下面四种:

  1. 对a的左儿子的左树进行一次插入。
  2. 对a的左儿子的右树进行一次插入。
  3. 对a的右儿子的左树进行一次插入。
  4. 对a的右儿子的右树进行一次插入。

情形1和4是关于a点的镜像对称,而2和3是关于a点的镜像对象。因此理论上只有两个情况。

第一种情况:插入在外侧(左左、右右)使用单旋转(single rotation)。
第二种情况:插入在内侧(左右、右左)使用双旋转(double rotation)。

4.2.1 单旋转

单旋转由于查找树的特性,非常易懂。

4.2.1.1 左旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
            5            
/ \
4 8
/
3
/
2

|
v

5
/ \
3 8
/ \
2 4
1
2
3
4
5
6
7
8
9
10
public static TreeNode singleRotateWithLeft(TreeNode k2) {
TreeNode k1;
k1 = k2.left;
k2.left = k1.right;
k1.right = k2;

k1.height = Math.max(TreeUtil.height(k1.left), TreeUtil.height(k1.right)) + 1;
k2.height = Math.max(TreeUtil.height(k2.left), TreeUtil.height(k2.right)) + 1;
return k1;
}

4.2.1.2 右旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
          5            
/ \
4 8
\
9
\
10

|
v

5
/ \
4 9
/ \
8 10
1
2
3
4
5
6
7
8
9
10
11
public static TreeNode singleRotateWithRight(TreeNode k2) {
TreeNode k1;

k1 = k2.right;
k2.right = k1.left;
k1.left = k2;

k1.height = Math.max(TreeUtil.height(k1.left), TreeUtil.height(k1.right)) + 1;
k2.height = Math.max(TreeUtil.height(k2.left), TreeUtil.height(k2.right)) + 1;
return k1;
}

4.2.2 双旋转

双旋转略微复杂一点,只需要将左右、右左类型转化为情况1(即左左、右右)。

4.2.2.1 左右

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
            8            
/ \
4 9
/ \
3 5
\
6

|
v

8
/ \
5 9
/ \
4 6
/
3
|
v

5
/ \
4 8
/ / \
3 6 9
1
2
3
4
public static TreeNode doubleRotateWithLeft(TreeNode k3) {
k3.left = singleRotateWithRight(k3.left);
return singleRotateWithLeft(k3);
}

4.2.2.2 右左

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
            5            
/ \
4 8
/ \
6 9
\
7

|
v

5
/ \
4 6
\
8
/ \
7 9

|
v
6
/ \
5 8
/ / \
4 7 9
1
2
3
4
public static TreeNode doubleRotateWithRight(TreeNode k3) {
k3.right = singleRotateWithLeft(k3.right);
return singleRotateWithRight(k3);
}

4.2.3 Insert

递归到插入的节点时,从下往下重新计算高度。
主要难点在这里,有点难理解。

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
public static TreeNode insert(TreeNode T, int val) {
if (T == null) {
T = new TreeNode(val);
} else if (val < T.value) {
// 插入在左边
T.left = insert(T.left, val);

// 找到破坏平衡的节点
if (height(T.left) - height(T.right) == 2) {
if (val < T.left.value) {
// 左左条件 单旋转
T = singleRotateWithLeft(T);
} else {
// 左右条件 双旋转
T = doubleRotateWithLeft(T);
}
}
} else if (val > T.value) {
T.right = insert(T.right, val);
if (height(T.right) - height(T.left) == 2) {
if (val > T.right.value) {
T = singleRotateWithRight(T);
} else {
T = doubleRotateWithRight(T);
}
}
}
// 重新计算节点高度
T.height = Math.max(height(T.left), height(T.right)) + 1;
return T;
}

4.2.4 样例

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
/**
* @author JiHongYuan
* @date 2021/6/17 17:51
*/
public class AvlTree<E extends Comparable<E>> {
Node<E> root;

private static class Node<E> {
E item;
int height;
Node<E> left;
Node<E> right;


public Node(E item, Node<E> left, Node<E> right) {
this.item = item;
this.left = left;
this.right = right;
}


@Override
public String toString() {
return "Node{" +
"item=" + item +
", height=" + height +
", left=" + left +
", right=" + right +
'}';
}
}

public int height(Node<E> node) {
if (node == null) {
return -1;
}
return node.height;
}

public boolean add(E e) {
root = insert(root, e);
return true;
}

public Node<E> get(E item) {
return node(root, item);
}

/**
* return specified element item.
*/
Node<E> node(Node<E> node, E item) {
if (item.compareTo(node.item) < 0) {
return node(node.left, item);
} else if (item.compareTo(node.item) > 0) {
return node(node.right, item);
} else {
return node;
}
}

private Node<E> singleRotateWithLeft(Node<E> k2) {
Node<E> k1;
k1 = k2.left;
k2.left = k1.right;
k1.right = k2;

k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
return k1;
}

private Node<E> singleRotateWithRight(Node<E> k2) {
Node<E> k1;

k1 = k2.right;
k2.right = k1.left;
k1.left = k2;

k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
return k1;
}

private Node<E> doubleRotateWithLeft(Node<E> k3) {
k3.left = singleRotateWithRight(k3.left);
return singleRotateWithLeft(k3);
}

private Node<E> doubleRotateWithRight(Node<E> k3) {
k3.right = singleRotateWithLeft(k3.right);
return singleRotateWithRight(k3);
}

private Node<E> insert(Node<E> node, E item) {
if (node == null) {
node = new Node<>(item, null, null);
} else if (item.compareTo(node.item) < 0) {
// 插入在左边
node.left = insert(node.left, item);

// 找到破坏平衡的节点
if (height(node.left) - height(node.right) == 2) {
if (item.compareTo(node.left.item) < 0) {
// 左左条件 单旋转
node = singleRotateWithLeft(node);
} else {
// 左右条件 双旋转
node = doubleRotateWithLeft(node);
}
}
} else if (item.compareTo(node.item) > 0) {
node.right = insert(node.right, item);
if (height(node.right) - height(node.left) == 2) {
if (item.compareTo(node.right.item) > 0) {
node = singleRotateWithRight(node);
} else {
node = doubleRotateWithRight(node);
}
}
}
// 重新计算节点高度
node.height = Math.max(height(node.left), height(node.right)) + 1;
return node;
}

private static void writeArray(Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) return;
// 先将当前节点保存到二维数组中
res[rowIndex][columnIndex] = String.valueOf(currNode.item);

// 计算当前位于树的第几层
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一层,则返回
if (currLevel == treeDepth) return;
// 计算当前行到下一行,每个元素之间的间隔(下一行的列索引与当前元素的列索引之间的间隔)
int gap = treeDepth - currLevel - 1;

// 对左儿子进行判断,若有左儿子,则记录相应的"/"与左儿子的值
if (currNode.left != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}

// 对右儿子进行判断,若有右儿子,则记录相应的"\"与右儿子的值
if (currNode.right != null) {
res[rowIndex + 1][columnIndex + gap] = "\\";
writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}

// 用于获得树的层数
private int getTreeDepth(Node<E> root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
}

public void show() {
// 得到树的深度
int treeDepth = getTreeDepth(root);

// 最后一行的宽度为2的(n - 1)次方乘3,再加1
// 作为整个二维数组的宽度
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// 用一个字符串数组来存储每个位置应显示的元素
String[][] res = new String[arrayHeight][arrayWidth];
// 对数组进行初始化,默认为一个空格
for (int i = 0; i < arrayHeight; i++) {
for (int j = 0; j < arrayWidth; j++) {
res[i][j] = " ";
}
}

// 从根节点开始,递归处理整个树
// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
writeArray(root, 0, arrayWidth / 2, res, treeDepth);

// 此时,已经将所有需要显示的元素储存到了二维数组中,将其拼接并打印即可
for (String[] line : res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2 : line[i].length() - 1;
}
}
System.out.println(sb.toString());

}
}
}


/**
* @author JiHongYuan
* @date 2021/6/17 18:24
*/
public class AvlTreeTest {
public static void main(String[] args) {
AvlTree<Integer> avlTree = new AvlTree<>();

Integer[] integers = {5, 4, 6, 7, 8, 11};
for (Integer integer : integers) {
avlTree.add(integer);
}
avlTree.show();

System.out.println(avlTree.get(5));
avlTree.show();

}
}