Tree

Tree


2018-12-19

树是什么

举个现实生活中的例子,公司的组织架构如下:

1
2
3
4
5
#        |ceo|
# / \
# |cto| |cfo|
# / \ / \
# |se| |se| |sm| |sm|

通过上图可以得到一个直观的感受,就是明显的层级关系。从顶端的 CEO ,到雇佣各种职能人员组成公司,就像一棵 “树” (颠倒的),从根部开始生长,到开枝散叶。在开发中多少都接触过树的概念 ,作为一种数据结构被广泛得应用在各种计算机语言中,了解它的设计思想对日后的开发是非常有帮助的。以上图公司的组织架构来了解下常用的术语,都比较基础:

  • 节点:从 ceo 到研发,都是一个个节点 ;
  • 边:两个节点间的联系,如 cto 与研发 ;
  • 根节点:架构最上层的节点 ,对应 ceo ;
  • 叶子节点:架构最下层的节点,如研发,没有子节点 ;
  • 高度:相对叶子节点而言,如 ceo 的高度 -> 研发;+1;
  • 深度:相对根节点而言,如 cto 的深度 -> ceo ; +1;

二叉树是什么

二叉树是一种特殊的树 ,每个节点最多只能有两个子节点(左子节点、右子节点):



从上图可以看出二叉树是一组节点的集合,每个节点有 3 个属性:

  • 当前节点保存的值
  • 左子节点
  • 右子节点

捋清楚这点关系后就可以动手敲代码了,从最简单的开始:

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

public BinaryTree(int value) {
this.value = value;
this.left = null;
this.right = null;
}

@Override
public String toString() {
return "value: " + value + " left: " + left + " right: " + right;
}
}

二叉树 – 插入

接下来尝试往二叉树中插入节点,分别定义插入左子节点和右子节点的方法。规则如下

  • 如果当前节点没有左/右子节点,则将创建新的节点作为当前节点的左/右子节点;
  • 如果当前节点存在左/右子节点,则用新创建的节点 “插入” 到当前节点的左/右子节点位置;

第一点比较好理解,第二点画个图:



也很好理解,思路有了,代码就比较好写了, BinaryTree 类中添加如下方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void insertLeft(int value) {
if (this.left == null) {
this.left = new BinaryTree(value);
} else {
BinaryTree newNode = new BinaryTree(value);
newNode.left = this.left;
this.left = newNode;
}
}

public void insertRight(int value) {
if (this.right == null) {
this.right = new BinaryTree(value);
} else {
BinaryTree newNode = new BinaryTree(value);
newNode.right = this.right;
this.right = newNode;
}
}

测试下上面写的代码,假设要生成的二叉树如下



测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
BinaryTree node11 = new BinaryTree(11);
node11.insertLeft(8);
node11.insertRight(16);

BinaryTree node8 = node11.left;
BinaryTree node16 = node11.right;

node8.insertLeft(5);
node8.insertRight(10);
node16.insertRight(18);

BinaryTree node5 = node8.left;
BinaryTree node10 = node8.right;
BinaryTree node18 = node16.right;

System.out.println(node11.value);//11
System.out.println(node8.value);//8
System.out.println(node16.value);//16
System.out.println(node5.value);//5
System.out.println(node10.value);//10
System.out.println(node18.value);//18

二叉树 – 遍历

二叉树的遍历分为深度优先遍历(Depth-First Search)和广度优先遍历 (Breadth-First Search)。



深度优先–先序

F-B-A-D-C-E-G-I-H

代码实现:

1
2
3
4
5
6
7
8
9
public static void preOrder(BinaryTree currentNode) {
System.out.println(currentNode.value);
if (currentNode.left != null) {
preOrder(currentNode.left);
}
if (currentNode.right != null) {
preOrder(currentNode.right);
}
}


深度优先–中序

A-B-C-D-E-F-G-H-I

代码实现:

1
2
3
4
5
6
7
8
9
public static void inOrder(BinaryTree currentNode) {
if (currentNode.left != null) {
inOrder(currentNode.left);
}
System.out.println(currentNode.value);
if (currentNode.right != null) {
inOrder(currentNode.right);
}
}


深度优先–后序

A-C-E-D-B-H-I-G-F

代码实现:

1
2
3
4
5
6
7
8
9
public static void postOrder(BinaryTree currentNode) {
if (currentNode.left != null) {
postOrder(currentNode.left);
}
if (currentNode.right != null) {
postOrder(currentNode.right);
}
System.out.println(currentNode.value);
}


广度优先–分层

