HelloWorld
登录

js实现二叉树、二叉查找树

白茶清欢

2021-04-21

2325 4 0

树是一种数据结构，该章节讨论二叉树（二叉树的每个节点的子节点不允许超过两个），二叉树中有又分为完全二叉树和不完全二叉树.....

不在本章节赘述相关概念，感兴趣可以去查阅《数据结构》。

你将会获得：

1.如何使用js实现二叉查找树。

2.学会前、中、后序遍历。

3.了解相关实现原理

阅读时长>5min，可选择直接调试代码

特点

    二叉查找树中序遍历后，得到的增序的排列方式。

预览

以下封装的二叉查找树，包含了查找方法

1function Node(data, left, right) {
2  this.data = data;
3  this.left = left;
4  this.right = right;
5
6}
7Node.prototype.show = function() {
8  return this.data;
9}
10
11
12function BST() {
13  this.root = null;
14}
15BST.prototype.insert = function (data) {
16  var n = new Node(data, null, null);
17  if (this.root == null) {
18    this.root = n;
19  } else {
20    var current = this.root;
21    var parent;
22    while (true) {
23      parent = current;
24      if (data < current.data) {
25        current = current.left;
26        if (current == null) {
27          parent.left = n;
28          break;
29        }
30      } else {
31        current = current.right;
32        if (current == null) {
33          parent.right = n;
34          break;
35        }
36      }
37    }
38  }
39}
40
41BST.prototype.inOrder = function(node) {
42  //  中序遍历
43  if (!(node == null)) {
44    inOrder(node.left);
45    console.log(node.show() + "");
46    inOrder(node.right);
47  }
48}
49
50BST.prototype.preOrder = function(node) {
51  //  先序
52  if (!(node == null)) {
53    console.log(node.show() + "");
54    preOrder(node.left);
55    preOrder(node.right);
56  }
57}
58
59BST.prototype.postOrder = function(node) {
60  //  先序
61  if (!(node == null)) {
62    postOrder(node.left);
63    postOrder(node.right);
64    console.log(node.show() + "");
65  }
66}
67
68//  查找最小值
69
70BST.prototype.getMin = function() {
71  var current = this.root;
72  while (current.left !== null) {
73    current = current.left;
74  }
75  return current.data;
76}
77
78//  查找最大值
79
80BST.prototype.getMax = function() {
81  var current = this.root;
82  while (current.right !== null) {
83    current = current.right;
84  }
85  return current.data;
86}
87
88//  查找给定值
89BST.prototype.find = function(data) {
90  var current = this.root;
91  while (current != null) {
92    if (current.data == data) {
93      return current;
94    } else if (data < current.data) {
95      current = current.left;
96    } else if (data > current.data) {
97      current = current.right;
98    }
99  }
100  return null;
101}
102
103
104
105BST.prototype.remove = function(data) {
106  
107  this.root = this.removeNode(this.root, data);
108  console.log(this.root,1)
109}
110
111BST.prototype.removeNode = function(node, data) {
112  if (node == null) {
113    return null;
114  }
115  if (data == node.data) { 
116    // 没有子节点的节点 
117    if (node.left == null && node.right == null) {
118      return null;
119    } 
120    // 没有左子节点的节点 
121    if (node.left == null) {
122      return node.right;
123    } 
124    // 没有右子节点的节点 
125    if (node.right == null) {
126      return node.left;
127    } 
128    //  查找最小节点
129    let getSmallest = function(node) {
130      if (node.left === null && node.right == null) {
131          return node;
132      }
133      if (node.left != null) {
134          return node.left;
135      }
136      if (node.right !== null) {
137          return getSmallest(node.right);
138      }
139
140  }
141    // 有两个子节点的节点 
142    var tempNode = getSmallest(node.right);
143    node.data = tempNode.data;
144    node.right = this.removeNode(node.right, tempNode.data);
145    return node;
146  } else if (data < node.data) {
147    node.left = this.removeNode(node.left, data);
148    return node;
149  } else {
150    node.right = this.removeNode(node.right, data);
151    return node;
152  }
153}

中序排列

1var nums = new BST(); 
2nums.insert(23); 
3nums.insert(45); 
4nums.insert(16); 
5nums.insert(37); 
6nums.insert(3); 
7nums.insert(99); 
8nums.insert(22); 
9console.log("Inorder traversal: "); 
10nums.inOrder(nums.root);
11
12> Inorder traversal: 
13> 3 16 22 23 37 45 99 // 增序

1.实现

二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点。这一特性使得查找效率很高，对于数值型和非数值型的数据，比如单词和字符串都是如此。

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

1.1创建BST类

BST 先要有一个 insert() 方法，用来向树中加入新节点。

