JavaScript/BinaryTree/binaryTree08.html

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8">
    <title>删除中间节点</title>
  </head>
  <body>
    <script>
      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);
          }
        };

        //中序遍历代码实现
        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);
        }

        //前序遍历代码实现
        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);
        }

        //后序遍历代码实现
        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);
        }

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

        //查找最大值
        var maxNode = function (node) {
          if (node) {
            while (node && node.right !== null) {
              node = node.right;
            }
            return node.key;
          }
          return null;
        }
        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);
        }

        //找到最小节点
        var findMinNode = function (node) {
          if (node) {
            while (node && node.left !== null) {
              node = node.left;
            }
            return node;
          }
          return null;
        }
        //删除节点
        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.left === 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, aux.key);
            return node;
          }
        }
        this.remove = function (key) {
          root = removeNode(root, key);
        }
      }

      var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
      var binaryTree = new BinaryTree();
      nodes.forEach(function (key) {
        binaryTree.insert(key);
      });

      //遍历整个二叉树
      var callback = function (key) {
        console.log(key);
      }
      binaryTree.remove(3);
      binaryTree.postOrderTraverse(callback);
    </script>
  </body>
</html>