&web_id=" language="JavaScript">
Fork me on GitHub

JavaScript 树

树的定义

在计算机科学中,树(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
1.每个节点有零个或多个子节点;
2.没有父节点的节点称为根节点;
3.每一个非根节点有且只有一个父节点;
4.除了根节点外,每个子节点可以分为多个不相交的子树。

JavaScript树的结构

今天我们要讲的是排序二叉树的JavaScript实现,首先,排序二叉树的节点跟我们双向链表的节点很像,都有两个指针,不同的是,它的指针指向的是它的左孩子和右孩子,具体实现如下:

1
2
3
4
5
6
7
8
9
function Node(element,leftChild,rightChild){ //传入节点的值,左右指针
this.data = element;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.show = show;
}
function show(){ //显示节点的值
return this.data;
}

下面我们就要实现树这种数据结构了,每次我们要新建一个树都需要新建一个根节点让其指向null

1
2
3
4
5
6
7
8
9
10
11
function BST(){
this.root = null;
this.insert = insert; //插入节点
this.maxValue = maxValue; //寻找树中的最大值
this.minValue = minValue; //寻找树中的最小值
this.find = find; //寻找树中的某个值
this.preOrder = preOrder; //前序遍历
this.inOrder = inOrder; //中序遍历
this.postOrder = postOrder; //后序遍历
this.remove = remove; //删除某个节点
}

首先,我们要实现的就是树的节点的插入,这需要我们调用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
//插入
function insert(element){
var node = new Node(element,null,null);
if(this.root == null){
this.root = node; //让节点变成根节点
}
else{
var copy = this.root; //记录根节点的位置
var parents; //记录你找的节点的父节点的位置
while(1){
parents = copy;
if(element < copy.data){ //如果小就往左走
copy = copy.leftChild;
if(copy == null){
parents.leftChild = node;
console.log(parents);
break;
}
}
else{
copy = copy.rightChild; //如果大就往右走
if(copy == null){
parents.rightChild = node;
console.log(parents);
break;
}
}
}
}
}

这就是简单的非递归调用了,接下来我们来试试查找一下我们的树中的节点。

节点的查找

节点的查找分为三类:查找树中的最大值,查找树中的最小值,查找树中的某个值。查找的思路很简单,查找树中的某个值就跟插入函数很像,只不过插入函数找到某个节点后插入,而查找只需要返回就行了。查找树中的最大值也很简单,一直找根节点的rightChild直到为空,即为最大值,最小值同理,具体代码实现:

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
//查找最大值
function maxValue(){
if(this.root == null){
console.log("此树中无节点!无法获取最大值。");
}
else{
var copy = this.root;
while(1){
if(copy.rightChild != null){
copy = copy.rightChild;
}
else{
console.log(copy.show());
break;
}
}
}
}
//查找最小值
function minValue(){
if(this.root == null){
console.log("此树中无节点!无法获取最大值。");
}
else{
var copy = this.root;
while(1){
if(copy.leftChild != null){
copy = copy.leftChild;
}
else{
console.log(copy.show());
break;
}
}
}
}
//查找某个值,返回节点
function find(element){
if(this.root == null){
console.log("此树中无节点!无法获取节点。")
}
else{
var copy = this.root;
while(1){
if(element < copy.data){
copy = copy.leftChild;
if(copy == null){
console.log("此树中无此节点!请检查数值是否正确。");
break;
}
}
else if(element > copy.data){
copy = copy.rightChild;
if(copy == null){
console.log("此树中无此节点!请检查数值是否正确。");
break;
}
}
else if(element == copy.data){
console.log(copy);
break;
}
}
}
}

写的比较麻烦使让每一步尽可能的清晰,相对于递归调用跟容易理解问题。接下来就轮到我们的遍历问题了。

树的遍历

什么是树的遍历

在计算机科学里,树的遍历(也称为树的搜索)是图的遍历的一种,指的是按照某种规则,不重复地访问某种树的所有节点的过程。具体的访问操作可能是检查节点的值、更新节点的值等。不同的遍历方式,其访问节点的顺序是不一样的。以下虽然描述的是二叉树的遍历算法,但它们也适用于其他树形结构。

遍历的种类

与那些基本上都有标准遍历方式(通常是按线性顺序)的线性数据结构(如链表、一维数组)所不同的是,树结构有多种不同的遍历方式。从二叉树的根节点出发,节点的遍历分为三个主要步骤:对当前节点进行操作(称为“访问”节点)、遍历左边子节点、遍历右边子节点。这三个步骤的先后顺序也是不同遍历方式的根本区别。

由于从给定的某个节点出发,有多个可以前往的下一个节点(树不是线性数据结构),所以在顺序计算(即非并行计算)的情况下,只能推迟对某些节点的访问——即以某种方式保存起来以便稍后再访问。常见的做法是采用栈(LIFO)或队列(FIFO)。由于树本身是一种自我引用(即递归定义)的数据结构,因此很自然也可以用递归方式,或者更准确地说,用corecursion,来实现延迟节点的保存。这时(采用递归的情况)这些节点被保存在call stack中。

遍历方式的命名,源于其访问节点的顺序。最简单的划分:是深度优先(先访问子节点,再访问父节点,最后是第二个子节点)?还是广度优先(先访问第一个子节点,再访问第二个子节点,最后访问父节点)? 深度优先可进一步按照根节点相对于左右子节点的访问先后来划分。如果把左节点和右节点的位置固定不动,那么根节点放在左节点的左边,称为前序(pre-order)、根节点放在左节点和右节点的中间,称为中序(in-order)、根节点放在右节点的右边,称为后序(post-order)。对广度优先而言,遍历没有前序中序后序之分:给定一组已排序的子节点,其“广度优先”的遍历只有一种唯一的结果。

JavaScript实现树的遍历

根据上面的结构设计,我们要实现树的前序遍历,中序遍历和后序遍历。这里我们用递归实现,非常简单,只需要四行代码即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//前序排序
function preOrder(node){
if(node != null){
console.log(node.show()); //根
preOrder(node.leftChild); //左子树
preOrder(node.rightChild); //右子树
}
}
//中序排序
function inOrder(node){
if(node != null){
inOrder(node.leftChild); //左子树
console.log(node.show()); //根
inOrder(node.rightChild); //右子树
}
}
//后序排序
function postOrder(node){
if(node != null){
postOrder(node.leftChild); //左子树
postOrder(node.rightChild); //右子树
console.log(node.show()); //根
}
}

树节点的删除

删除的算法

接下来就是最考验脑力的删除操作了,因为在删除的过程中,你要考虑到不同的情况,针对每一种不同的情况,你要有针对性的反应和调整。树的删除具体分为五种情况和三个步骤:

1)判断参数的合法性,判断参数是否在当前的二叉树当中
2)删除的节点是根节点,此时应该怎么调整
3)删除的节点是普通节点,此时又应该怎么调整

