二叉搜索树 #30

wl05 · 2019-05-28T10:07:17Z

实现一个简单的二叉搜索树(BST)

代码实现

首先创建一个类来表示二叉查找树，它的内部应该有一个Node类，用来创建节点

function BinarySearchTree () {
    var Node = function(key) {
        this.key = key,
        this.left = null,
        this.right = null
    }
    var root = null
}

它还应该有一些方法：

insert(key) 插入一个新的键
inOrderTraverse() 对树进行中序遍历，并打印结果
preOrderTraverse() 对树进行先序遍历，并打印结果
postOrderTraverse() 对树进行后序遍历，并打印结果
search(key) 查找树中的键，如果存在返回true,不存在返回fasle
findMin() 返回树中的最小值
findMax() 返回树中的最大值
remove(key) 删除树中的某个键

1. 向树中插入一个键

向树中插入一个新的键，首页应该创建一个用来表示新节点的Node类实例，因此需要new一下Node类并传入需要插入的key值，它会自动初始化为左右节点为null的一个新节点

然后，需要做一些判断，先判断树是否为空，若为空，新插入的节点就作为根节点，如不为空，调用一个辅助方法insertNode()方法，将根节点和新节点传入

this.insert = function(key) {
    var newNode = new Node(key)
    if(root === null) {
        root = newNode
    } else {
        insertNode(root, newNode)
    }
}

定义一下insertNode() 方法，这个方法会通过递归得调用自身，来找到新添加节点的合适位置

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)
        }
    }
}

2. 完成中序遍历方法

要实现中序遍历，我们需要一个inOrderTraverseNode(node)方法，它可以递归调用自身来遍历每个节点

this.inOrderTraverse = function() {
    inOrderTraverseNode(root)
}

这个方法会打印每个节点的key值，它需要一个递归终止条件————检查传入的node是否为null，如果不为空，就继续递归调用自身检查node的left、right节点实现起来也很简单:

var inOrderTraverseNode = function(node) {
    if (node !== null) {
        inOrderTraverseNode(node.left)
        console.log(node.key)
        inOrderTraverseNode(node.right)
    }
}

3. 先序遍历、后序遍历

有了中序遍历的方法，只需要稍作改动，就可以实现先序遍历和后序遍历了上代码：
这样就可以对整棵树进行中序遍历了

// 实现先序遍历
this.preOrderTraverse = function() {
    preOrderTraverseNode(root)
}
var preOrderTraverseNode = function(node) {
    if (node !== null) {
        console.log(node.key)
        preOrderTraverseNode(node.left)
        preOrderTraverseNode(node.right)
    }
}

// 实现后序遍历
this.postOrderTraverse = function() {
    postOrderTraverseNode(root)
}
var postOrderTraverseNode = function(node) {
    if (node !== null) {
        postOrderTraverseNode(node.left)
        postOrderTraverseNode(node.right)
        console.log(node.key)
    }
}

发现了吧，其实就是内部语句更换了前后位置，这也刚好符合三种遍历规则：先序遍历（根-左-右）、中序遍历（左-根-右）、中序遍历（左-右-根）

既然已经完成了添加新节点和遍历的方式，我们来测试一下吧：

定义一个数组，里面有一些元素

var arr = [9,6,3,8,12,15]
我们将arr中的每个元素依此插入到二叉搜索树中，然后打印结果

var tree = new BinarySearchTree()
arr.map(item => {
    tree.insert(item)
})
tree.inOrderTraverse()
tree.preOrderTraverse()
tree.postOrderTraverse()

输出结果

中序遍历：3 6 8 9 12 15

先序遍历：9 6 3 8 12 15

后序遍历：3 8 6 15 12 9

很明显，结果是符合预期的，所以，我们用上面的JavaScript代码，实现了对树的节点插入，和三种遍历方法，同时，很明显可以看到，在二叉查找树树种，最左侧的节点的值是最小的，而最右侧的节点的值是最大的，所以二叉查找树可以很方便的拿到其中的最大值和最小值

4. 查找最小、最大值

怎么做呢？其实只需要将根节点传入minNode/或maxNode方法，然后通过循环判断node为左侧(minNode)/右侧(maxNode)的节点为null

实现代码：

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

// 查找最大值
this.findMax = function() {
    return maxNode(root)
}
var maxNode = function (node) {
    if(node) {
        while (node && node.right !== null) {
            node =node.right
        }
        return node.key
    }
    return null
}

5. 搜索特定值

this.search = function(key) {
    return searchNode(root, key)
}

同样，实现它需要定义一个辅助方法,这个方法首先会检验node的合法性，如果为null，直接退出，并返回fasle。如果传入的key比当前传入node的key值小，它会继续递归查找node的左侧节点，反之，查找右侧节点。如果找到相等节点，直接退出，并返回true

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 true
    }
}

