人人都能看懂的数据结构 | 二叉树
-
本文已获得原作者的独家授权,有想转载的朋友们可以在后台联系我申请开白哦! -
PS:欢迎掘友们向我投稿哦,被采用的文章还可以送你掘金精美周边!
概述
二叉树中的节点最多只能有两个子节点:一个是左侧子节点,另一个是右侧子节点。二叉树分两种节点:一种有子节点的节点叫作“内部节点”;一种没有子节点的叫作“叶节点”
一棵标准的二叉树就长上图那样。
创建一棵BST(二叉查找树)
二叉查找树是一颗比较特殊的二叉树,树左侧的节点必须必右侧节点小。
需求分析
节点类:每个节点都要有一个元素(key),和左右指针(left、right);二叉树类:需要一个跟节点(root),需要一个插入节点方法(insert)。
代码实现
// 节点类
class Node {
constructor(key) {
//需要创建的元素
this.key = key
//左指针
this.left = null
//右指针
this.right = null
}
}
//二叉树类
class BinarySearchTree {
constructor() {
// 跟节点
this.root = null
}
//插入节点方法
insert(key) {}
}
插入节点需求分析
认真看的同学,会发现上面的
insert方法
是还没有实现的,实现其实本不难,但是我的本意是想让大家知道为什么是这样做,而不是直接贴代码。
不清楚手机是否能看清,图片的文字,这里还是把里面的文字帖了一下。
-
①第一次进来,还是一棵空树,也就是还没有根节点;假设,现在要插入一个节点11,但是现在还没有根节点,那么这个11就应该成为根节点
-
②假设下一次要插入一个节点7,那么这棵树应该存在根节点了,这次插入的节点就不应该成为根节点而是成为子节点,那么它应该成为谁的子节点呢?又应该成为左节点还是右节点呢?
-
2.1:首页,应该从根节点开始对比,现在根节点是11,而要插入的节点是7,7比11小,那么7就应该在父节点的左边,反而就在右边。
-
2.2:(这是图上红色部分)第一种情况,假设刚好当前的树根节点没有左节点,而要插入的节点7就顺理成章成为11的左节点了。
-
2.3:(图上绿色部分)第二种情况,假设现在根节点已经存在左节点8,那么现在要插入的节点7就不能再成为节点11的左节点了,它只能继续往下走,继续跟8对比,现在又回到了2.1步骤,只是根节点换成了8,因此,添加节点是一个递归的过程。
代码实现插入节点需求
class BinarySearchTree {
constructor() {
this.root = null
this.tree = []
}
insert(key) {
// 如果还没有根节点就添加根节点
if (this.root === null) {
this.root = new Node(key)
} else {
// 如果有根节点就添加左节点或者右节点
this.insertNode(this.root, key)
}
}
insertNode(node, key) {
// 要添加的节点,比父节点小,就走添加左节点流程,反而走添加右节点流程
if (node.key > key) {
// 如果刚好当前节点还没有左节点,那就直接添加,否则,就让继续执行insertNode函数递归下去,直到找到合适的位置创建
node.left === null ? node.left = new Node(key) : this.insertNode(node.left, key)
} else {
// 如果刚好当前节点还没有右节点,那就直接添加,否则,就让继续执行insertNode函数递归下去,直到找到合适的位置创建
node.right === null ? node.right = new Node(key) : this.insertNode(node.right, key)
}
}
}
测试插入节点实例
let tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(9)
tree.insert(13)
console.log(tree.root)
代码结构如上图
二叉树的遍历
二叉树遍历方式
中:中节点(也可以说是父节点);右:右节点;左:左节点。
-
中序遍历:以上行顺序访问所有节点的遍历方式,也就是以从最小到最大的顺序访问所有节点;访问规则是
左中右
。 -
先序遍历:先访问根节点,然后以同样方式访问左子树和右子树;访问规则是
中左右
。 -
后序遍历:先访问叶子节点,从左子树到右子树,再到根节点;访问规则是
左右中
。
中序遍历
按照中序遍历的规则(左中右),上面那棵树应该如何遍历?
-
①: 第一次按照规则可以按规左中右则拆成三部分
[22,10,30],[56],[81,77,92]
,如上图。 -
②: 第二次拆分,第一部分还有是内部节点,还可以按照规则拆分
[10,22,30]
,第二部分,已经是叶节点了,就不用再拆了,直接拖下来[56]
,第三部分,还是内部节点,还可以按照规则拆分[77,81,92]
,如上图。 -
③:第二次拆分完,全部节点都成立叶节点,就不需要再继续拆下去了,所以最终的中序遍历结果为:
[10, 22, 30, 56, 77, 81, 92]
,如上图。 -
④:很明显这个过程是一个递归的过程。
遍历规则都理顺了,那么用代码实现就非常简单了。
代码实现
class BinarySearchTree {
constructor() {
...
// 存放遍历后的结果
this.tree = []
}
...
// 中序遍历
inOrderTraverseNode(node) {
if (node !== null) {
this.inOrderTraverseNode(node.left)
this.tree.push(node.key)
this.inOrderTraverseNode(node.right)
}
}
}
let tree = new BinarySearchTree()
tree.insert(56)
tree.insert(22)
tree.insert(81)
tree.insert(10)
tree.insert(30)
tree.insert(77)
tree.insert(92)
// 从根开始遍历
tree.inOrderTraverseNode(tree.root)
console.log(tree.tree) //[10, 22, 30, 56, 77, 81, 92]
代码实现非常简单就几行。
先序遍历
按照先序遍历的规则(中左右),想必大家如果看懂上面的中序遍历,先序遍历就是如鱼得水,唾手可及,快马加鞭,九牛一虎,勾股定理,杠杆原理...的事了。
-
①: 第一次按照规则可以按规中左右则拆成三部分
[56],[22,10,30],[81,77,92]
,如上图。 -
②: 第二次拆分,第一部分,已经是叶节点了,就不用再拆了,直接拖下来
[56]
,第二部分还有是内部节点,还可以按照规则拆分[22,10,30]
,第三部分,还是内部节点,还可以按照规则拆分[81,77,92]
,如上图。。 -
③:第二次拆分完,全部节点都成立叶节点,就不需要再继续拆下去了,所以最终的中序遍历结果为:
[56, 22, 10, 30, 81, 77, 92]
,如上图。
代码实现
class BinarySearchTree {
...
// 先序遍历
preOrderTraverseNode(node) {
if (node !== null) {
this.tree.push(node.key)
this.preOrderTraverseNode(node.left)
this.preOrderTraverseNode(node.right)
}
}
}
let tree = new BinarySearchTree()
tree.insert(56)
tree.insert(22)
tree.insert(81)
tree.insert(10)
tree.insert(30)
tree.insert(77)
tree.insert(92)
// 从根开始遍历
tree.postOrderTraverse(tree.root)
console.log(tree.tree) //[56, 22, 10, 30, 81, 77, 92]
先序遍历跟先中序遍历代码都是大同小异的。
后序遍历
如果上面的两种遍历都看懂了,那么后序遍历就是...的事了。
-
①: 第一次按照规则可以按规左右中则拆成三部分
[22,10,30],[81,77,92],[56]
,如上图。 -
②: 第二次拆分,第一部分,还有是内部节点,还可以按照规则拆分
[10,30,22]
,第二部分还是内部节点,还可以按照规则拆分[77,92,81]
,第三部分,已经是叶节点了,就不用再拆了,直接拖下来[56]
,如上图。 -
③:第二次拆分完,全部节点都成立叶节点,就不需要再继续拆下去了,所以最终的中序遍历结果为:
[10, 30, 22, 77, 92, 81, 56]
,如上图。
二叉树的搜索
-
搜索最大节点
-
搜索最小节点
-
搜索某个节点是否存在
搜索最大节点
没错还是以这个图为例,惊喜不。
按照二叉树的规则,小值在左,大值在右。那么最大节点肯定就是在最右底脚的那个叶节点了。
代码实现
class BinarySearchTree {
...
maxNode(node) {
// 一直往右边找,直到找到最右边的叶节点
while (node.right !== null) {
node = node.right
}
return node
}
}
...
let tree = new BinarySearchTree()
tree.maxNode(tree.tree) // 92
实现代码也非常简单。
搜索最小节点
按照二叉树的规则,小值在左,大值在右。那么最小节点肯定就是在最左底脚的那个叶节点了,刚好跟最大节点相反。
代码实现
class BinarySearchTree {
...
minNode(node) {
// 一直往左边找,直到找到最左边的叶节点
while (node.left !== null) {
node = node.left
}
return node
}
}
...
let tree = new BinarySearchTree()
tree.minNode(tree.tree) // 10
搜索某个特定的节点
搜索某个特定的节点,也是从根节点开始,先当前节点是否跟指定节点相同,相同就返回
true
;不同就看指定节点比当前节点大还是小,小继续往左边找,大就往右边找,一直到找到或者为null
为止。
代码实现
class BinarySearchTree {
...
searchNode(node, key) {
if (node === null) return false
if (node.key === key) {
return true
} else {
return node.key > key ? this.searchNode(node.left, key) : this.searchNode(node.right, key)
}
}
}
...
let tree = new BinarySearchTree()
// 从根开始找,指定找199,
let res = tree.searchNode(tree.root, 199)
console.log(res) // false
删除某个特定节点
为什么把删除节点放在最后呢?其实一开始不打算写这一部分的,因为这部分是比较难理解的,也不知道自己能不能描述清楚,但是写完文章之后,总觉得不加上这部分,文章不完整,缺了点什么。
节点删除有三种情况
-
①:要删除的节点没有左右节点,这种比较好处理,直接将要删除的节点置为
null
,或者直接返回null
。 -
②:要删除的节点左右节点有其中一个,这种情况,就要把左节点或者右节点返回给上一个父节点就行。
-
③:要删除的节点有左右节点,这种是最复杂的情况了,首先找到要删除的节点,再找到要删除节点的右侧最小节点,或者左侧最大节点,来替换要删除的节点,最后,再把刚刚找到的那个最大节点(最小节点)删除。
代码实现
class BinarySearchTree {
...
removeNode(node,key){
if (node === null) return null
if (node.key === key) {
// 情况一
if(node.left === null && node.right === null){
return null
// 情况二
}else if(node.left === null || node.right === null){
let key = node.left ? 'left' : 'right'
return node[key]
// 情况三
}else{
let aux =this.minNode(node.right)
node.key = aux.key
node.right = this.removeNode(node.right, aux.key)
return node
}
} else {
let nodeKey = node.key > key ? "left" : "right"
node[nodeKey] = node.key > key ? this.removeNode(node.left, key) : this.removeNode(node.right, key)
return node
}
}
}
完整代码
class Node {
constructor(key) {
this.key = key
this.left = null
this.right = null
}
}
class BinarySearchTree {
constructor() {
this.root = null
this.tree = []
}
insert(key) {
if (this.root === null) {
this.root = new Node(key)
} else {
this.insertNode(this.root, key)
}
}
insertNode(node, key) {
if (node.key > key) {
node.left === null ? node.left = new Node(key) : this.insertNode(node.left, key)
} else {
node.right === null ? node.right = new Node(key) : this.insertNode(node.right, key)
}
}
inOrderTraverseNode(node) {
if (node !== null) {
this.inOrderTraverseNode(node.left)
this.tree.push(node.key)
this.inOrderTraverseNode(node.right)
}
}
preOrderTraverseNode(node) {
if (node !== null) {
this.tree.push(node.key)
this.preOrderTraverseNode(node.left)
this.preOrderTraverseNode(node.right)
}
}
postOrderTraverse(node) {
if (node !== null) {
this.postOrderTraverse(node.left)
this.postOrderTraverse(node.right)
this.tree.push(node.key)
}
}
minNode(node) {
while (node.left !== null) {
node = node.left
}
return node
}
maxNode(node) {
while (node.right !== null) {
node = node.right
}
return node
}
searchNode(node, key) {
if (node === null) return false
if (node.key === key) {
return true
} else {
return node.key > key ? this.searchNode(node.left, key) : this.searchNode(node.right, key)
}
}
removeNode(node,key){
if (node === null) return null
if (node.key === key) {
if(node.left === null && node.right === null){
return null
}else if(node.left === null || node.right === null){
let key = node.left ? 'left' : 'right'
return node[key]
}else{
let aux =this.minNode(node.right)
node.key = aux.key
node.right = this.removeNode(node.right, aux.key)
return node
}
} else {
let nodeKey = node.key > key ? "left" : "right"
node[nodeKey] = node.key > key ? this.removeNode(node.left, key) : this.removeNode(node.right, key)
return node
}
}
}
重组二叉树
重组二叉树什么意思?也就是说现在不是给你一颗二叉树,让你找出它的先、中、后序遍历了,而是给你先,中,后反推成一颗二叉树。
某大厂的一道面试题:根据先序[1,2,4,7,3,5,6,8]和中序[4,7,2,1,5,3,8,6],重组二叉树。
题目分析:
-
这里说的是重组的是二叉树,不是BST(二叉查找树),所以没有小在左,大在右的概念。
-
重组二叉树,还是可以按先,中,后的遍历规则
-
①:先序的第一个肯定是根节点(也可以说是中,父节点)
-
②:在中序列表找到根位置,然后根据这个位置,找出左节点和右节点的先序和中序
-
递归①,②步,直到节点为null/undefinde。
代码实现
class Node {
constructor(key) {
this.key = key
this.left = null
this.right = null
}
}
let preOrder = [1,2,4,7,3,5,6,8]
let inOrder = [4,7,2,1,5,3,8,6]
class regroupTree{
constructor(){
this.root = null
}
sliceTree(preOrder,inOrder){
let node = preOrder[0]
// 判断根节点存不存在
if(node){
// 找到根节点在中序列表的位置
let index = inOrder.indexOf(node)
// 通过根节点位置,找到左节点的中序
let inOrderLeft = inOrder.slice(0,index)
// 通过根节点位置,找到右节点的中序
let inOrderRight = inOrder.slice(index+1)
// 通过根节点位置,找到左节点的先序
let preOrderLeft = preOrder.slice(1,index+1)
// 通过根节点位置,找到右节点的先序
let preOrderRight = preOrder.slice(index+1)
let root = new Node(node)
root.left = this.sliceTree(preOrderLeft,inOrderLeft)
root.right = this.sliceTree(preOrderRight,inOrderRight)
return root
}
}
buildTree(preOrder,inOrder){
this.root = this.sliceTree(preOrder,inOrder)
}
}
let tree = new regroupTree()
tree.buildTree(preOrder,inOrder)
console.log(tree.tree)
加两个方法(先序遍历,中序遍历)验证一下
let preOrder = [1,2,4,7,3,5,6,8]
let inOrder = [4,7,2,1,5,3,8,6]
class regroupTree{
constructor(){
...
this.tree = []
}
...
inOrderTraverseNode(node) {
if (node) {
this.inOrderTraverseNode(node.left)
this.tree.push(node.key)
this.inOrderTraverseNode(node.right)
}
}
preOrderTraverseNode(node) {
if (node) {
this.tree.push(node.key)
this.preOrderTraverseNode(node.left)
this.preOrderTraverseNode(node.right)
}
}
}
let tree = new regroupTree()
tree.buildTree(preOrder,inOrder)
tree.preOrderTraverseNode(tree.root) // [1,2,4,7,3,5,6,8]
// tree.preOrderTraverseNode(tree.root) [4,7,2,1,5,3,8,6]
结尾
看完希望你对二叉树概念,遍历规则,找最大节点,最小节点,找特点节点,删除特定节点,二叉树重组都有一个更深的理解,希望你这一趟没有白点进来🤡