JavaScript简单实现二叉搜索树

概念

二叉树：树中每个节点最多只能有两个子节点。
二叉搜索树（BST）：二叉树的一种，但是它只允许你在左侧节点存储(比父节点)小的值， 在右侧节点存储(比父节点)大(或者等于)的值。
比如：

      11
    7   13
  5   9 
3

代码中存储结构如下

{
  key: 11,  // root 指向 key 为 11 的对象。
  left: {
    key: 7,
    left:  { 
      key: 5, 
      left: {
        key: 3,
        left: null,  
        right: null  
      },  
      right: null  
    },
    right:  {  
      key: 9,  
      left: null,  
      right: null  
    } 
  },
  right: {  
    key: 13,  
    left: null,  
    right: null  
  }  
}

代码实现及注释

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 (callback) {
        inOrderTraverseNode(root,callback)
    }
    var inOrderTraverseNode = function (node, callback) {
        if(node !== null){
            inOrderTraverseNode(node.left,callback)
            callback(node.key)
            inOrderTraverseNode(node.right,callback)
        }
    }
    // 递归方式进行先序遍历，先访问根，然后访问左子树和右子树
    this.proOderTraverse = function (callback) {
        proOderTraverseNode(root,callback)
    }
    var proOderTraverseNode = function (node,callback) {
        if(node !== null){
            callback(node.key);
            proOderTraverseNode(node.left,callback)
            proOderTraverseNode(node.right,callback)
        }
    }
    // 递归方式进行后序遍历，先访问左子树和右子树，最后访问根
    this.postOrderTraverse = function (callback) {
        postOrderTraverseNode(root,callback)
    }
    var postOrderTraverseNode = function (node,callback) {
        if(node !== null){
            postOrderTraverseNode(node.left,callback)
            postOrderTraverseNode(node.right,callback)
            callback(node.key)
        }
    }
    this.values = function (traversFunc) {
        var keyList = [];
        this[traversFunc](function (key) {
            keyList.push(key)
        })
        return keyList
    }
    // 非递归方式实现中序遍历，通过栈的方式实现
    this.inOrderTraverseUnRec = function (calback) {
        // 存在跟节点时才进行遍历
        if(root !== null){
            // 使用数组实现一个栈的存储
            var items = [], node = root;
            // 当栈不为空或者当前的节点时存在时都会进行如下操作
            while(items.length !== 0 && node){
                if(node){
                    // node存在时向左遍历整个树结构，将最左边的节点push到栈中
                    items.push(node);
                    node = node.left
                }else{
                    // 如果node不存在时，可能是上次遍历的左节点或右节点不存在，这时是需要pop栈中之前存放的一个节点，对该节点进行其循环操作
                    node = items.pop();
                    calback(node.key)
                    node = node.right
                }
            }
        }
    }
    // 非递归法实现先序遍历法，先访问根节点，然后访问左右子树
    this.preOrderTraverseUnRec = function (calback) {
        if (root !== null) {
            var items = [];
            // 最初将根节点push到栈中
            items.push(root);
            // 当栈不为空时进行如下操作，每次都将一个节点push到栈中，栈为空时是将节点遍历完了
            while (item.length !== 0) {
                // 从根节点开始，先访问当前节点，然后将当前节点的右、左节点一次push到栈中，因为后入先出，每次循环都pop出一个节点
                var node = items.pop();
                if (calback) {
                    calback(node.key)
                }
                if (node.right) {
                    item.push(node.right)
                }
                if (node.left) {
                    item.push(node.left)
                }
            }
        }
    }
    // 非递归法实现后序遍历法，先访左右子树节点，然后访问根节点
    this.postOrderTraverseUnRec = function (calback) {
        if (root !== null) {
            var items1 = [],
                items2 = [],
                node;
        // 非递归法实现后序遍历需要用到两个栈，第一个栈用于先序遍历，
        // 第二个栈用于存放先序遍历的结果，该栈出栈的结果即为后序遍历结果
            items1.push(root)
            while (items1.length !== 0) {
                node = items1.pop();
                items2.push(node);
                // 此处需要进入到另一个栈出栈，左右节点进入到第二个栈的顺序与先序遍历有所不同
                if (node.left) {
                    items1.push(node.left)
                }
                if (node.right) {
                    items1.push(node.right)
                }
            }
            while (items2.length !== 0) {
                node = items2.pop()
                if (calback) {
                    calback(node.key)
                }
            }
        }
    }
}