6. 移除节点

移除节点的实现情况比较复杂，它会有三种不同的情况：

需要移除的节点是一个叶子节点
需要移除的节点包含一个子节点
需要移除的节点包含两个子节点

和实现搜索指定节点一样，要移除某个节点，必须先找到它所在的位置，因此移除方法的实现中部分代码和上面相同：

// 移除节点
this.remove = function(key) {
    removeNode(root,key)
}
var removeNode = function(node, key) {
    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{
        //需要移除的节点是一个叶子节点
        if (node.left === null && node.right === null) {
            node = null
            return node
        }
        //需要移除的节点包含一个子节点
        if (node.letf === 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, axu.key)
        return node
    }
}

var findMinNode = function(node) {
    if (node) {
        while (node && node.left !== null) {
            node = node.left
        }
        return node
    }
    return null
}

其中，移除包含两个子节点的节点是最复杂的情况，它包含左侧节点和右侧节点，对它进行移除主要需要三个步骤：

找到它的右侧子树中的最小节点的值，并将该值赋值给它。
将它右侧子树中的最小节点移除。
将更新后的节点的引用赋值给它的右子树。

有点绕儿，但必须这样，因为删除元素后的二叉搜索树必须保持它的排序性质。

测试：

tree.remove(8)
tree.inOrderTraverse()

打印结果：3 6 9 12 15
8这个节点被成功删除了，但是对二叉查找树进行中序遍历依然是保持排序性质的。

到这里，一个简单的二叉查找树就基本上完成了，我们为它实现了，添加、查找、删除以及先中后三种遍历方法。

完整的代码

1.方法一

/*
  实现下列方法
 insert(key) 插入一个新的键
 inOrderTraverse() 对树进行中序遍历，并打印结果
 preOrderTraverse() 对树进行先序遍历，并打印结果
 postOrderTraverse() 对树进行后序遍历，并打印结果
 search(key) 查找树中的键，如果存在返回true,不存在返回fasle
 findMin() 返回树中的最小值
 findMax() 返回树中的最大值
 remove(key) 删除树中的某个键
 */

function BinarySearchTree () {
  function Node (key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
  
  var root = null;
  // 插入节点
  this.insert = function (key) {
    var newNode = new Node(key);
    if (!root) {
      root = newNode;
    } else {
      insertNode(root, newNode);
    }
  };
  
  function insertNode (node, newNode) {
    if (node.key >= newNode.key) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        insertNode(node.left, newNode);
      }
    }
  }
  
  // 实现中序遍历
  this.inOrderTraverse = function () {
    inOrderTraverseNode(root);
  }
  
  function inOrderTraverseNode (node) {
    if (node !== null) {
      inOrderTraverseNode(node.left);
      console.log(node.key);
      inOrderTraverseNode(node.right);
    }
  }
  
  // 实在先序遍历
  this.preOrderTraverse = function () {
    preOrderTraverseNode(root);
  }
  
  function preOrderTraverseNode (node) {
    if (node !== null) {
      console.log(node.key);
      preOrderTraverseNode(node.left);
      preOrderTraverseNode(node.right);
    }
  }
  
  // 实现后序遍历
  this.postOrderTraverse = function () {
    inOrderTraverseNode(root);
  }
  
  function postOrderTraverseNode (node) {
    if (node !== null) {
      postOrderTraverseNode(node.left);
      postOrderTraverseNode(node.right);
      console.log(node.key);
    }
  }
  
  // 查找最大值
  this.findMax = function () {
    return maxNode(root);
  }
  
  function maxNode (node) {
    if (node) {
      while (node && node.right !== null) {
        node = node.right;
      }
      return node.right;
    }
    return null;
  }
  
  // 查找最小值
  this.findMin = function () {
    return minNode(root);
  }
  
  function minNode (node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }
      return node.left;
    }
    return null;
  }
  
  // 搜索特定的值
  this.search = function (key) {
    return searchNode(root, key);
  }
  
  function searchNode (node, key) {
    if (node === null) {
      return false;
    }
    
    if (key < node.key) {
      return searchNode(node.left, key);
    }
    if (key > node.key) {
      return searchNode(node.right, key);
    }
    
    if (key === node.key) {
      return true;
    }
  }
  
  // 移除节点
  this.remove = function (key) {
    removeNode(root, key);
  }
  
  function removeNode (node, key) {
    if (node === null) {
      return null;
    }
    if (key > node.key) {
      node = removeNode(node.right, key);
      return node;
    } else if (key < node.key) {
      node = removeNode(node.left, key);
      return node;
    } else {
      if (node.left === null && node.right === null) {
        node = null;
        return node;
      }
      if (node.left === null) {
        node = node.right;
        return node;
      }
      if (node.right === null) {
        node = node.left;
        return node;
      }
      var tem = minNode(node.right)
      node.key = tem.key;
      node.right = removeNode(node.right, tem.key)
      return node;
    }
  }
}

