接下来让咱们一起来讨论js数据结构中的树。这儿的树类比现实生活中的树，有树干，树枝，在程序中树是一种数据结构，关于存储需求快速查找的数据非有用，它是一种分层数据的笼统模型。一个树结构包括一系列存在父子联系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所认为一个树结构：)

• 和树相关的概念：1.子树：由节点和他的子孙构成，如上图标明处。2.深度：节点的深度取决于它祖节点的数量，比方节点5有2个祖节点，他的深度为2。3.高度：树的高度取决于一切节点深度的最大值。

二叉树和二叉查找树介绍

二叉树中的节点最多只能有2个子节点，一个是左边子节点，一个是右侧子节点，这样界说的优点是有利于咱们写出更高效的刺进，查找，删去节点的算法。二叉查找树是二叉树的一种，可是它只允许你在左边子节点存储比父节点小的值，但在右侧节点存储比父节点大的值。接下来咱们将依照这个思路去完成一个二叉查找树。

1. 创立BinarySearchTree类

这儿咱们将运用结构函数去创立一个类：

functionBinarySearchTree(){
//用于创立节点的类
letNode=function(key){
this.key=key;
this.left=null;
this.right=null;
}
//根节点
letroot=null;
}

咱们将运用和链表相似的指针办法去表明节点之间的联系，假如不了解链表，请看我后序的文章《怎么完成单向链表和双向链表》。

2.刺进一个键

//刺进一个键
this.insert=function(key){
letnewNode=newNode(key);
root===null?(root=newNode):(insertNode(root,newNode))
}

向树中刺进一个新的节点主要有以下三部分：1.创立新节点的Node类实例 --> 2.判别刺进操作是否为根节点,是根节点就将其指向根节点 --> 3.将节点参加非根节点的其他方位。

insertNode的详细完成如下：

functioninsertNode(node,newNode){
if(newNode.key<node.key){
node.left===null?(node.left=newNode):(insertNode(node.left,newNode))
}else{
node.right===null?(node.right=newNode):(insertNode(node.right,newNode))
}
}

这儿咱们用到递归，接下来要完成的search，del等都会很多运用递归，所以说不了解的能够先自行学习了解。咱们创立一个二叉树实例，来刺进一个键：

lettree=newBinarySearchTree();
tree.insert(20);
tree.insert(21);
tree.insert(520);
tree.insert(521);

刺进的结构会依照二叉查找树的规矩去刺进，结构相似于上文的第一个树图。

树的遍历

拜访树的一切节点有三种遍历办法：中序，先序和后序。

• 中序遍历：以从最小到最大的次序拜访一切节点
• 先序遍历：以优先于子孙节点的次序拜访每个节点
• 后序遍历：先拜访节点的子孙节点再拜访节点自身

依据以上的介绍，咱们能够有以下的完成代码。

1 中序排序

this.inOrderTraverse=function(cb){
inOrderTraverseNode(root,cb);
}
//辅佐函数
functioninOrderTraverseNode(node,cb){
if(node!==null){
inOrderTraverseNode(node.left,cb);
cb(node.key);
inOrderTraverseNode(node.right,cb);
}
}

运用中序遍历能够完成对树进行从小到大排序的功用。

2 先序排序

//先序排序---优先于子孙节点的次序拜访每个节点
this.preOrderTraverse=function(cb){
preOrderTraverseNode(root,cb);
}
//先序排序辅佐办法
functionpreOrderTraverseNode(node,cb){
if(node!==null){
cb(node.key);
preOrderTraverseNode(node.left,cb);
preOrderTraverseNode(node.right,cb);
}
}

运用先序排序能够完成结构化输出的功用。

3 后序排序

//后续遍历---先拜访子孙节点，再拜访节点自身
this.postOrderTraverse=function(cb){
postOrderTraverseNode(root,cb);
}
//后续遍历辅佐办法
functionpostOrderTraverseNode(node,cb){
if(node!==null){
postOrderTraverseNode(node.left,cb);
postOrderTraverseNode(node.right,cb);
cb(node.key);
}
}

后序遍历能够用于核算有层级联系的一切元素的巨细。

查找树中的值

在树中有三种常常履行的查找类型：最大值，最小值，特定的值。

1 最小值

最小值经过界说能够知道便是左边树的最底端的节点，详细完成代码如下：

//最小值
this.min=function(){
returnminNode(root)
}
functionminNode(node){
if(node){
while(node&&node.left!==null){
node=node.left;
}
returnnode.key
}
returnnull
}

相似的，完成最大值的办法如下：

//最大值
this.max=function(){
returnmaxNode(root)
}
functionmaxNode(node){
if(node){
while(node&&node.right!==null){
node=node.right;
}
returnnode.key
}
returnnull
}

2.查找一个特定的值

//查找树中某个值
this.search=function(key){
returnsearchNode(root,key)
}
//查找辅佐办法
functionsearchNode(node,key){
if(node===null){
returnfalse
}
if(key<node.key){
returnsearchNode(node.left,key)
}elseif(key>node.key){
returnsearchNode(node.right,key)
}else{
returntrue
}
}

3 移除一个节点

//刺进一个键
this.insert=function(key){
letnewNode=newNode(key);
root===null?(root=newNode):(insertNode(root,newNode))
}
0

删去节点需求考虑的状况比较多，这儿咱们会运用和min相似的完成去写一个发现最小节点的函数，当要删去的节点有两个子节点时，咱们要将当时要删去的节点替换为子节点中最大的一个节点的值，然后将这个子节点删去。

至此，一个二叉查找树现已完成，可是还存在一个问题，假如树的一遍十分深，将会存在必定的功能问题，为了处理这个问题，咱们能够使用AVL树，一种自平衡二叉树，也就是说任何一个节点的左右两边子树的高度之差最多为1。