树

树的相关术语

位于树顶部的节点叫做根节点。他没有父节点。树中的每个元素都叫做节点，节点分为内部节点和外部节点。至少有一个子节点的节点称为内部节点。没有子元素的节点称为外部节点或叶节点。子树由节点和它的后代构成。节点的一个属性是深度，节点的深度取决于它的祖先节点的数量。比如节点有3个祖先节点，它的深度为3。树的高度取决于所有节点深度的最大值。

二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。

二叉搜索树（BST）是二叉树的一种，但是它只允许你在左侧节点存储(比父节点)小的值，在右侧节点存储(比父节点)大或相等的值。

创建BinarySearchTree类

function BinarySearchTree(){
    let Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    };
    let root = null;
}

和链表一样，将通过指针来表示节点之间的关系（术语称其为边）。因此声明一个Node类表示树中的每个节点。

键是树相关的术语中对节点的称呼。

向树中插入一个键

//向树中插入一个键
this.insert = function(key){
    var newNode = new Node(key);
    if(root === null){
        root = newNode;
    } else {
        insertNode(root,newNode);
    }
};

第一步创建用来表示新节点的Node类实例。只需要向构造函数传递我们想用来插入树的节点值，它的左指针和右指针的值会由构造函数自动设置为null。

第二步验证这个插入操作是否是插入根节点。

第三步是将节点加在非根节点的其他位置。需要一个私有的辅助函数：

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

树的遍历

中序遍历

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

this.inOrderTraverse = function(callback) {
    inOrderTraverseNode(root, callback);
};

inOrderTraverse方法接收一个回调函数作为参数。回调函数用来定义我们对遍历到的每个节点进行的操作（这也叫访问者模式）。由于我们在BST中最常实现算法是递归，这里使用了一个私有的辅助函数，来接收一个节点和对应的回调函数作为参数。

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

要通过中序遍历的方法遍历一棵树，首先要检查以参数形式传入的节点是否为null。然后递归调用相同的函数来访问左侧子节点。接着对这个节点进行一些操作(callback)，然后再访问右侧子节点。

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

先序遍历

先序遍历是以优先于后代节点的顺序访问每个节点的。

this.preOrderTraverse = function(callback){
    preOrderTraverseNode(root, callback);
};

preOrderTraverseNode方法的实现如下：

var preOrderTraverseNode = fucntion(node, callback) {
    if(node !== null){
        callback(node.key);
        preOrderTraverseNode(node.left, callback);
        preOrderTraverseNode(node.right, callback);
    }
};

先序遍历和中序遍历的不同点是，先序遍历会先访问节点本身，然后再访问他的左侧子节点，最后是右侧子节点；中序遍历是←本→。

后序遍历

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

this.postOrderTraverse = function(callback){
    postOrderTraverseNode(root, callback);
};

postOrderTraverseNode实现方法如下：

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

后序遍历会先访问左侧子节点，然后是右侧子节点，最后是父节点本身。

搜索树中的值

搜索最小值和最大值

//最小值
this.min = function(){
    return minNode(root);
};
var minNode = function(node){
    if(node) {
        while(node && node.left !== null){
            node = node.left;
        }
        return node.key;
    }
    return null;
};

minNode允许我们从树中任意一个节点开始寻找最小的键。我们可以使用它来找到一棵树或它的子树中最小的键。因此，我们在调用minNode方法的时候传入树的根节点，因为我们想要找到整棵树的最小键。

//最大键
this.max = function() {
    return maxNode(root);
};
var maxNode = function(node) {
    if(node) {
        while(node && node.right !== null) {
            node = node.right;
        }
        return node.key;
    }
    return null;
};

搜索一个特定的值

this.search = function(key) {
    return searchNode(root, key);
}
var searchNode = function(node, key) {
    if(node === null) {
        return false;
    }
    if(key < node.key) {
        return searchNode(node.left, key);
    } else if(key>node.key) {
        return searchNode(node.right,key);
    }else {
        return t
    }
}

移除一个节点

先创建这个方法使它能够在树的实例上被调用：

this.remove = function(key) {root = removeNode(root, key)};
var removeNode = function(node, key) {
    //如果正在检测的节点是null，那么说明键不存在于树中，所以返回null。
    if(node === null) {
        return null;
    }
    if(key < node.key) {
        node.left = removeNode(node.left, key);
        return node;
    } else if (key > node.key) {
        node.right = removeNode(node.right, key);
        return node;
    } else {   //键等于node.key
        //第一种情况--一个叶节点
        if(node.left === null && node.right === null) {
            node = null;
            //通过返回null来将对应的父节点指针赋予null值。
            return node;
        }
        //第二种情况--一个只有一个子节点的节点
        //需要跳过这个节点，直接将父节点指向它的指针指向子节点。
        if(node.left === null){
            node = node.right;
            return node;
        } else if(node.right === null) {
            node = node.left;
            return node;
        }
        //第三种情况--一个有两个子节点的节点
        var aux = findMinNode(node.right);
        node.key = aux.key;
        node.right = removeNode(node.right, aux.key);
        return node;
    }
};
//findMinNode方法如下：
var findMinNode = function(node) {
    while (node && node.left !== null) {
        node = node.left;
    }
    return node;
};

要移除有两个子节点的节点，需要执行4个步骤：

当找到了需要移除的节点后，需要找到它右边子树中最小的节点(它的继承者)。
然后用它右侧子树中最小节点的键去更新这个节点的值。通过这一步，我们改变了这个节点的键，也就是说他被移除了。
但是，这样在树中就有两个相同键的节点了，这是不行的。要继续把右侧子树中的最小节点移除，毕竟它已经被移至要移除的节点位置了。
最后向它的父节点返回更新后节点的引用。

前端知识大全

树

树