二叉树原理手记。


二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结
点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。二叉树是由n（n>=0）个结点组成的有序集合
集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

“二叉树”
“二叉树”

设计二叉树逻辑

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
function BinaryTree(){
	//定义节点
	var Node=function(key){
		this.key=key;
		this.left=null;
		this.right=null;
	};
	//定义一个根节点
	var root=null;
	//node老节点,newNode新节点（要插入一个新节点的时候，如果新节点比当前的老节点的值要小，那么就可以把新节点放到老节点的左边）
	var insertNode=function(node,newNode){  
	if (node.key>newNode.key) {   //如果新节点小于老节点或者
			if (node.left===null) {    //如果新节点还没有左节点的话
				node.left=newNode;     //可以把新节点当作老节点的左孩子
			}else{   //如果已经有左孩子了，就将这个新节点插入到左节点的左边部分
				insertNode(node.left,newNode);
			}
		}else{    //如果新节点大于老节点、，就插入老节点右边部分
			if(node.right===null){   //看老节点右边部分是不是为空
				node.right=newNode;   //如果老节点右边为空，就把这个新节点作为老节点的右孩子
			}else{    //如果右孩子不为空的话，继续往右边添加
				insertNode(node.right,newNode);                                         //到此为止，整个树的插入逻辑就设计完成了
			}
		}
	}
	this.insert=function(key){   //专门用来插入节点
		var newNode=new Node(key)  //根据传进来的节点数值，构造一个节点对象
		if (root===null) {       //如果此时根节点是空
			root=newNode;        //新插入的节点就是根节点
		}else{                  //否则根据排序二叉树的特性插入新的节点
			insertNode(root,newNode)    //插入新节点的方法
		}
	}
}

树逻辑设计完成之后，构造一系列节点，来调用这个二叉树的接口，进行节点插入的过程

1
2
3
4
5
6
var ndoes=[8,3,10,1,6,14,4,7,13];   //构造一个数组定义插入节点的数值
var binaryTree=new BinaryTree();    //实例化一个BinaryTree
//然后依次把数组中的数值插入二叉树，插入完之后，完整的二叉树就构成了
ndoes.forEach(function(key){
    binaryTree.insert(key)
})

一开始二叉树是空的，所以第一次插入节点的时候节点8就成了根节点，也就是起始二叉树的根节点

“进入的第一个节点”
“进入的第一个节点”

用chrome调试可以看到二叉树生成的过程
“根节点8”
“根节点8”

第二个节点3进来的时候会和根节点比较，然后成为节点8的左孩子
“左孩子3”
“左孩子3”

“左孩子3”
“左孩子3”

第三次进来的时候是节点10，节点10会和8比对，发现比8大并且节点8的右孩子节点为空，所以节点10就成了节点8的右孩子
“左孩子3”
“左孩子3”

第四次进来的是节点1，此时二叉树已经有了根节点8以及左孩子3，右孩子10，然后进来的1比8小，而且此时已经有了左孩子3,左孩子3此时是没有左右孩子节点的，所以进来的1成了3的左孩子
“左孩子1”
“左孩子1”

“左孩子1进来的时候和8比对”
“左孩子1进来的时候和8比对”

“左孩子1和8比对之后和3比对”
“左孩子1和8比对之后和3比对”

第五次加入的是节点6，由于节点6是小于节点8的并且大于此时节点8的左孩子节点3，所以就成了此时空着的节点3的右节点
“根节点8的左子树3的右孩子”
“根节点8的左子树3的右孩子”

它的过程是6进来的时候和8比对，然后8此时有了左孩子3，然后6和3比对，6>3而且此时3没有右孩子，所以就成了3的右孩子
“6和8比对”
“6和8比对”

“6和3比对”
“6和3比对”

第六次进来的是节点14，由于节点14大于节点8所以走右边，因为节点8的右孩子此时是10,14大于10而且节点10此时没有右孩子，所以就成了节点10的右孩子
“此时的二叉树”
“此时的二叉树”

“14和8比对”
“14和8比对”

“14和10比对”
“14和10比对”

以此类推，最后根据给的数组生成了一颗二叉树
“生成的排序二叉树”
“生成的排序二叉树”

有了一棵构建好的排序二叉树之后，可以用遍历获取二叉树中每个节点的信息，遍历分三种方法，中序遍历、前序遍历、后序遍历

中序遍历

中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
假如此时我处于某一个节点，处于这个节点的时候，我先看左孩子有没有，如果有的话，遍历整棵左子树，遍历完整棵左子树之后再返回来输出当前节点，输出完之后
再去遍历整棵右子树，遍历完之后，一个节点的左子树和右子树以及它本身就都被遍历完了，然后它沿着箭头向它的父节点遍历，依赖这个中序遍历的话实际上是以升
序的方式访问整个二叉树的节点

给BinaryTree增加一个中序遍历的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var inOrderTraverseNode=function(node,callback){    //node=二叉树的节点对象,callback=普通回调函数
if(node!==null){   //如果节点不为空的话
    inOrderTraverseNode(node.left,callback)  //访问它的左子树
    callback(node.key)   //访问完左子树之后访问当前节点，然后把当前节点的值传入回调函数中
    inOrderTraverseNode(node.right,callback)  //继续访问当前节点的右子树
    }
}

//callback=待会要输出某个节点的值得时候，把这个节点的值传入到这个回调函数中，让这个回调函数决定如何输出
this.inOrderTraverse=function(callback){        
	inOrderTraverseNode(root,callback)   //从根节点开始遍历
}

var callback=function(key){
    console.log(key)
}

//调BinaryTree的中序接口
binaryTree.inOrderTraverse(callback)
“打断点调试”
“打断点调试”

前序遍历

前序遍历（DLR），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

给BinaryTree增加一个前序遍历的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
var preOrderTraverseNode=function(node,callback){
	if(node!==null){
		callback(node.key)
		preOrderTraverseNode(node.left,callback)   //遍历该节点左子树
		preOrderTraverseNode(node.right,callback)  //遍历该节点的右子树
	}
}
this.preOrderTraverse=function(callback){
	preOrderTraverseNode(root,callback)
}

//调BinaryTree的前序接口
binaryTree.preOrderTraverse(callback)
“打断点调试”
“打断点调试”

后序遍历

后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历
左子树，然后遍历右子树，最后访问根结点。

给BinaryTree增加一个后序遍历的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
var postOrderTraverseNode=function(node,callback){
	if (node!==null) {
		postOrderTraverseNode(node.left,callback) //先遍历当前节点的左子树
		postOrderTraverseNode(node.right,callback) //遍历完左子树之后遍历右子树
		callback(node.key)   //遍历完之后输出节点的值
	}
}
this.postOrderTraverse=function(callback){
	postOrderTraverseNode(root,callback)
}

//调BinaryTree的前序接口
binaryTree.postOrderTraverse(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
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
//接口
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
		}
	}
}
this.remove=function(key){
	removeNode(root,key)
}

//调接口
binaryTree.remove(10)    //删除节点10

假如删除的节点含有左右子树的话，就要从被删除节点的右子树中找到最小的子节点，然后将要删除的节点的值换成找到的最小的子节点的值，这样二叉树里面就有
两个相同的节点，这时候就要把最小子节点去掉，做完这些步骤之后二叉树仍然是保持平衡性质的，这时候接口可以改成

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
var 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倍左右
，中序遍历可用于排序，后序遍历可以用在系统文件检索。

最后放上我偶像
最后放上我偶像