文章目录
  1. 1. 树是什么鬼
  2. 2. 都有什么树
  3. 3. 和树相关的操作

树,尤其是二叉搜索树(Binary Search Tree => BST)是算法、数据结构领域重要的数据结构之一。
那么既然BST这么重要,想要了解BST需要了解哪些方面呢?

树是什么鬼

树(tree)是一种由节点(nodes)和无环向量(edges without having any cycle)构成的数据结构(通常是非线性的)。
一棵没有节点的树我们称为空树(Empty tree)
更多树的细节(如:叶子、度、树高等概念的定义)请参考这里)

都有什么树

总的来说我们按照有序和无序的维度将树分为无序树和有序树。

  • 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树
  • 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树。
    • 二叉树 :每个节点最多含有两个子树的树称为二叉树
      • 完全二叉树
      • 满二叉树
      • 平衡二叉树
        • 红黑树
      • 二叉搜索树
    • B树 :概括来说是一个一般化的n叉搜索树,可以拥有多于2个子节点
      • B+树
    • 霍夫曼树

和树相关的操作

由于二叉搜索树有着广泛的应用,所以这部分以二叉搜索树为例表述。
既然是二叉搜索树那么以下三个操作是基本操作:

  • 遍历(Travels)

    • 中序(inorder)遍历
    • 先序(preorder)遍历
    • 后序(postorder)遍历
  • 添加节点(Add node)

  • 查找节点(Search node)
  • 删除节点(Delete node)

上面说得都是些比较抽象的内容,相信你一定已经按耐不住想撸一遍代码了。好!给你机会。
从最简单的开始, 用你最熟悉的语言定义一个树结构:
考虑到Java的广泛使用程度,下面的代码都以Java编写。

1
2
3
4
5
6
7
8
public class TreeNode {
// left child node
TreeNode leftChild;

// left rightChild
TreeNode rightChild;
int data;
}

在进行遍历之前还有一个关键的步骤没有做,那就是构造树。
如果你也这样想,好吧,再想想是不是错过了些什么?
对,其实构建树只是添加树的一个复合操作。废话少说上码来战。

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
public class BinarySearchTree {
// root node
TreeNode root;

// Do nothing
public BinarySearchTree(){
}


//
// Insert the node to the BST
//
// put the value item into the BST
public TreeNode put(int value){
//
return put(this.root, value);
}

/**
*
* 添加节点
*
* @param root
* @param value
* @return
*/
private TreeNode put(TreeNode root, int value){
if (root == null){
this.root = new TreeNode();
this.root.data = value;
return this.root;
}

int valueOfrootElement = root.data;
if (value < valueOfrootElement){
root.leftChild = put(root.leftChild, value);
}else if (value > valueOfrootElement){
root.rightChild = put(root.rightChild, value);
}else {
root.data = value;
}

return root;
}
}

是不是感觉上面的代码有些不舒服,对的,有代码强迫症的你肯定已经毛爪挠心了,不废话,消灭所有不合理的因素。这次从方法命名开始。
(敲黑板,认真脸)

方法名中若不是简单的getter/setter 操作应当避免使用get/set作为方法名,以免引起不必要的误解。

改正后的版本

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
public class BinarySearchTree {
// root node
TreeNode root;

// Do nothing
public BinarySearchTree(){
}

/**
* 添加节点
*
* @param value
* @return
*/
public TreeNode addTreeNode(int value) {
//
if (this.root == null) {
this.root = new TreeNode(value);
}

return addTreeNode(this.root, value);
}

private TreeNode addTreeNode(TreeNode root, int value) {
if (root == null){
return new TreeNode(value);
}

int valueOfrootElement = root.data;
if (value < valueOfrootElement){
root.leftChild = addTreeNode(root.leftChild, value);
}else if (value > valueOfrootElement){
root.rightChild = addTreeNode(root.rightChild, value);
}else {
root.data = value;
}

return 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
public TreeNode searchNode(int value){
return searchNode(this.root, value);
}

/**
*
* 查找节点
*
* @param root
* @param value
* @return
*/
private TreeNode searchNode(TreeNode root, int value){
// empty tree
if (root == null){
return null;
}

// in order travels
int rootValue = this.root.data;
if (rootValue == value){
return root;
} else if (value < rootValue) {
return searchNode(root.leftChild, value);
} else {
return searchNode(root.rightChild, value);
}
}

上面的代码用到了inorder travels标准写法,递归(Reccurrence)调用查找方法。

我们实现了添加查找节点的方法,下一步就是实现删除节点。

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
public TreeNode deleteNode(int value){
return deleteNode(this.root, value);
}

private TreeNode deleteNode(TreeNode root, int value) {
if (root == null) {
return null;
}

int rootValue = root.data;
if (value < rootValue) {
root.leftChild = deleteNode(root.leftChild, value);
} else if (value > rootValue) {
root.rightChild = deleteNode(root.rightChild, value);
} else {
if (root.leftChild == null) {
return root.rightChild;
}

if (root.rightChild == null) {
return root.leftChild;
}

// search for the min node in right child subtree,
// and then replace the current node.
//
TreeNode newRootNode = findMin(root.rightChild);
// replace the current node.
root.data = newRootNode.data;
// remove from the previous right subtree
root.rightChild = deleteNode(root.rightChild, newRootNode.data);
}

return root;
}

算法的细节就不解释了,稍微麻烦点的地方都有注释。

到了这里是不是觉得就可以打完收工了? No,No,No……
没有测试的代码是不可以发布的,只有写过单元测试代码,并且GreenBar通过后才可以。
具体怎么添加单元测试工程的过程这里就不再啰嗦了,不同语言下都有比较成熟的单元测试框架, 例如java下的就是junit。下附图为测试工程GreenBar通过:
GreenBarPass

下附工程代码:gitHub

文章目录
  1. 1. 树是什么鬼
  2. 2. 都有什么树
  3. 3. 和树相关的操作