情况一:删除的节点是根节点【即步骤二】
情况二:删除的节点是叶子节点
情况三:删除的节点只有左孩子没有右孩子
情况四:删除的节点只有右孩子没有左孩子
情况五:删除的节点既有左孩子也有右孩子

下面直接贴代码进行讲解:【为了更清晰的展示五种情况,将根单独列出来】

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
function remove(element){
if(this.root == null){
console.log("此树中无节点!无需删除节点。") //如果树为空,
}
else{
var copy = this.root; //删除节点的寻找
var parents;
var findNode;
while(1){
if(element < copy.data){
parents = copy;
copy = copy.leftChild;
if(copy == null){
console.log("此树中无此节点!请检查数值是否正确。");
return;
}
}
else if(element > copy.data){
parents = copy;
copy = copy.rightChild;
if(copy == null){
console.log("此树中无此节点!请检查数值是否正确。");
return;
}
}
else if(element == copy.data){
findNode = copy;
break;
}
}
if(findNode == this.root){ //删除节点为根节点判断四种情况
if((findNode.leftChild == null) && (findNode.rightChild == null)){
findNode = null;
}
else if((findNode.leftChild == null)&&(findNode.rightChild != null)){
findNode.data = findNode.rightChild.data;
findNode.rightChild = findNode.rightChild.rightChild;
findNode.leftChild = findNode.rightChild.leftChild;
}
else if((findNode.leftChild != null)&&(findNode.rightChild == null)){
findNode.data = findNode.leftChild.data;
findNode.rightChild = findNode.leftChild.rightChild;
findNode.leftChild = findNode.leftChild.leftChild;
}
else if((findNode.leftChild != null)&&(findNode.rightChild != null)){
var code = findNode.leftChild;
var studio;
while(1){
if(code.rightChild != null){
studio = code;
code = code.rightChild;
}
else{
break;
}
}
if(code==findNode.leftChild){
findNode.data = code.data;
findNode.leftChild = code.leftChild;
}
else{
findNode.data = code.data;
studio.rightChild = code.leftChild;
}
}
}
else{ // 不是根节点的四种情况
if((findNode.leftChild == null) && (findNode.rightChild == null)){
if(findNode.data > parents.data){
parents.rightChild = null;
}
else{
parents.leftChild = null;
}
}
else if((findNode.leftChild == null)&&(findNode.rightChild != null)){
if(findNode.data > parents.data){
parents.rightChild = findNode.rightChild;
}
else{
parents.leftChild = findNode.rightChild;
}
}
else if((findNode.leftChild != null)&&(findNode.rightChild == null)){
if(findNode.data > parents.data){
parents.rightChild = findNode.leftChild;
}
else{
parents.leftChild = findNode.leftChild;
}
}
else if((findNode.leftChild != null)&&(findNode.rightChild != null)){
var Chrome = findNode.leftChild;
var Google;
while(1){
if(Chrome.rightChild != null){
Google = Chrome;
Chrome = Chrome.rightChild;
}
else{
break;
}
}
if(Chrome==findNode.leftChild){
findNode.data = Chrome.data; //千万要记住只有一个左孩子的情况,我就错在这里了,报错的是rightChild undefined
findNode.leftChild = Chrome.leftChild;
}
else{
findNode.data = Chrome.data;
Google.rightChild = Chrome.leftChild;
}
}
}
}
}

今天的资料就分享到这里,接下来我还会持续更新所学的。谢谢大家。

Godlike Meteor wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
我知道不会有人点开,但万一真有人想不开呢?
------ 本文结束 ------