首先要创建一个 Node 对象，将数据传入该对象保存。其次检查 BST 是否有根节点，如果没有，那么这是棵新树，该节点就是根节点，这个方法 到此也就完成了；否则，进入下一步。如果待插入节点不是根节点，那么就需要准备遍历 BST，找到插入的适当位置。该过程类 似于遍历链表。用一个变量存储当前节点，一层层地遍历 BST。进入 BST 以后，下一步就要决定将节点放在哪个地方。找到正确的插入点时，会跳出循 环。查找正确插入点的算法如下。

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

1function Node(data, left, right) {
2  this.data = data;
3  this.left = left;
4  this.right = right;
5
6}
7Node.prototype.show = function() {
8  return this.data;
9}
10
11
12function BST() {
13  this.root = null;
14}
15BST.prototype.insert = function (data) {
16  var n = new Node(data, null, null);
17  if (this.root == null) {
18    this.root = n;
19  } else {
20    var current = this.root;
21    var parent;
22    while (true) {
23      parent = current;
24      if (data < current.data) {
25        current = current.left;
26        if (current == null) {
27          parent.left = n;
28          break;
29        }
30      } else {
31        current = current.right;
32        if (current == null) {
33          parent.right = n;
34          break;
35        }
36      }
37    }
38  }
39}

‍以上是最主要的，二叉查找树的js实现，其他方法简单描述一下

中序：就是先访问左子节点-->根节点-->右子节点

先序： 就是先访问根节点再访问子节点

后序:最后访问根节点

删除二叉树节点：

删除节点主要分为，叶子节点，有左节点，有右节点，有两个子节点；

思路就是：

  1. 找到要删除节点，判断是否含有子节点。

  2. 如果没有子节点，便将该节点的值置为null。

    2.1 有左/右节点，被删节点指向子节点。

    2.2 含左右节点:

  • （1）查找待删节点的左子树的最大值
  • （2）查找待删节点的右子树的最小值

将待删节点的值替换成以上（1）/（2）的值

以下选的是（2）方案

1BST.prototype.remove = function(data) {
2  //  最后改变根节点值
3  this.root = this.removeNode(this.root, data);
4}
5//  返回的是node类型
6BST.prototype.removeNode = function(node, data) {
7  if (node == null) {
8    return null;
9  }
10  if (data == node.data) { 
11    // 没有子节点的节点 
12    if (node.left == null && node.right == null) {
13      return null;
14    } 
15    // 没有左子节点的节点 
16    if (node.left == null) {
17      return node.right;
18    } 
19    // 没有右子节点的节点 
20    if (node.right == null) {
21      return node.left;
22    } 
23    //  查找最小节点
24    let getSmallest = function(node) {
25      if (node.left === null && node.right == null) {
26          return node;
27      }
28      if (node.left != null) {
29          return node.left;
30      }
31      if (node.right !== null) {
32          return getSmallest(node.right);
33      }
34
35  }
36    // 有两个子节点的节点 
37    var tempNode = getSmallest(node.right);
38    node.data = tempNode.data;
39    //  处理待删节点的右子树
40    node.right = this.removeNode(node.right, tempNode.data);
41    return node;
42  } else if (data < node.data) {
43    node.left = this.removeNode(node.left, data);
44    return node;
45  } else {
46    node.right = this.removeNode(node.right, data);
47    return node;
48  }
49}

欢迎关注《前端划水笔记》

原文地址 https://mp.weixin.qq.com/s/Qc5_68ljBWjVee6cHrFUTg。

点赞
收藏

评论区

加载中...

相关推荐

MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1

文章目录问题用navicat导入数据时，报错：原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等，这样可以更容易地在不同的环境中使用MySQL。全局s

Oracle 分组与拼接字符串同时使用

SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(

手写Java HashMap源码

HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22

二叉树创建后，如何使用递归和栈遍历二叉树？

0.前言前文主要介绍了树的相关概念和原理，本文主要内容为二叉树的创建及遍历的代码实现，其中包括递归遍历和栈遍历。1.二叉树的实现思路1.0.顺序存储——数组实现前面介绍了满二叉树和完全二叉树，我们对其进行了编号——从0到n的不中断顺序编号，而恰好，数组也有一个这样的编号——数组下标，只要我们把二者联合起来，数组就能存储二叉树了。那么非满

JAVA递归实现线索化二叉树

JAVA递归实现线索化二叉树基础理论首先，二叉树递归遍历分为先序遍历、中序遍历和后序遍历。先序遍历为：根节点左子树右子树中序遍历为：左子树根节点右子树后序遍历为：左子树右子树根节点（只要记住根节点在哪里就是什么遍历，且都是先左再右）线索化现在有这么一棵二叉树，它的数据结

04.重建二叉树 (Java)

题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。(https://www.oschina.net/action/GoToLink?urlht