[数据结构与算法]树的一些基础

树

定义
树是n（n>=0)个节点的有限集。n=0时称为空树。在任意一颗非空树中：

1. 有且仅有一个特定的称为根（Root）的节点；
2. 当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1、T2、…、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。
3. n>0时根节点是唯一的，不可能存在多个根节点，数据结构中的树只能有一个根节点。
4. m>0时，子树的个数没有限制，但它们一定是互不相交的。

二叉树

定义
二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树）；或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组成。

• 每个节点最多有两颗子树，所以二叉树中不存在度大于2的节点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某节点只有一棵子树，也要区分它是左子树还是右子树

存储方式
了解一个结构，比较重要的是了解它的存储以及读取。对于树这种一对多的，还是可以用顺序存储，它使用一维数组来存储树的节点，数组的下标可以提现节点之前的父母关系，兄弟关系，即使子树为空数组值也会留空；根据一个数组可以画出一棵树；特别说一下完全二叉树，用顺序存储是最节省内存的方式；

当然它缺点也很明显，特别是斜二叉树浪费空间，常用的是链式存储。每个节点由三个字段组成，其中一个存储数据，另外两个指向左右子节点的指针；知道根节点，就可以知道左右子节点的指针，把整颗树串起来。

遍历

怎么读取二叉树数据呢？不管是数组，链表，栈，点都是前驱与后继的关系，树不同于线性结构，最多从头到尾，循环等访问；它到下一个点有多种选择；所有常用的有前序、中序、后序三种遍历；

• 前序遍历是指，若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树
• 中序遍历是指，若二叉树为空，则空操作返回，否则从根节点开始，中序遍历节点左子树，再访问根节点，最后中序遍历右子树
• 后序遍历是指，若二叉树为空，则空操作返回，否则从左到右先叶子再节点方式遍历左右子树，再访问根节点

 preOrderTraverse(){
 	return this.preOrder(this.root)
 }
 preOrder(node){
     if (node == null) return;
     this.preOrder(node.left) 
     this.preOrder(node.right) 
 }

二叉查找树

• 普通的顺序存储；比如数组，插入数据从最后插入；删除一个数据 跟最后一个值交换 再删掉最后一个值；查找就很难；
• 有序线性表；查找就很简单，但是每次插入一个数据，都需要跟其他值比较，找到位置后还需要移动其他元素，直到顺序排放；
• 而二叉排序数 特性动态插入删除查找

定义
二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值

插入
首先点跟跟节点比较 如果为空则直接插入进去；如果不为空，就比较大小小于则再树左边 大于则在树的右边；同样用递归来比较；

//检查是否有根节点，没有则添加，有则比较大小；大于则在右子树查找合适的点；小于则在右子树查找合适的点插入
insert(val){  
    this.root = this.insertNode(this.root, val)    
}
insertNode(node,val){
    if(node == null){
        return new this.Node(val)
    }  
    if(node.value > val){
        node.left = this.insertNode(node.left, val)
    }
    if(node.value < val){
        node.right = this.insertNode(node.right, val)
    }
    return node;
}

搜索
与跟节点比较，相等则返回；否则大于则与它的右子树比较；小于则与它的左子树比较是否相等

 //与跟节点比较，相等则返回；大于节点则继续与它的右子树比较；小于则与它的左子树比较
 search(val){
     return this.searchNode(this.root,val)
 }
 searchNode(node,val){            
     if(node == null){
         return false;
     }else if(node.value == val){
         return true;
     }else if(node.value > val){
         return this.searchNode(node.left, val)
     }else{
         return this.searchNode(node.right, val)
     } 
 }

删除

1. 查找节点的位置； 找到后看看它有没有子树 没有就直接删除
2. 有一个就直接返回这个节点的子树；有两个那么就比较复杂；比如直接删掉这个点？那么在重新排序它的子树吗？所以最好的方法就是求两个点，中序遍历它的前后两个点，也就是左子树最大值
3. 右子树最小值；这里我用的是右子树最小值，获取这个点之后，将节点的左树给他；它肯定是比左树大，这个是二叉排序树的特点；接着就是把节点的右边数（删掉这个最小值的）给它，这个时候就成功的替换掉了；

//有几种情况；1)删除的点是叶子节点2)删除的点只有一个点3)删除的点有两个点 
 delete(val){
 this.root = this.deleteNode(this.root,val) 
  }  
  deleteNode(node,val){
 if(node == null){
     return node;
 }
 if(node.value > val){
     node.left = this.deleteNode(node.left, val)
     return node
 }
 if(node.value < val){
     node.right = this.deleteNode(node.right, val)
     return node
 }
 //是获得点的位置后
 if(node.left == null && node.right == null){
     node = null;
     return node;
 }
 if(node.left == null){
     node = node.right;
     return node;
 }
 if(node.right == null){
     node = node.left;
     return node;
 }
 // 找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，
 if(node.left !== null && node.right !== null){
     var json = JSON.stringify(this.minNodeValue(node.right))
     const s = JSON.parse(json)      
     s.left = node.left;
     s.right = this.deleteNode(node.right, s.value);
     node = null
     return s; // 返回 s 节点替换掉 node 节点
 }  
}

特点

1. 支持动态数据集合的快速插入、删除、查找操作，插入或删除不需要移动元素；查找比较次数取决于树的高度，时间复杂度其实都跟树的高度成正比，也就是O(height)。
2. 含 n个节点的完全二叉树中，第一层包含1个节点，第二层包含2个节点，第三层包含4个节点，依次类推，下面一层节点个数是上一层的2倍，第K层包含的节点个数就是2^(K-1)，计算出时间复杂度为O(log2n)
3. 两个极端情况的时间复杂度分别是 O(n) 和 O(logn)，分别对应二叉树退化成链表的情况和完全二叉树。
4. 也叫二叉排序树，中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效 。两个极端情况的时间复杂度分别是 O(n)和 O(logn)，分别对应二叉树退化成链表的情况和完全二叉树。

平衡二叉查找树

定义
平衡二叉树是一种特殊的二叉搜索树。平衡二叉树保证节点平衡因子的绝对值不超过1，保证了树的平衡。满足任何节点的两个子树的高度最大差为1
为什么需要平衡
当二叉树退化成链表，搜索效率降至是 O(n)，二叉树的查找效率取决于树的高度，即需要保持树的高度最小，树的节点一定时，保持两端的平衡，效率才会更高。
特点
平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是O(logn)。

参考以及引用：
http://caibaojian.com/js-bst.html
https://time.geekbang.org/column/article/67856
代码参考链接，完整代码可点：https://juejin.cn/post/6844904200644591623
定义引用：《大话数据结构》