Fork me on GitHub

二叉树

algorithm/binary_tree/banner

嗯~中秋节前来一波关于二叉树的博文!二叉树是一种特殊的,它的子节点个数步超过两个。二叉树具有一些特殊的计算性质,使得在它们之上的一些操作异常高效。

当考虑某种特殊的二叉树,比如二叉查找树时,确定子节点就非常重要。二叉查找树是一种特殊的二叉树,相对较小的值保存在左节点,较大的值保存在右节点中。这一特性使得查找的效率很高,对于数值型和非数值型的数据,比如单词和字符串,都是如此。下面的截图就是一个二叉查找树(BST)

algorithm/binary_tree/bst_demo

实现二叉查找树

二叉查找树由节点组成,我们定义一个Node对象来存储。如下:

1
2
3
4
5
6
7
8
9
10
function Node(data , left , right) {
this.data = data;
this.left = left;
this.right = right;
this.show = show;
}

function show() { // 显示节点数据
return this.data;
}

接下来就是创建BST类,进入BST以后,下一步就是决定将节点放在那个地方了。步骤如下:

  1. 设根节点为当前节点
  2. 如果待插入节点保存的数据小于当前节点,则设新的单前节点为原节点的左节点;反之,执行第四步。如果单前的
  3. 如果当前节点的左节点为null,就将新的节点插入这个位置,退出循环;反之,继续执行下一次循环;
  4. 设新的当前节点为原节点的右节点。
  5. 如果当前节点的右节点为null,就将新的节点插入这个位置,退出循环;反之,继续执行下一个循环。

BST类创建和插入元素的代码如下:

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
function BST() {
this.root = null;
this.insert = insert;
this.inOrder = inOrder;
}

function insert(data) {
var n = new Node(data,null,null);
if(this.root == null) {
this.root = n;
}
else {
var current = this.root;
var parent;
while(true) {
parent = current;
if(data < current.data) {
current = current.left;
if(current == null) {
parent.left = n;
break;
}
}else {
current = current.right;
if(current.right == null) {
current.right = n;
break;
}
}
}
}
}

遍历二叉查找树

经过上面的编写,二叉查找树已经成型了,上面知识能够插入元素。下面我们来编写下如何遍历二叉查找树了。有三种遍历的方式:中序、先序和后序

中序

中序遍历按照节点上的键值,以升序访问BST上的所有节点。也就是下面的路径效果图:

algorithm/binary_tree/inorder_traversal

上图中序遍历的结果是:10,22,30,56,77,81,92,也就是数据的从小到大的排列啦。相关实现的代码如下:

1
2
3
4
5
6
7
functon inOrder(node) {
if(!(node == null)) { // 或者node != null
inOrder(node.left);
console.log(node.show() + " ");
inOrder(node.right);
}
}

先序

先序遍历先访问根节点,然后以同样方式访问左子树和右子树。相关的路径入如下:

algorithm/binary_tree/preorder_traversal

上图先序遍历的结果是:56,22,10,30,81,77,92。实现先序的代码如下:

1
2
3
4
5
6
7
function preOrder(node) {
if(!(node == null)) {
console.log(node.show() + " ");
preOrder(node.left);
preOrder(node.right);
}
}

后序

后序遍历先访问叶子节点,从左子树到右子树,再到根节点啦。相关路径如下:

algorithm/binary_tree/postorder_traversal

上图后续遍历的结果是:10,30,22,77,92,81,56,实现的代码如下:

1
2
3
4
5
6
7
function postOrder(node) {
if(!(node == null)) {
postOrder(node.left);
postOrder(node.right);
console.log(node.show() + " ");
}
}

细心的读者应该看到三种遍历都是以根节点为中心的啦。下面做个小小的题目:

❓已知某数据集有中序排序为3,16,22,23,37,45,99,它的先序排序为23,16,3,22,45,37,99,请问这个数据集的后序排列是什么呢?

二叉查找树查找最小值和最大值

查找BST上面的最小值和最大值非常简单。你应该留意到上面的图片中我特意标出的最小和最大值的位置。是的,最小值就是左叶子节点的值,遍历左子树,直到找到最后一个节点就行;最大值就是右叶子节点的值,遍历右子树,直到找到最后一个节点就行。代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 获取最小值
function getMin() {
var current = this.root;
while(!(current.left == null)){ // 或者current.left != null
current = current.left;
}
return current.data;
}

// 获取最大值
function getMax() {
var current = this.root;
while(!(current.right == null)){
current = current.right;
}
return current.data;
}

二叉查找树查找给定值

在BST上查找给定的值,需要比较该值和当前节点上的值的大小。通过比较,就能确定如果给定的值不在当前节点时,该向左遍历还是向右遍历。相关的查找代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
function find(data) { // @param data是传进来要查找的数据
var current = this.root;
while(current !=null ){
if(current.data == data) {
return current;
} else if(data < current.data) {
current = current.left; // 向左查找
} else {
current = current.right; // 向右查找
}
}
return null;
}

二叉查找树删除节点

在二叉查找树上删除节点比较复杂,分为下面的几种情况:

  • 删除的节点是叶子节点(最简单)
    • 方法: 将叶子节置为null,也就是其父节点的左指针或右指针指向了null
  • 删除的节点有一个字节点(较复杂)
    • 方法: 将原本指向的父节点左一些调整,使其指向删除节点的子节点就行
  • 删除的节点包含两个子节点(最复杂)
    • 方法一:要么查找待删除节点左子树上的最大值
    • 方法二:要么查找待删除节点右子树上的最小值(演示采用此种方法 )

为了管理删除操作的复杂度,这里使用了递归的操作,同时定义两个方法:remove()removeNode()remove()方法只是简单地接受待删除数据,调用removeNode()删除它,后者才是完成主要工作的方法。相关的代码如下:

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
function remove(data){ // @oaram data是要删除的数据
root = removeNode(this.root , data);
}

function removeNode(node , data){
if(node == null) {
return null;
}
if(data == node.data) {
// 叶子节点
if(node.left == null && node.right == null) {
return null;
}
// 没有左子节点的节点
if(node.left == null) {
return node.right;
}
// 没有右子节点的节点
if(node.right == null) {
return node.left;
}
// 有两个子节点的节点
var tempNode = getSmallest(node.right); // getSmallest()方法和getMin()类似
node.data = tempNode.data;
node.right = removeNode(node.right , tempNode.data); // 这一步的removeNode()是删除替换后的右子树的最小节点
return node;
}
else if(data < node.data){
node.left = removeNode(node.left , data);
return node;
}
else {
node.right = removeNode(node.right , data);
return node;
}
}

嗯~二叉查找树的知识点核心大概就是这么一丢丢了。本博文的参考自《数据结构和算法JavaScript描述》一书。如有不妥的地方还请多多指教@-@.

更多的内容请戳我的github!

algorithm/binary_tree/binary_tree_qiaoba

<-- 本文已结束  感谢您阅读 -->
客官,且步,赏一个呗 (@ ~ @)