二叉树原理手记。
二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结
点。然而,没有足够的信息来区分左结点和右结点。如果不考虑连通性,允许图中有多个连通分量,这样的结构叫做森林。二叉树是由n(n>=0)个结点组成的有序集合
集合或者为空,或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
设计二叉树逻辑
1 | function BinaryTree(){ |
树逻辑设计完成之后,构造一系列节点,来调用这个二叉树的接口,进行节点插入的过程
1 | var ndoes=[8,3,10,1,6,14,4,7,13]; //构造一个数组定义插入节点的数值 |
一开始二叉树是空的,所以第一次插入节点的时候节点8就成了根节点,也就是起始二叉树的根节点
用chrome调试可以看到二叉树生成的过程
第二个节点3进来的时候会和根节点比较,然后成为节点8的左孩子
第三次进来的时候是节点10,节点10会和8比对,发现比8大并且节点8的右孩子节点为空,所以节点10就成了节点8的右孩子
第四次进来的是节点1,此时二叉树已经有了根节点8以及左孩子3,右孩子10,然后进来的1比8小,而且此时已经有了左孩子3,左孩子3此时是没有左右孩子节点的,所以进来的1成了3的左孩子
第五次加入的是节点6,由于节点6是小于节点8的并且大于此时节点8的左孩子节点3,所以就成了此时空着的节点3的右节点
它的过程是6进来的时候和8比对,然后8此时有了左孩子3,然后6和3比对,6>3而且此时3没有右孩子,所以就成了3的右孩子
第六次进来的是节点14,由于节点14大于节点8所以走右边,因为节点8的右孩子此时是10,14大于10而且节点10此时没有右孩子,所以就成了节点10的右孩子
以此类推,最后根据给的数组生成了一颗二叉树
有了一棵构建好的排序二叉树之后,可以用遍历获取二叉树中每个节点的信息,遍历分三种方法,中序遍历、前序遍历、后序遍历
中序遍历
中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。
假如此时我处于某一个节点,处于这个节点的时候,我先看左孩子有没有,如果有的话,遍历整棵左子树,遍历完整棵左子树之后再返回来输出当前节点,输出完之后
再去遍历整棵右子树,遍历完之后,一个节点的左子树和右子树以及它本身就都被遍历完了,然后它沿着箭头向它的父节点遍历,依赖这个中序遍历的话实际上是以升
序的方式访问整个二叉树的节点
给BinaryTree增加一个中序遍历的接口
1 | var inOrderTraverseNode=function(node,callback){ //node=二叉树的节点对象,callback=普通回调函数 |
前序遍历
前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。
给BinaryTree增加一个前序遍历的接口
1 | var preOrderTraverseNode=function(node,callback){ |
后序遍历
后序遍历(LRD)是二叉树遍历的一种,也叫做后根遍历、后序周游,可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根,即首先遍历
左子树,然后遍历右子树,最后访问根结点。
给BinaryTree增加一个后序遍历的接口
1 | var postOrderTraverseNode=function(node,callback){ |
二叉树节点查找
主要是看某个给定数值的节点是否在二叉树中存在,设想开发作战游戏,飞机发出导弹的运行轨迹在不断改变,那它能否击中外星人了,这样就把外星人的坐标当成
一个二叉树,导弹前进的时候坐标也在变化,导弹每前进一次,坐标变化之后就在外星人坐标的二叉树中查找,如果导弹的坐标和外星人在二叉树中的坐标重合的话
,也就是说,在二叉树中找到了一个数值和导弹的数值是一样的,也就是击中了,要是找不到的话,就说明导弹击不中外星人
二叉树的节点查找分三种
1、查找二叉树最小节点,从当前节点出发查找节点左子树1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//查找二叉树最小节点接口
var minNode=function(node){
if(node){
while(node&&node.left!==null){
node=node.left
}
return node.key
}
return null
}
this.min=function(){
return minNode(root)
}
console.log(`二叉树的最小节点是${binaryTree.min()}`)
2、查找二叉树最大节点,从当前节点出发查找节点右子树1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//查找二叉树最大节点接口
var maxNode=function(node){
if (node) {
while(node&&node.right!==null){
node=node.right
}
return node.key
}
return null
}
this.max=function(){
return maxNode(root)
}
console.log(`二叉树的最小节点是${binaryTree.max()}`)
3、给定某个节点数值,然后和根节点进行比对大小,大的话从右子树继续比对,小的话就是左子树,如果是一样的话,直接返回当前节点的值,如果没找到可以认为是查找失败1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18//查找给定的节点
var searchNode=function(node,key){
if (node===null) {
return false
}
if (node.key>key) {
return searchNode(node.left,key)
}else if (node.key<key) {
return searchNode(node.right,key)
}else{
return true
}
}
this.search=function(key){
return searchNode(root,key)
}
console.log(binaryTree.search(6)?`key is 6`:`not found`) //6是二叉树中有的节点
console.log(binaryTree.search(16)?`key is 16`:`not found`) //16是二叉树中没有的节点
二叉树节点删除
删除只有一个子树的节点
1 | //接口 |
假如删除的节点含有左右子树的话,就要从被删除节点的右子树中找到最小的子节点,然后将要删除的节点的值换成找到的最小的子节点的值,这样二叉树里面就有
两个相同的节点,这时候就要把最小子节点去掉,做完这些步骤之后二叉树仍然是保持平衡性质的,这时候接口可以改成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
40var findMinNode=function(node){
if (node) {
while(node&&node.left!==null){
node=node.left
}
return node
}
return node
}
var removeNode=function(node,key){
if (node===null) {
return null
}
if (key<node.key) {
node.left=removeNode(node.left,key)
return node
}else if (key>node.key) {
node.right=removeNode(node.right,key)
}else{
if (node.left===null&&node.right===null) {
node=null
return node
}
if (node.left===null) {
node=node.right
return node
}else if (node.right===null) {
node=node.left
return node
}
//执行到这里就说明这是有两个子树的节点
var aux=findMinNode(node.right) //找到这个节点,在节点右子树中找到最小的子节点
node.key=aux.key //找到之后把这个节点的值更新成这个子节点的值
node.right=removeNode(node.right,aux.key) //从右子树中把这个最小子节点删除
return node //删除之后得到平衡的二叉树
}
}
this.remove=function(key){
removeNode(root,key)
}
应用场景:前序遍历用于复制二叉树,因为即使你想重新根据节点生成,如果节点多的话,算法的空间复杂度是很大的,前序遍历复制的效率要比重新生成的效率高出10倍左右
,中序遍历可用于排序,后序遍历可以用在系统文件检索。