前言

• 紧接前面说过的 二叉树的实现 和 二叉树的遍历，今天来说一下用javascript实现二叉树的查找和节点删除。

• 为了表面写起来读起来很拗口，以下内容中就将“节点值为x的节点”直接省略成“节点x”

• 下面先引入二叉树的实现和遍历，二叉树的实现在此做了一点修改：

// 节点对象
function Node(data, right, left) {
    this.data = data;
    this.left = left;
    this.right = right;
}
// 二叉树对象
function BST() {
    this.root = null;
}
// 插入二叉树
BST.prototype.insert = function(data) {
    var node = new Node(data, null, null);
    if(this.root == null) {
        this.root = node;
    } else {
        var current = this.root;
        while(true) {
            if(data < current.data) {
                if(current.left == null) {
                    current.left = node;
                    break;
                } else {
                    current = current.left;
                }
            } else {
                if(current.right == null) {
                    current.right = node;
                    break;  
                } else {
                    current = current.right;
                }
            }
        }
    }
};
// 中序遍历
BST.prototype.inOrder = function(node, callback) {
    if(node != null) {
        this.inOrder(node.left, callback);
        callback && callback(node.data);
        this.inOrder(node.right, callback);
    }
};
// 先序遍历
BST.prototype.preOrder = function(node, callback) {
    if(node != null) {
        callback && callback(node.data);
        this.preOrder(node.left, callback);
        this.preOrder(node.right, callback);
    }
};
// 后序遍历
BST.prototype.postOrder = function(node, callback) {
    if(node != null) {
        this.postOrder(node.left, callback);
        this.postOrder(node.right, callback);
        callback && callback(node.data);
    }
};

二叉树查找

二叉树的查找课简单地细分成：

• 查找二叉树的最大最小值；
• 给定值在二叉树中进行查找。

查找最大最小值

看过 二叉树的实现 的或者已经有相关数据结构的道友就会了解，实现起来异常简单。最小值就是二叉树最左边的叶子节点，而最大值就是二叉树最左边的叶子节点。

BST.prototype.getMin = function() {
    var current = this.root;
    while(current.left != null) {
        current = current.left;
    }
    return current.data;
};

BST.prototype.getMax = function() {
    var current = this.root;
    while(current.right != null) {
        current = current.right;
    }
    return current.data;
};

异常简单吧！
代码测试一下：

查找给定值

二叉树的一个特点是：左节点值 < 父节点值 < 右节点
这样思路就出来了，分成三种情况：

• 节点值和给定值相当 => 返回该节点；
• 给定值 < 节点值 => 查找当前节点的左节点，用左节点的值和给定值比较；
• 给定值 > 节点值 => 查找当前节点的右节点，用右节点的值和给定值比较；

PS：说白了，就是用给定值从根节点开始往下逐个和每个节点比较，相等就返回，大于就找右边，小于就找左边，直到找到相等的或已经没得找。

BST.prototype.find = function(data) {
    var current = this.root;
    while(current) {
        if(current.data == data) {
            return current;
        } else if(data < current.data) {
            current = current.left;
        } else{
            current = current.right;
        }
    }
    return null;
};

也是异常简单吧！

二叉树节点的删除

二叉树节点的删除也是可以分为几种情况:

• 被删除节点为叶子节点；
• 被删除节点仅有一个子节点（子树）；
• 被删除节点有两个子节点（子树）

被删除节点为叶子节点

思路：将该叶子节点的父节点指向的子节点的引用值设为空

以上图为例子，要删除节点 2

console.log(node.data);  // 3
// 删除节点2
node.letf = null;

被删除节点仅有一个子树

思路：将该节点的父节点指向该节点的引用改成指向该节点的子节点。

以上图为例子，删除节点4。就是将节点3的node.right 改成 node.letf = 节点9

被删除节点有两个子树

思路：处理这种情况有两种方法：

• 从待删除节点的左子树找节点值最大的节点A，替换待删除节点，并删除节点A；
• 从待删除节点的右子树找节点值最小的节点A，替换待删除节点，并删除节点A。

PS：我们这里选择第二种方法。
以下图的二叉树为例，删除节点3。

看到我改了图吧，改一下，让人好点理解嘛，绝不是避开坑专门不说。

三种情况的解决思路都说完，来看看代码的具体实现：

// 获取给定节点下的二叉树最小值
BST.prototype.getSmallest = function(node) {
    if(node.left == null) {
        return node;
    } else {
        return getSmallest(node.left);
    }
};
// 根据给定删除给定节点下二叉树的对应节点
BST.prototype.removeNode = function(node, data) {
    if(node == null) {
        return null;
    }
    if(data == node.data) {
        // 没有子节点（子树）
        if(node.left == null && node.right == null) {
            return null;
        } 
        // 只有右子节点（子树）
        else if(node.left == null ) {
            return node.right;
        } 
        // 只有左子节点（子树）
        else if(node.right == null){
            return node.left;
        } 
        // 有两个子节点（子树）
        else {
            var tempNode = this.getSmallest(node.right);
            node.data = tempNode.data;
            node.right = this.removeNode(node.right, tempNode.data);
            return node;
        }
    } else if(data < node.data) {
        node.left = this.removeNode(node.left, data);
        return node;
    } else {
        node.right = this.removeNode(node.right, data);
        return node;
    }
}

由上面看到这两个方法都是用递归实现的。removeNode 递归实现的巧妙之处在于 return ，比如说 node.right = this.removeNode(node.right, data); 这一句，假设被删除的节点是节点4

else if(node.left == null ) {
  return node.right;
} 

理一下代码，最后的代码是：node.right = node.right.right;，在“不知不觉中”就删除了节点node.right，可以用删除节点4代入一下。node就是节点3，而node.right就是节点4， node.right.right就是节点9。
最后也是代码测试一下：

[传送门：demo]

各位观众老爷，先说到这里，下次再尬blog。