二叉树

二叉树是树的特殊一种,具有如下特点:

  1. 每个结点最多有两颗子树,结点的度最大为2
  2. 左子树和右子树是有顺序的,次序不能颠倒
  3. 即使某结点只有一个子树,也要区分左右子树

存储结构

1
2
3
4
5
class Node<E> {
E e;
Node<E> left; // 左孩子
Node<E> right; // 右孩子
}

二叉树

跟链表类似,链表用一个 next 连成一条 线性 ,而二叉树用 left And right 表示树结构的两个分支。

添加

添加操作很简单,依循 左比右小 原则,将 new 放到合适的位置即可。

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
/**
* 添加元素
* @param e
*/
public void add(E e) {
root = add(root, e);
}
private Node<E> add(Node<E> node, E e) {
if (node == null) {
length++;
return new Node<>(e, null, null);
}
/**
* 递归遍历到 null 再插入新节点
* 递归时会将已连接的节点重新连接一次
*/
if (e.compareTo(node.e) < 0) {
node.left = add(node.left, e);
} else if (e.compareTo(node.e) > 0) {
node.right = add(node.right, e);
}
/**
* 返回的还是 root 节点
*/
return node;
}

/**
* 添加元素(非递归)
* @param e
*/
public void add0(E e) {
Node<E> rootTemp = root;
if (rootTemp == null) {
root = new Node<>(e, null, null);
return;
}
while (true) {
/*
* 相等 什么都不做
* 大于 右边
* 小于 左边
*/
if (e.compareTo(rootTemp.e) == 0) {
return;
} else if (e.compareTo(rootTemp.e) < 0) {
if (rootTemp.left != null) {
rootTemp = rootTemp.left;
} else {
Node<E> newNode = new Node<>(e, null, null);
rootTemp.left = newNode;
break;
}
} else {
if (rootTemp.right != null) {
rootTemp = rootTemp.right;
} else {
Node<E> newNode = new Node<>(e, null, null);
rootTemp.right = newNode;
break;
}
}
}
length++;
}

遍历

前、中、后序属于 深度优先遍历(DFT),层序遍历属于 广度优先遍历(BFT)

前、中、后序遍历递归实现本身就是进栈出栈,而非递归实现需要利用辅助栈来实现遍历。

层序遍历属于 先来后到,需要利用队列来实现。

每个元素都有三次访问 :

  1. 访问左节点之前
  2. 访问左节点之后 And 访问右节点之前
  3. 访问右节点之后

index 是一个成员属性,用于遍历转换成 Array

前序遍历

root -> 左 -> 右

访问左节点之前操作(入栈之前操作)。

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
/**
* 前序遍历
* @return
*/
public E[] preOrder() {
if (root == null) {
return null;
}
E[] array = (E[]) new Comparable[length];
preOrder(root, array);
index = 0;
return array;
}
private void preOrder(Node<E> node, E[] array) {
if (node == null) {
return;
}
array[index++] = node.e;
preOrder(node.left, array);
preOrder(node.right, array);
}

/**
* 前序遍历(非递归)
* @return
*/
public E[] preOrder0() {
if (isEmpty()) {
return null;
}
E[] array = (E[]) new Comparable[length];
Stack<Node<E>> stack = new ArrayStack<>();
Node<E> current = root;
while (current != null || !stack.isEmpty()) {
if (current != null) {
array[index++] = current.e;
stack.push(current);
current = current.left;
} else {
Node<E> node = stack.pop();
current = node.right;
}
}
index = 0;
return array;
}

中序遍历

左 -> root -> 右

访问左节点之后操作(出栈后操作)。

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
/**
* 中序遍历
* @return
*/
public E[] inOrder() {
if (root == null) {
return null;
}
E[] array = (E[]) new Comparable[length];
inOrder(root, array);
index = 0;
return array;
}
private void inOrder(Node<E> node, E[] array) {
if (node == null) {
return;
}
inOrder(node.left, array);
array[index++] = node.e;
inOrder(node.right, array);
}

/**
* 中虚遍历(非递归)
* @return
*/
public E[] inOrder0() {
if (isEmpty()) {
return null;
}
E[] array = (E[]) new Comparable[length];
Stack<Node<E>> stack = new ArrayStack<>();
Node<E> current = root;
/**
* 未找到最左侧节点 or 栈不为空
*/
while (current != null || !stack.isEmpty()) {
/**
* 左侧有元素,一路压栈,直到找到最左侧节点
*/
if (current != null) {
stack.push(current);
current = current.left;
} else {
/**
* 得到最左侧节点,最小值
*/
Node<E> node = stack.pop();
array[index++] = node.e;
current = node.right;
}
}
index = 0;
return array;
}

后序遍历

访问右节点之后操作(两个栈都出栈后访问)。

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
/**
* 后序遍历
* @return
*/
public E[] postOrder() {
if (root == null) {
return null;
}
E[] array = (E[]) new Comparable[length];
postOrder(root, array);
index = 0;
return array;
}
private void postOrder(Node<E> node, E[] array) {
if (node == null) {
return;
}
postOrder(node.left, array);
postOrder(node.right, array);
array[index++] = node.e;
}

