二叉树 JS数据结构与算法总结 （第二篇）

JS数据结构与算法总结 （第一篇）

六.树：

6.1 概念

1. 树是一种数据结构，它是由n(n>=0)个有限结点组成一个具有层次关系的集合。若n=0，称为空树。
2. 有如下特点：

每个结点有零个或多个子结点。
没有父结点的结点称为根结点。
每一个非根结点有且只有一个父结点。
除了根结点外，每个子结点可以分为多个不相交的子树。
具有递归的特性，（任何一颗子树又满足树的概念）。
树形结构种的数据元素之间存在的关系的是一对多, 或者是多对一的关系。

3. 树的相关术语：
   （1）结点的度：一个结点含有的子树的个数称为该结点的度。
   （2）树的度：一棵树中，最大的结点的度称为树的度；
   （3）叶结点或终端结点：度为0的结点称为叶结点；
   （4）分支结或非终端结点：就是度不为0的结点。父节点称为开始结点，其它称为内部节点。
   （5）孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点。
   （6）双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点。
   （7）兄弟结点：具有相同父结点的结点互称为兄弟结点。
   （8）子孙：以某结点为根的子树中任一结点都称为该结点的子孙。
   （9）结点的祖先：从根到该结点所经分支上的所有结点。
   （10）路径：这个结点自上而下的通过每条路径上的每条边。
   （11）结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。
   （12）树的高度或深度：树中结点的最大层次。
   （13）森林：由棵互不相交的树的集合称为森林。

6.2 树的存储结构

计算机只能是顺序或者是链式的存储，所以树这样的结构是不能够直接存储的，要将其转换为顺序或者是链式存储。

1. 双亲表示法: 采用数组存储普通的树，就是顺序存储每个结点的同时，给各个结点添加一个记录其父结点位置的变量，其实就是父节点的下标。

2. 孩子表示法：给各个结点配备一个链表，用于存储各结点的孩子结点位于数组中的位置（也是下标），如果说，结点没有子结点(叶子结点)，则该结点的链表为空链表。

3. 孩子兄弟表示法：从树的根节点开始，依次用链表存储各个节点的孩子节点和兄弟节点。
链表结点包括三部分内容：

[孩子指针域][数据][兄弟指针域]

6.3 二叉树

官方解释为：

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

二叉树（binarytree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。

左子树和右子树是有顺序的，次序不能任意的颠倒的。所以，即使树中某个结点只有一棵子树，也要去区分它是左子树还是右子树。还有，在二叉树中，第 i 层上最多有 2^（i-1） 个结点 (i>=1) 。如果深度为k，则总共最多有2^k-1个结点。

五种形态：

1、空二叉树——如图（a）；
2、只有一个根结点的二叉树——如图（b） ；
3、只有左子树——如图（c） ；
4、只有右子树——如图（d） ；
5、左右子树都有——如图（e） 。

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。满二叉树一定是完全二叉树，反过来不一定成立。

6.4 二叉搜索树

                   图 6.4
官方解释为：

 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

6.5 js实现二叉搜索树基本结构

//一个结点的结构
class Node{
    constructor(value){
        //值
        this.value = value;
        // 保存左子树，就是比当前小的值
        this.left = null;
        //保存右子树，就是比当前大的值
        this.right = null;
    }
}
//二叉搜索树的结构
class BinarySearchTree{
    constructor(){
        //有个根节点
        this.root = null;
    }
    //对于插入的新结点（值）的走向方法,就是新结点从根结点开始向下一一比较
    insertNode(node,newNode){
        //如果新结点更大，往右走
        if(newNode.value>node.value){
            //往右走后发现没数据了
            if(node.right === null){
               node.right = newNode;
            }else{
                //往右走后还有结点，“当前结点更新为该结点”，递归重新判断大小后走
                this.insertNode(node.right,newNode);
            }
        //如果新结点更小，往左走   
        }else if(newNode.value<node.value){
            //往左走后发现没数据了
            if(node.left === null){
                node.left = newNode;
             }else{
                 //往左走后还有结点，“当前结点更新为该结点”，递归重新判断大小后走
                 this.insertNode(node.left,newNode);
             }                    
        }      
    }
    //插入新结点
    insert(value){
        //用结点保存数据
        let newNode = new Node(value);
        // 如果空树该结点为根结点
        if(this.root === null){
            this.root = newNode;
        }else{
            //则走insertNode(node,newNode)方法，判断该结点往哪里走,新结点从根结点开始向下一一比较
            this.insertNode(this.root,newNode);
        }
    }
}

