二叉搜索树实现与操作

[evenMai92]

// 二叉搜索树
function BinaryTree() {
  const Node = function(key) {
    //节点函数
    this.key = key;
    this.left = null;
    this.right = null;
  };

  let root = null;

  // 插入
  this.insert = function(key) {
    // 插入节点
    let insertNode = function(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.right, newNode);
        }
      }
    };
    const newNode = new Node(key);
    if (root == null) {
      root = newNode;
    } else {
      insertNode(root, newNode);
    }
  };

  // 获取二叉树
  this.getTree = function() {
    return root;
  }

  // 递归中序遍历 排序
  this.inOrderTraverse = function(callback) {
    const inOrderTraverseNode = function(node, callback) {
      if (node != null) {
        inOrderTraverseNode(node.left, callback);
        callback(node.key);
        inOrderTraverseNode(node.right, callback);
      }
    };
    inOrderTraverseNode(root, callback);
  };

  // 非递归中序遍历(利用栈实现)
  this.nonRecursiveInOrderTraverse = function(callback) {
    const stack = [{status: 'next', node: root}];
    while(stack && stack.length !== 0) {
      const cur = stack.pop();
      if(cur.status === 'print') {
        callback(cur.node.key);
      } else {
        cur.node.right && stack.push({status: 'next', node: cur.node.right});
        stack.push({status: 'print', node: cur.node });
        cur.node.left && stack.push({status: 'next', node: cur.node.left});
      }
    }
  }

  //递归前序遍历  复制二叉树  效率高得多
  this.proOrderTraverse = function(callback) {
    const proOrderTraverseNode = function(node, callback) {
      if (node != null) {
        callback(node.key);
        proOrderTraverseNode(node.left, callback);
        proOrderTraverseNode(node.right, callback);
      }
    };
    proOrderTraverseNode(root, callback);
  };

  // 非递归前序遍历(利用栈实现)
  this.nonRecursiveProOrderTraverse = function(callback) {
    const stack = [{status: 'next', node: root}];
    while(stack && stack.length !== 0) {
      const cur = stack.pop();
      if(cur.status === 'print') {
        callback(cur.node.key);
      } else {
        cur.node.right && stack.push({status: 'next', node: cur.node.right});
        cur.node.left && stack.push({status: 'next', node: cur.node.left});
        stack.push({status: 'print', node: cur.node });
      }
    }
  }

  //后续遍历  文件系统遍历
  this.postOrderTraverse = function(callback) {
    const postOrderTraverseNode = function(node, callback) {
      if (node != null) {
        postOrderTraverseNode(node.left, callback);
        postOrderTraverseNode(node.right, callback);
        callback(node.key);
      }
    };
    postOrderTraverseNode(root, callback);
  };

  // 非递归前序遍历(利用栈实现)
  this.nonRecursivePostOrderTraverse = function(callback) {
    const stack = [{status: 'next', node: root}];
    while(stack && stack.length !== 0) {
      const cur = stack.pop();
      if(cur.status === 'print') {
        callback(cur.node.key);
      } else {
        stack.push({status: 'print', node: cur.node });
        cur.node.right && stack.push({status: 'next', node: cur.node.right});
        cur.node.left && stack.push({status: 'next', node: cur.node.left});
      }
    }
  }

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

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

  // 查找指定值
  this.search = function(key) {
    const searchNode = function(node, key) {
      if (node == null) {
        return false;
      }

      if (node.key > key) {
        searchNode(node.left, key);
      } else if (node.key < key) {
        searchNode(node.right, key);
      } else {
        return true;
      }
    };
    return searchNode(root, key);
  };

  /**
   * 二叉树的删除
   * 二叉树删除分三种情况
   * 删除左叶子节点
   * 删除右叶子节点
   * 以及拥有左右两个节点的主节点删除
   * 拥有左右两个节点的主节点删除要考虑到数据的可排序行需要将删掉的节点重新赋值
   */
  // 移除节点
  this.remove = function(key) {
    const findMinNode = function(node) {
      //如果存在左右两个节点的话查找右节点的最小节点
      if (node) {
        while (node && node.left != null) {
          node = node.left;
        }
        return node;
      }
      return null;
    };
    const removeNode = function(node, key) {
      if (node == null) {
        return null;
      }
  
      if (node.key > key) {
        // 递归查找左叶子节点，直接等于返回的null值
        node.left = removeNode(node.left, key);
        return node;
      } else if (node.key < key) {
        node.right = removeNode(node.right, key);
        return node;
      } else {
        if (node.left == null && node.right == null) {
          // 当只有一个节点，而且被选中
          node = null;
          return node;
        }
        if (node.left == null) {
          //左节点为空
          node = node.right;
          return node;
        } else if (node.right == null) {
          //右节点为空
          node = node.left;
          return node;
        }
  
        // ?????
        let aux = findMinNode(node.right); //查找到右节点最小节点赋值
        node.key = aux.key;
        node.right = removeNode(node.right, aux.key);
        return node;
      }
    };
    return removeNode(root, key);
  };
}

// test
const nodes = [8, 3, 10, 2, 9, 14, 4, 7, 13];
const binaryTree = new BinaryTree();
nodes.forEach(function(key) {
  binaryTree.insert(key);
});

const callback = function(key) {
  console.log(key);
};
binaryTree.nonRecursivePostOrderTraverse(callback);