/**
* 后序遍历(非递归)
* @return
*/
public E[] postOrder0() {
if (isEmpty()) {
return null;
}
E[] array = (E[]) new Comparable[length];
Stack<Node<E>> nodeStack = new ArrayStack<>();
Stack<Integer> flagStack = new ArrayStack<>();
Node<E> current = root;
int flag = 1;
while (current != null || !nodeStack.isEmpty()) {
/**
* 左节点全部入栈,并记录入栈状态
*/
while (current != null) {
nodeStack.push(current);
flagStack.push(0);
current = current.left;
}
/**
* 节点栈不为空, 标记栈顶为出栈状态(没有右节点了) 消费标记
*/
while (!nodeStack.isEmpty() && flagStack.peek() == flag) {
flagStack.pop();
array[index++] = nodeStack.pop().e;
}
/**
* 节点栈不为空
* 标记栈替换成出栈状态
* 进入右节点
*/
if (!nodeStack.isEmpty()) {
flagStack.pop();
flagStack.push(1);
current = nodeStack.peek();
current = current.right;
}
}
index = 0;
return array;
}

层序遍历

利用队列实现一层层访问。

  1. root 出 -> left 入 -> right 入
  2. left 出 -> left.left 入 -> left.right 入
  3. right 出 -> right.left 入 -> right.right 入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 广度优先遍历 (BFT)
* @return
*/
public E[] levelOrder() {
if (root == null) {
return null;
}
E[] array = (E[]) new Comparable[length];
Queue<Node<E>> queue = new LinkedQueue<>();
queue.enqueue(root);
while (!queue.isEmpty()) {
Node<E> node = queue.dequeue();
array[index++] = node.e;
if (node.left != null) {
queue.enqueue(node.left);
}
if (node.right != null) {
queue.enqueue(node.right);
}
}
index = 0;
return array;
}

查询

查询最小值

最左侧节点即为最小值节点

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 最小值
* @return
*/
public E min() {
return min(root).e;
}
private Node<E> min(Node<E> node) {
if (node.left == null) {
return node;
}
return min(node.left);
}

查询最大值

最右侧节点即为最大值节点

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 最大值
* @return
*/
public E max() {
return max(root).e;
}
private Node<E> max(Node<E> node) {
if (node.right == null) {
return node;
}
return max(node.right);
}

删除

删除最小值

因为最小值的 left 节点肯定是 null 所以在删除时会出现两种情况。

  1. right 节点为空

right 为空时,让最小值的父节点取消引用 parent.left = null, 最小值节点自身取消对 的引用即可。

  1. right 节点不为空

若是不为空,将最小值节点替换为 right 节点即可。

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
/**
* 删除最小值
* @return
*/
public E removeMin() {
if (root == null) {
return null;
}
E min = min();
removeMin(root);
return min;
}
private Node<E> removeMin(Node<E> node) {
if (node.left == null) {
Node<E> right = node.right;
node.right = null;
length--;
return right;
}
node.left = removeMin(node.left);
return node;
}

/**
* 删除最小值
* @return
*/
public E removeMin0() {
if (root == null) {
return null;
}
if (size() == 1) {
return removeRoot();
}
Node<E> parent = root;
Node<E> current = root;
while (current.left != null) {
parent = current;
current = current.left;
}
E result = current.e;
if (current.right != null) {
current = current.right;
} else {
parent.left = null;
current.e = null;
}
length--;
return result;
}

删除最大值

同删除最小值,方向反转了。

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
/**
* 删除最大值
* @return
*/
public E removeMax() {
if (root == null) {
return null;
}
E max = max();
removeMax(root);
return max;
}
private Node<E> removeMax(Node<E> node) {
if (node.right == null) {
Node<E> left = node.left;
node.left = null;
length--;
return left;
}
node.right = removeMax(node.right);
return node;
}

/**
* 删除最大值
* @return
*/
public E removeMax0() {
if (root == null) {
return null;
}
if (size() == 1) {
return removeRoot();
}
Node<E> parent = root;
Node<E> current = root;
// 找到最大值
while (current.right != null) {
parent = current;
current = current.right;
}
E result = current.e;
if (current.left != null) {
current = current.left;
} else {
parent.right = null;
current.e = null;
}
length--;
return result;
}

删除指定元素

删除任意元素有点复杂,删除时会出去三种情况 :

前三种很好处理,直接删除 Or 删除节点替换为不为空的节点即可,不做赘述。

  1. left And right 都为空
  2. left 不为空
  3. right 不为空
  4. left And right 都不为空

都不为空时 :

挑选右侧最小节点

删除并替换

挑选出大于被删除节点的最小节点 (也就是被删除节点的右节点的最左侧节点),这个节点的值最接近被删除节点,将这个节点填充到被删除节点的位置,并从原来的位置删除即可。

被删除节点的左节点的最右侧节点貌似也可以,但是这样做范围会被拉近不够分散,影响性能,所以选大不选小。

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
/**
* 删除指定节点
* @param e
* @return
*/
public boolean remove(E e) {
return remove(root, e) != null;
}
private Node<E> remove(Node<E> node, E e) {
if (node == null) {
return null;
}
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else { // e == node.e
/**
* 左节点为空:用右节点顶替
* 右节点为空:用左节点顶替
*/
if (node.left == null) {
Node<E> right = node.right;
node.right = null;
length--;
return right;
}
if (node.right == null) {
Node<E> left = node.left;
node.left = null;
length--;
return left;
} else {
/**
* 得到被删除节点的右侧最小节点
* 删除被删除节点的右侧最小节点
*/
Node<E> min = min(node.right);
/**
* 接管被删除节点的引用
*/
min.right = removeMin(node.right);
min.left = node.left;
node.left = node.right = null;
return min;
}
}
}

BinaryTree.java