方法二

function BinarySearchTree () {
  var Node = function (key) {
    this.key = key,
      this.left = null,
      this.right = null
  }
  var root = null
  
  //插入节点
  this.insert = function (key) {
    var newNode = new Node(key)
    if (root === null) {
      root = newNode
    } else {
      insertNode(root, newNode)
    }
  }
  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)
      }
    }
  }
  
  //实现中序遍历
  this.inOrderTraverse = function () {
    inOrderTraverseNode(root)
  }
  var inOrderTraverseNode = function (node) {
    if (node !== null) {
      inOrderTraverseNode(node.left)
      console.log(node.key)
      inOrderTraverseNode(node.right)
    }
  }
  // 实现先序遍历
  this.preOrderTraverse = function () {
    preOrderTraverseNode(root)
  }
  var preOrderTraverseNode = function (node) {
    if (node !== null) {
      console.log(node.key)
      preOrderTraverseNode(node.left)
      preOrderTraverseNode(node.right)
    }
  }
  
  // 实现后序遍历
  this.postOrderTraverse = function () {
    postOrderTraverseNode(root)
  }
  var postOrderTraverseNode = function (node) {
    if (node !== null) {
      postOrderTraverseNode(node.left)
      postOrderTraverseNode(node.right)
      console.log(node.key)
    }
  }
  
  // 查找最小值
  this.findMin = function () {
    return minNode(root)
  }
  var minNode = function (node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left
      }
      return node.key
    }
    return null
  }
  
  // 查找最大值
  this.findMax = 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 true
    }
  }
  // 移除节点
  this.remove = function (key) {
    removeNode(root, key)
  }
  var removeNode = function (node, key) {
    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 {
      //需要移除的节点是一个叶子节点
      if (node.left === null && node.right === null) {
        node = null
        return node
      }
      //需要移除的节点包含一个子节点
      if (node.letf === 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, axu.key)
      return node
    }
  }
  var findMinNode = function (node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left
      }
      return node
    }
    return null
  }
}

方法三（慕课网js代码重写）

/**
 * 节点的结构
 * @param e 节点的值
 * @constructor
 */
function Node (e) {
    this.left = null; // 左节点初始值为空
    this.right = null; // 左右节点初始值为空的
    this.e = e; // 传入的节点的值
}

class BinarySearchTree {
    constructor () {
        this.size = 0; // 节点的数目
        this.root = null; // 根节点初始值为空
    }
    
    /**
     * 返回节点数目
     * @return {function()}
     */
    count () {
        return this.size;
    }
    
    /**
     * 判断二叉树是否为空
     * @return {boolean}
     */
    isEmpty () {
        return this.size === 0;
    }
    
    /**
     * 插入新的节点
     * @param e
     */
    add (e) {
        this.root = this._addNode(this.root, e);
    }
    
    /**
     * 利用递归的方法从根节点递归找到插入的位置然后插入相应的节点
     * @param node
     * @param e
     * @private
     */
    _addNode (node, e) {
        if (node === null) {
            this.size++;
            return new Node(e);
        }
        
        if (node.e >= e) {
            node.left = this._addNode(node.left, e);
        } else {
            node.right = this._addNode(node.right, e);
        }
        return node;
    }
    
    /**
     * 查看二叉树中是否包含元素e
     * @param e
     */
    contains (e) {
        return this._contains(this.root, e)
    }
    
    /**
     * 利用递归来判断e是否存在二叉树中
     * @param node
     * @param e
     * @return {*}
     * @private
     */
    _contains (node, e) {
        if (node === null) {
            return false;
        }
        if (node.e > e) {
            return this._contains(node.left, e);
        } else if (node.e < e) {
            return this._contains(node.right, e);
        } else {
            return true;
        }
    }
    
    preOrder () {
        this._preOrder(this.root);
    }
    
    /**
     * 前序遍历, 递归算法
     * @param node
     * @private
     */
    _preOrder (node) {
        if (node === null) {
            return;
        }
        console.log(node.e);
        this._preOrder(node.left);
        this._preOrder(node.right);
    }
    
    /**
     * 前序遍历的非递归实现
     * 利用数组模仿栈来实现非递归前序遍历
     */
    preOrderNR () {
        if (this.root === null) {
            return;
        }
        const stack = [];
        let cur = null;
        stack.push(this.root);
        while (stack.length) {
            cur = stack.pop();
            console.log(cur.e);
            if (cur.right) {
                stack.push(cur.right);
            }
            if (cur.left) {
                stack.push(cur.left);
            }
        }
    }
    
