《学习JavaScript数据结构与算法》（第8章）（树）

摘要：先序遍历的一种应用是打印一个结构化的文档。方法的实现如下中序遍历中序遍历是一种以上行顺序访问所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作。

（1）二叉树中的节点最多只有两个子节点：一个是左侧节点，另一个是右侧子节点；
（2）只允许在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大（或者等于）的值；

主要包括有插入（insert）、搜索（search）、移除（removce）、遍历（traverse）等功能

var Tree = function() {
    var Node = function(value) {
        this.value = value;
        this.left = null;  //左节点
        this.right = null; //右节点
    }
    var root = null;    //根节点  
    /*
    插入节点：
    1、树为空
    2、树不为空 -> 比较（小于 -> 往左走；大于 -> 往右走）
    */ 
    this.insert = function(value) {};
    //搜索节点(搜索一个特定的值)
    this.search = function(value) {};
    //寻找树的最小键的方法
    this.min = function() {};
    //寻找树的最大键的方法
    this.max = function() {};
    /*
    移除节点：
    1、最简单的情况：移除叶节点
    2、移除只有一个子节点的节点
    3、移除有两个子节点的节点(替换为右侧子树的最小节点)
    */
    this.remove =function(value) {
    };
    //遍历节点
    this.traverse = function(callback) {};
    
    //显示树
    this.getRoot = function() {};
}

var Tree = function() {
    var Node = function(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    var root = null;    //根节点  
    /*
    插入节点：
    1、树为空
    2、树不为空 -> 比较（小于 -> 往左走；大于 -> 往右走）
    */ 
    this.insert = function(value) {
        var newNode = new Node(value);
        if(root == null) { //空树          
            root = newNode;
        }else{//树非空           
            insertNode(root, newNode);
        }
    };
    var insertNode = function(node, newNode) {
        if(newNode.value > node.value) {
            //往右走
            if(node.right == null) {
                node.right = newNode;
            }else{
                insertNode(node.right, newNode);
            }   
        }else if(newNode.value < node.value) {
            //往左走
            if(node.left == null) {
                node.left = newNode;
            }else{
                insertNode(node.left, newNode);
            }
        }
    };


    //搜索节点(搜索一个特定的值)
    this.search = function(value) {
        return searchNode(root, value);
    };
    var searchNode = function(node, value) {
        if(node === null) {
            return false;
        }
        if(value < node.value) {
            return searchNode(node.left, value);
        }else if(value > node.value) {
            return searchNode(node.right, value);
        }else{
            return true;
        }
    };
   //寻找树的最小键的方法
   this.min = function() {
       return minNode(root);
   };
   var minNode = function(node) {
       if(node) {
           while(node && node.left !== null) {
               node = node.left;
           }
           return node.value;
       }
       return null;
   };
   //寻找树的最大键的方法
   this.max = function() {
       return maxNode(root);
   };
   var maxNode = function(node) {
       if(node) {
           while(node && node.right !== null) {
               node = node.right;
           }
           return node.value;
       }
       return null;
   };

    /*
    移除节点：
    1、最简单的情况：移除叶节点
    2、移除只有一个子节点的节点
    3、移除有两个子节点的节点(替换为右侧子树的最小节点)
    */
    this.remove =function(value) {
        root = removeNode(root, value);
    };
    var removeNode = function(node,value) {
        if( node == null) return null;
        if(node.value < value) {
            //继续向右查找
            node.right = removeNode(node.right , value);
            return node;
        }else if(node.value > value) {
            //向左查找
            node.left = removeNode(node.left, value);
            return node;
        }else{
            //value == node.value
            //执行删除过程
            //叶节点条件
            if(node.left == null && node.right == null) {
                node = null;
                return node;
            }
            //只有一个子节点条件
            if(node.left == null && node.right) {
                node = node.right;
                return node;     
            }else if(node.right == null && node.left){
                node = node.left;
                return node;
            }

            //有两个子节点（替换为右侧子树的最小节点）
            var aux = findMinNode(node.right);   //aux是查找到的最小的子节点
            node.value = aux.value;
            node.right = removeNode(node.right, aux.value);
            return node;
        }
    };
    var findMinNode = function(node) {
        if(node == null) return null;
        while(node && node.left) {
            node = node.left;
        }
        return node;
    };


    //遍历节点
    this.traverse = function(callback) {
        traverse(root, callback);
    };
    var traverse = function(node, callback) {
        if(node == null) return;
        //（后续遍历）左右中；（中序遍历）左中右；（前序遍历）中左右
        traverse(node.left, callback);
        traverse(node.right, callback);
        callback(node.value);
    };
    
    //显示树
    this.getRoot = function() {
        return root;
    };
}

var t = new Tree;
var print = function(value) {
    console.log("value -",value)   
};

t.insert(11);
t.insert(8);
t.insert(4);
t.insert(9);
t.insert(3);
t.insert(5);

t.insert(9);
t.insert(12);

t.search(9); //true
t.remove(8);
t.min(); //3
t.max(); //12
t.traverse(print); 

先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。

11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

this.preOrderTraverse = function(callback){
    preOrderTraverseNode(root, callback);
};
preOrderTraverseNode方法的实现如下：
var preOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        callback(node.key); //{1}
        preOrderTraverseNode(node.left, callback); //{2}
        preOrderTraverseNode(node.right, callback); //{3}
    }
};

中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作。

3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

this.inOrderTraverse = function(callback){
    inOrderTraverseNode(root, callback); //{1}
};
var inOrderTraverseNode = function (node, callback) {
    if (node !== null) { //{2}
    inOrderTraverseNode(node.left, callback); //{3}
    callback(node.key); //{4}
    inOrderTraverseNode(node.right, callback); //{5}
    }
};

后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录和它的子目录中所有文件所占空间的大小。

3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

this.postOrderTraverse = function(callback){
    postOrderTraverseNode(root, callback);
};
postOrderTraverseNode方法的实现如下：
var postOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        postOrderTraverseNode(node.left, callback); //{1}
        postOrderTraverseNode(node.right, callback); //{2}
        callback(node.key); //{3}
    }
};