《剑指offer》— JavaScript（4）重建二叉树

重建二叉树

题目描述

　　输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

实现代码

function reConstructBinaryTree(pre, vin)
{
    if(!pre || pre.length===0){
        return;
    }
    
    var root={
        val:pre[0]
    };
    
    for(var i=0;i<pre.length;i++){
        if(vin[i]==pre[0]){
            var leftpre=pre.slice(1,i+1),//左子树的前序遍历结果
                leftvin=vin.slice(0,i),  //左子数的中序遍历结果
                rightpre=pre.slice(i+1),
                rightvin=vin.slice(i+1);
            root.left= reConstructBinaryTree(leftpre,vin.leftvin);
            root.right= reConstructBinaryTree(rightpre,rightvin);
        }
    }
    
    return root;
}

思路

　　先序遍历第一个位置是根节点treeNode，找到中序遍历的根节点位置在中间i；

那么中序遍历i的左侧就是子树的中序数组，右侧是右子树的中序数组

先序遍历的第二个起的i个数是左子数的先序数组，右侧是右字数的先序数组

使用递归算法重建二叉树

注意停止递归的条件；

//二叉搜索树是一种特殊的二叉树， 相对较小的值保存在左节点中， 较大的值保存在右节点中
// 这一特性查找的效率很高，包括数值和非数值的数据
function BinarySearchTree() {
    var Node = function(key){
        this.key=key;
        this.left=null;
        this.right=null;
    }

    var root=null;

    var insertNode=function(node,newNode){
          if (node.key>newNode.key) {
               if (!node.left) {
                     node.left = newNode;
               }else{
                     insertNode(node.left,newNode)
               }
          }else{
                if (!node.right) {
                     node.right = newNode;
               }else{
                     insertNode(node.right,newNode)
               }
          }
    }

    this.insert=function(key){
        var newNode=new Node(key);
        if (!root) {
            root=newNode;
        }else{
            insertNode(root,newNode)
        }
    }
/*有三种遍历 BST 的方式： 中序、 先序和后序。

中序遍历：是一种从小到大访问二叉搜索树BST的遍历方式
应用：对树进行排序操作
给binary search tree 添加一个inorder traverse方法，这个方法接受一个callback参数
回调函数定义了我们对访问到的节点的操作 比如打印
在函数体内调用inorder traverse Node 方法，这是一个递归函数：在函数内部调用自身，有两个参数，
一个是节点，还有一个回调函数
首先检查以参数传入的节点是不是null,这是停止递归的判断条件
然后递归调用相同的函数访问左子点，接着对这个节点进行callback操作，然后再访问右侧节点*/

    var inorderTraverseNode=function(node,callback){
         if (node != null) {
             inorderTraverseNode(node.left,callback);
             callback(node.value);
             inorderTraverseNode(node.right,callback);
         }
    }


    this.inorderTraverse=function(callback){
        inorderTraverseNode(root,callback)
    }
/*
先序遍历：以优先于后代节点的顺序访问每个节点
和中序遍历不同的是先访问节点本身然后访问左子点
应用：打印结构化的文档*/

   
    var preorderTraverseNode=function(node,callback){
         if (node != null) {
             callback(node.value);
             preorderTraverseNode(node.left,callback);
             preorderTraverseNode(node.right,callback);
         }
    }

    this.preorderTraverse=function(callback){
        preorderTraverseNode(root,callback)
    }
/*后序遍历是先访问节点后代子点，然后再访问节点本身
应用：计算一个目录 和他的子目录中 所有文件所占空间的大小*/
    
    var postorderTraverseNode=function(node,callback){
         if (node != null) {
             postorderTraverseNode(node.left,callback);
             postorderTraverseNode(node.right,callback);
             callback(node.value);
         }
    }

    this.postorderTraverse=function(callback){
        postorderTraverseNode(root,callback)
    }
/*搜索树中的值
搜索最小值：在最左端
方法：沿着树的左端进行遍历，直到找到最左端的节点
*/
    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);
    }

/*搜索最大值：在最左端
方法：沿着树的右端进行遍历，直到找到最右端的节点*/
    
    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);
    }

/*搜索特定值*/
    
    var findNode=function(node,key){
       if (!node) {
            return false;
       }
       if (node.key < key) {
             findNode(node.left,key);
       }else if (node.key > key) {
             findNode(node.right,key);
       }else{
             return true;
       }
    } 


   this.find=function(key){
        findNode(root,key);
   }

}

var tree = new binarySearchTree();

tree.inorderTraverse(printNode);
function printNode(value){
    console.log(value)
}

BST有一个问题，就是添加的节点数如果让输的一边非常深的话，这时候在树上添加删除搜索某个节点的时候性能会比较差。为了解决这个问题，提出了平衡二叉树

平衡二叉树：任何一个节点左右两侧字树的高度差不大于一，平衡二叉树主要优点集中在快速查找。

AVL树的查找平均时间复杂度要比二叉搜索树低——它是O(logN)，也就是说，在大量的随机数据中AVL树的表现要好得多

要将不平衡的二叉搜索树转换为平衡的AVL树需要对树进行一次或多次旋转，旋转方式分为左单旋、右单旋、左-右双旋、右-左双旋。

第一种情况是插入发生在“外边”的情况（即该结点的左儿子的左子树进行了一次插入的情况或即该结点的右儿子的右子树进行了一次插入的情况的情况）该情况可以通过对树的一次单旋转来完成调整。

第二种情况是插入发生在“内部”的情况（即左-右的情况或右-左的情况），该情况要通过稍微复杂些的双旋转来处理。