    /**
     * 中序遍历
     */
    inOrder () {
        this._inOrder(this.root)
    }
    
    _inOrder (node) {
        if (node === null) {
            return;
        }
        this._inOrder(node.left);
        console.log(node.e);
        this._inOrder(node.right);
    }
    
    /**
     * 后序遍历
     */
    postOrder () {
        this._postOrder(this.root)
    }
    
    _postOrder (node) {
        if (node === null) {
            return;
        }
        this._postOrder(node.left);
        this._postOrder(node.right);
        console.log(node.e);
    }
    
    /**
     * 层序遍历
     */
    levelOrder () {
        if (this.root === null) {
            return;
        }
        const queue = [];
        let cur = null;
        queue.push(this.root);
        while (queue.length) {
            cur = queue.shift();
            console.log(cur.e);
            if (cur.left) {
                queue.push(cur.left)
            }
            if (cur.right) {
                queue.push(cur.right)
            }
        }
    }
    
    /**
     * 寻找最小值
     * @return {*|string}
     */
    minimum () {
        if (!this.size) {
            throw new Error('二叉树为空');
        }
        return (this._minimum(this.root)).e;
    }
    
    _minimum (node) {
        if (node.left === null) {
            return node;
        }
        return this._minimum(node.left);
    }
    
    /**
     * 寻找最大值
     * @return {*|string}
     */
    maximum () {
        if (!this.size) {
            throw new Error('二叉树为空');
        }
        return (this._maximum(this.root)).e;
    }
    
    _maximum (node) {
        if (node.right === null) {
            return node;
        }
        return this._maximum(node.right);
    }
    
    /**
     * 删除二叉树中的最小值
     * @return {*}
     */
    removeMin () {
        const res = this._minimum(this.root);
        this.root = this._removeMin(this.root);
        return res;
    }
    
    /**
     * 删除掉以node为根的二分搜索树中的最小节点
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @return {*}
     * @private
     */
    _removeMin (node) {
        if (node.left === null) {
            this.size--;
            return node.right;
        }
        node.left = this._removeMin(node.left);
        return node;
    }
    
    /**
     * 删除二叉树中的最大值
     * @return {*}
     */
    removeMax () {
        const res = this._maximum(this.root);
        this.root = this._removeMax(this.root);
        return res;
    }
    
    /**
     * 删除掉以node为根的二分搜索树中的最大节点
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @return {*}
     * @private
     */
    _removeMax (node) {
        if (node.right === null) {
            this.size--;
            return node.left;
        }
        node.right = this._removeMax(node.right);
        return node;
    }
    
    /**
     * 从二分搜索树中删除元素为e的节点
     * @param e
     */
    remove (e) {
        this.root = this._remove(this.root, e);
    }
    
    _remove (node, e) {
        if (node === null) {
            // return null;
            throw new Error('没有找到节点');
        }
        if (node.e > e) {
            node.left = this._remove(node.left, e);
            return node;
        } else if (node.e < e) {
            node.right = this._remove(node.right, e);
            return node;
        } else {
            // 待删除节点右子树为空的情况
            if (node.right === null) {
                this.size--;
                return node.left;
            }
            // 待删除节点左子树为空的情况
            if (node.left === null) {
                this.size--;
                return node.right;
            }
            // 待删除节点左右子树均不为空的情况
            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            const successor = this.minimum(node.right);
            successor.right = this.removeMin(node.right);
            successor.left = node.left;
            return successor;
        }
    }
    
}

const bst = new BinarySearchTree();
[ 29, 38, 39, 20 ].map((item) => {
    return bst.add(item);
})
// console.log(JSON.stringify(bst));
// console.log(bst.count())
// console.log(bst.contains(10))
// bst.preOrder()
// console.log('-----')
// bst.preOrderNR()
// console.log('-----')
// bst.inOrder()
// console.log('-----')
// bst.postOrder()
// console.log('-----')
// bst.levelOrder()
// console.log('-----')
// console.log(bst.minimum())
// console.log('-----')
// console.log(bst.maximum())
// console.log('-----')
// bst.removeMin()
// console.log(bst.minimum())
// console.log('-----')
// bst.removeMax()
// console.log(bst.maximum())
// console.log('-----')
// console.log(bst.count())

console.log('-----')
// bst.remove(39)
console.log(bst.contains(39))

参考文章

JavaScript实现简单二叉查找树

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

二叉搜索树 #30

二叉搜索树 #30

wl05 commented May 28, 2019

二叉搜索树 #30

二叉搜索树 #30

Comments

wl05 commented May 28, 2019

相关术语

代码实现

1. 向树中插入一个键

2. 完成中序遍历方法

3. 先序遍历、后序遍历

4. 查找最小、最大值

5. 搜索特定值

6. 移除节点

完整的代码

参考文章