排序二叉树基本操作

创建

function BinaryTree() {
  var Node = function (key) {
    this.key = key;
    this.left = null;
    this.right = null;
  };

  var root = 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);
      }
    }
  }

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

遍历

中序遍历

function BinaryTree() {
  // code ...
  // 中序遍历
  var inOrderTraverseNode = function (node, callback) {
    if (node !== null) {
      inOrderTraverseNode(node.left, callback);
      callback(node.key);
      inOrderTraverseNode(node.right, callback);
    }
  }

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

前序遍历

function BinaryTree() {
  // code ...
  // 前序遍历
  var preOrderTraverseNode = function (node, callback) {
    if (node !== null) {
      callback(node.key);
      preOrderTraverseNode(node.left, callback);
      preOrderTraverseNode(node.right, callback);
    }
  };

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

后序遍历

function BinaryTree() {
  // code ...
  // 后序遍历
  var postOrderTraverseNode = function (node, callback) {
    if (node !== null) {
      postOrderTraverseNode(node.left, callback);
      postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  };

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

查找

function BinaryTree() {
  // code ...
  // 排序二叉树最小最大值
  var minNode = function (node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }
      return node.key;
    }
    return null;
  };

  var maxNode = function (node) {
    if (node) {
      while (node && node.right !== null) {
        node = node.right;
      }
      return node.key;
    }
    return null;
  };

  this.min = function () {
    return minNode(root);
  };

  this.max = function () {
    return maxNode(root);
  }

  // 二叉排序树查找给定数值
  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.search = function (key) {
    return searchNode(root, key);
  }
  // code ...
}

删除

function BinaryTree() {
  // code ...
  // 二叉排序树删除给定中间节点
  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) {
        return null;
      }
      if (node.left === null) {
        node = node.right;
        return node;
      } else if (node.right === null) {
        node = node.left;
        return node;
      }
      var temp = findMinNode(node.right);
      node.key = temp.key;
      node.right = removeNode(node.right, temp.key);
      return node;
    }
  }

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

  this.remove = function (key) {
    root = removeNode(root, key);
  };
  // code ...
}