测试一下（就上面那个6.4的图的数据,后面代码都用这个图做例子）：

const tree = new BinarySearchTree();
tree.insert(8);
tree.insert(3);
tree.insert(10);
tree.insert(1);
tree.insert(6);
tree.insert(14);
tree.insert(4);
tree.insert(7);
tree.insert(13);
console.log(tree);

结果：

6.6 遍历

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

6.6.1 先序遍历

先序遍历(Pre-order)，按照根左右的顺序沿一定路径经过路径上所有的结点。在二叉树中，先根后左再右。巧记：根左右。

特点：
⑴ 访问根结点；
⑵ 先遍历左子树；
⑶ 再遍历右子树。

 就这种感觉，对于进入到当前的某个结点时，它都会执行遍历左子树和遍历右子树。若它遍历左子树那个结点时，当前结点更新为左子树那个结点，而当前结点又会遍历左子树和遍历右子树，在当前结点左子树和右子树都都没时（相当叶子了），会返回其父节点遍历没遍历过的子树，父结点也都遍历完时，又再向上返回。

结果应为 8-3-1-6-4-7-10-14-13

6.6.1.1 js实现先序遍历：

在6.5的基础上添加一个先序遍历方法：

// 添加先序遍历方法
    //开始从根节点开始遍历，cb相当于获取每一个结点的数据的函数，后面打印出来
    preOrderTraverasl(cb){
        this.proOrderTraveraslNode(this.root,cb);
    }
    // 通过递归实现遍历
    proOrderTraveraslNode(node,cb){
        // 若没结点，空结点，直接返回
        if(node===null) return;
        // cb添加一个结点数据
        cb(node.value);
        // 遍历左子树，同样采用递归，就想象成当前结点的更新又要重新遍历左右子树
        this.proOrderTraveraslNode(node.left,cb);
        // 遍历右子树，同样采用递归，就想象成当前结点的更新又要重新遍历左右子树
        this.proOrderTraveraslNode(node.right,cb);
    }

测试下：

const tree = new BinarySearchTree();
tree.insert(8);
tree.insert(3);
tree.insert(10);
tree.insert(1);
tree.insert(6);
tree.insert(14);
tree.insert(4);
tree.insert(7);
tree.insert(13);
/* console.log(tree); */

const rst = [];
const cb = function(val){
    rst.push(val);
}
tree.preOrderTraverasl(cb);
console.log(rst);

结果没毛病：

6.2 中序遍历

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

特点：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树

有个巧妙的方法就是二叉树的中序遍历就是将节点投影到一条水平的坐标上。如下：

这个图的中序遍历结果就是5-10-6-15-2

6.2.1 js实现中序遍历

同样在6.5基础上添加一个中序遍历：

 // 添加中序遍历方法
    //开始从根节点开始遍历，cb相当于获取每一个结点的数据的函数，后面打印出来
    inOrderTraverasl(cb){
        this.inOrderTraveraslNode(this.root,cb);
    }
    // 通过递归实现遍历
    inOrderTraveraslNode(node,cb){
        // 若没结点，空结点，直接返回
        if(node===null) return;
         // 遍历左子树
         this.inOrderTraveraslNode(node.left,cb);
        // cb添加一个结点数据
        cb(node.value);
        // 遍历右子树
        this.inOrderTraveraslNode(node.right,cb);
    }

测试：

const tree = new BinarySearchTree();
tree.insert(8);
tree.insert(3);
tree.insert(10);
tree.insert(1);
tree.insert(6);
tree.insert(14);
tree.insert(4);
tree.insert(7);
tree.insert(13);
/* console.log(tree); */

const rst = [];
const cb = function(val){
    rst.push(val);
}
/* tree.preOrderTraverasl(cb); */
tree.inOrderTraverasl(cb);
console.log(rst);

结果：

6.3 后序遍历：

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

特点：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点

6.3.1 js实现后序遍历

同样在6.5基础上添加一个后序遍历：

