二叉树

Veröffentlicht am

什么是二叉树？

在计算机的世界里面，二叉树时每个节点最多有两个子数的树结构，通常分之被称作“左子数”和“右子数”。二叉树的分支具有左右次序，不能颠倒。

二叉树的第i层最多拥有2^(i-1)个节点数，深度为k的二叉树最多总共有2^(k+1)-1个节点数，而总计拥有的节点数匹配的称为“满二叉树”；深度为k有n个节点的二叉树，当且仅当其中的每一个节点，都可以和同样深度k的满二叉树，序号为1到n的节点一对一对应时，成为“完美二叉树”。

二叉树通常作为数据结构应用，典型用法是对节点定义一个标记函数，将一些值与每一个节点相关系。这样标记的二叉树就可以实现二叉查找树和二元堆积，并应用于搜索和排序。

二叉查找树

也称为二叉搜索树，是指对一个空树，或者具有下列性质的二叉树：
1.若任意节点的左子树不空，则左子树上的所有节点的值均小于他根节点的值；
2.若任一节点的右字数不空，则右子树上的所有节点的值均大于他根节点的值；
3.任意节点的左、右子树叶分别为二叉查找树
4.没有键值相等的节点

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。

###二叉查找树和js
二叉树的一个节点Node由data、left、right组成，data报错本节点的值，left指向左节点，right指向右节点。如何使用JS构建一个二叉查找树呢？

创建一个Node实例来试试看吧

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
function Node(data,left,right){
	this.data = data//创建data
	this.left = left//创建左节点
	this.right = right//创建右节点
}
fuction BST(){
	this.root = null
	this.insert = insert
}
fuction insert(data){
	var node = new Node(data,null,null)
	if(this.root == null){
		this.root = node
	}else{
		var current = this.root
		while(true){
			if(current.data > data){
				if(current.left === null){
					current.left = node
					break
				}
				current = current.left
			}else{
				if(current.right === null){
					current.right = node
					break
				}
				current = current.right
			}
		}
	}
}
var bst = new BST()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(2)
}