F-B-G-A-D-I-C-E-H

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void bfs(BinaryTree currentNode) {
Queue<BinaryTree> queue = new LinkedList<>();
if (currentNode == null) {
return;
}
queue.clear();
queue.add(currentNode);
while (!queue.isEmpty()) {
BinaryTree node = queue.remove();
System.out.println(node.value);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}

这里借助队列来实现广度优先遍历,假如要遍历下面这棵二叉树:



整个流程如下:

二叉查找树

二叉查找树就是排序后的二叉树,通俗理解如下:

1
左子树上所有节点的值 < 根节点的值 < 右子树上所有节点的值



  • A:不满足条件,子树 7-5-8-6 与子树 2-1-3 顺序颠倒;
  • B:满足条件;
  • C:不满足条件,4 应该在 5 的左边;

二叉查找树 – 插入

假如要按照 50,76,21,4,32,100,64,52 顺序生成一颗树,流程如下

代码如下:

1
2
3
4
5
6
7
8
9
10
public static BinaryTree insert(BinaryTree currentNode, int value) {
if (currentNode == null) {
return new BinaryTree(value);
} else if (value < currentNode.value) {
currentNode.left = insert(currentNode.left, value);
} else if (value > currentNode.value) {
currentNode.right = insert(currentNode.right, value);
}
return currentNode;
}

二叉查找树 – 查找

在上面例子的基础上,假设要查找 52 这个值是否存在,流程如下:

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
public static boolean find(BinaryTree currentNode, int value) {
if (currentNode == null) {
return false;
}
if (value < currentNode.value) {
return find(currentNode.left, value);
}
if (value > currentNode.value) {
return find(currentNode.right, value);
}
return true;
}

二叉查找树 – 删除

删除操作相对繁琐,需要考虑几种情况:

  • 被删除的节点无子节点;
1
2
3
4
5
#        |50|                              |50|
# / \ / \
# |30| |70| (DELETE 20) ---> |30| |70|
# / \ \
# |20| |40| |40|

这种情况很简单,直接删除即可

  • 被删除的节点有一个子节点;
1
2
3
4
5
#        |50|                              |50|
# / \ / \
# |30| |70| (DELETE 30) ---> |20| |70|
# /
# |20|

这种情况也相对简单,作为 20 父节点的 30 被删除了,那么此时 20 就由 30 的父节点 50 来 “接管”。

  • 被删除的节点有两个子节点;
1
2
3
4
5
#        |50|                              |50|
# / \ / \
# |30| |70| (DELETE 30) ---> |40| |70|
# / \ /
# |20| |40| |20|

这种情况稍微麻烦一些,首先查找节点 30 的右子树中最小的值(40),并用它替换节点 30 的值,再将节点 40 删掉。不太好理解?下面会有更详细的分解介绍。

代码如下:

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
public static BinaryTree delete(BinaryTree currentNode, int value) {
if (currentNode == null) {
return null;
}
if (value < currentNode.value) {
currentNode.left = delete(currentNode.left, value);
} else if (value > currentNode.value) {
currentNode.right = delete(currentNode.right, value);
} else {
if (currentNode.left == null && currentNode.right == null) {
System.out.println("deleting leaf node" + value);
return null;
} else if (currentNode.left == null) {
System.out.println("no left node; deleting " + value);
return currentNode.right;
} else if (currentNode.right == null) {
System.out.println("no right node; deleting " + value);
return currentNode.left;
} else {
currentNode.value = minimumValue(currentNode.right);
delete(currentNode.right, currentNode.value);
System.out.println("with two child node; deleting " + value);
}
}
return currentNode;
}

public static int minimumValue(BinaryTree root) {
if (root.left != null) {
return minimumValue(root.left);
}
return root.value;
}

做个测试,通过下面代码生成一棵二叉查找树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BinaryTree root = new BinaryTree(15);
insert(root, 10);
insert(root, 20);
insert(root, 8);
insert(root, 12);
insert(root, 17);
insert(root, 25);
insert(root, 19);
bfs(root);

# |15|
# / \
# |10| |20|
# / \ / \
# |8| |12| |17| |25|
# \
# |19|

删无子节点的节点 8 :

1
2
3
4
5
6
7
8
9
10
delete(root, 8);
bfs(root);

# |15|
# / \
# |10| |20|
# \ / \
# |12| |17| |25|
# \
# |19|

再删带一个子节点的节点 17:

1
2
3
4
5
6
7
8
delete(root, 17);
bfs(root);

# |15|
# / \
# |10| |20|
# \ / \
# |12| |19| |25|

再删带两个子节点的节点 15:

1
2
3
4
5
6
7
8
delete(root, 15);
bfs(root);

# |19|
# / \
# |10| |20|
# \ \
# |12| |25|

删带两个子节点的节点的过程用流程表示:

Enjoy –☺