// 添加后序遍历方法
    //开始从根节点开始遍历
    postOrderTraverasl(cb){
        this.postOrderTraveraslNode(this.root,cb);
    }
    // 通过递归实现遍历
    postOrderTraveraslNode(node,cb){
        // 若没结点，空结点，直接返回
        if(node===null) return;
         // 遍历左子树
         this.postOrderTraveraslNode(node.left,cb);
        // 遍历右子树
        this.postOrderTraveraslNode(node.right,cb);
         // cb添加一个结点数据
         cb(node.value);
    }

同样测试下，结果为：

const rst = [];
const cb = function(val){
    rst.push(val);
}
 tree.postOrderTraverasl(cb); 
console.log(rst);

6.7 完善6.5js实现二叉搜索树的基本结构

6.7.1 添加输出最大值的方法：

//输出最大值
     max(){
         let node = this.root;
         //按照二叉搜索树特性，一直往右走
         while(node.right !== null){
             node = node.right;
         }
         return node.value;
     }

测试下：

console.log(tree.max());

6.7.2 添加输出最小值方法

 //输出最小值
      max(){
        let node = this.root;
        //按照二叉搜索树特性，一直往左走
        while(node.left != null){
            node = node.left;
        }
        return node.value;
    }

测试：

console.log(tree.min());

6.7.3 查找看是否有特定的值

//参数为要寻找的值
    search(val){
        let node = this.root;
        while(node != null){
            if(node.value > val){
                node = node.left;
            }else if(node.value < val){
                node = node.right;
            }else {
                //就是node.value == val 时，返回true,没有的话会undefined
                return true;
            }
        }
    }

测试下，给一个 13 和一个 不存在的 5 看看：

console.log(tree.search(13));
console.log(tree.search(5));

6.8 二叉搜索树删除结点

6.8.1 结点没有子树

直接删除结点就可，对树结构影响不大。

6.8.1 结点有一个子树

对于只有一个子树的情况，考虑将其子树作为其父结点的子树，当然要根据被删除的结点确定是放左子树还是右子树。

6.8.1 结点有两个子树

网上这么解释：

用被删除节点A的左子树的最右节点或者A的右子树的最左节点作为替代A的节点，并修改相应的最左或最右节点的父节点的指针。

6.9 二叉搜索树总结

二叉搜索树的优点:作为数据存储的结构有重要的意义,可以快速的找到给定的关键字的数据项,并且可以快速的插入和删除数据。

二叉搜索树的缺点:具有局限性。同样的数据，可以对应不同的二叉搜索树。比较好的二叉搜索树的结构是左右分布均匀的。但是在我们插入连续的数据的时候，也会有导致数据分布不均匀的二叉搜索树。我们就把这个分布不均匀的树叫做非平衡树。如下：它其实就是一个链表，甚至比链表查询速度还要慢。所以这就很不好。

6.10 二叉平衡树*

概念: 也叫平衡二叉搜索树，也叫做AVL树， 是一种自平衡的树。除了规定左结点小于根结点，右结点大于根结点以外，还规定了左子树和右子树的高度差不得超过1。

平衡因子:每个结点的左子树的高度减去其右子树的高度。
平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。
如果绝对值超过1，就是失衡了。

可以通过旋转来操作来达到平衡，有以下几种旋转：

6.11 红黑树*

官方概念：

   红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
    红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
   红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
   它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

有如下特征：

1. 结点是红色或者黑色。（结点上有一个color的属性）。
2. 根结点是黑色。
3. 叶子结点都是黑色，都为null。（也叫NIL结点，为配合红黑树特性假想出来的结点）。
4. 连接红色结点的两个子结点都是黑色，就是说红色结点的父结点都是黑色，红色结点的子结点也是黑色。
5. 从任一节结点出发到每个叶子的路径都包含相同数目的黑色结点。

以上的5个特性就是红黑树能自动维持平衡的的准则。

这都是为了保证从根节点到叶子结点的最长路径不大于最短路径的2倍。

当插入和删除结点时，就会导致红黑树的平衡被破坏，这个时候就需要对红黑树进行调整,从而使他符合5个特性,以此保证红黑树的平衡。

红黑树的平衡调整有两种方式: 变色，旋转(左旋转和右旋转)。

未完结，第三篇更新中~