js实现二叉树

二叉树的基本概念

二叉树是一种树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的常见操作包括插入、删除、遍历等。

二叉树的节点定义

在JavaScript中，二叉树的节点可以通过对象或类来定义。每个节点包含数据、左子节点和右子节点的引用。

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

二叉树的插入

插入操作需要根据二叉树的规则（如二叉搜索树的性质）将新节点放置在正确的位置。

class BinaryTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new TreeNode(value);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this._insertNode(this.root, newNode);
    }
  }

  _insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this._insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this._insertNode(node.right, newNode);
      }
    }
  }
}

二叉树的遍历

二叉树的遍历方式包括前序遍历、中序遍历和后序遍历。

class BinaryTree {
  // ... 其他方法

  // 前序遍历
  preOrderTraversal(node = this.root) {
    if (node !== null) {
      console.log(node.value);
      this.preOrderTraversal(node.left);
      this.preOrderTraversal(node.right);
    }
  }

  // 中序遍历
  inOrderTraversal(node = this.root) {
    if (node !== null) {
      this.inOrderTraversal(node.left);
      console.log(node.value);
      this.inOrderTraversal(node.right);
    }
  }

  // 后序遍历
  postOrderTraversal(node = this.root) {
    if (node !== null) {
      this.postOrderTraversal(node.left);
      this.postOrderTraversal(node.right);
      console.log(node.value);
    }
  }
}

二叉树的查找

查找操作根据二叉树的规则（如二叉搜索树的性质）判断节点是否存在。

class BinaryTree {
  // ... 其他方法

  search(value, node = this.root) {
    if (node === null) {
      return false;
    }
    if (value < node.value) {
      return this.search(value, node.left);
    } else if (value > node.value) {
      return this.search(value, node.right);
    } else {
      return true;
    }
  }
}

二叉树的删除

删除操作需要处理三种情况：节点无子节点、节点有一个子节点、节点有两个子节点。

class BinaryTree {
  // ... 其他方法

  delete(value) {
    this.root = this._deleteNode(this.root, value);
  }

  _deleteNode(node, value) {
    if (node === null) {
      return null;
    }
    if (value < node.value) {
      node.left = this._deleteNode(node.left, value);
    } else if (value > node.value) {
      node.right = this._deleteNode(node.right, value);
    } else {
      if (node.left === null && node.right === null) {
        return null;
      }
      if (node.left === null) {
        return node.right;
      }
      if (node.right === null) {
        return node.left;
      }
      const minRight = this._findMinNode(node.right);
      node.value = minRight.value;
      node.right = this._deleteNode(node.right, minRight.value);
    }
    return node;
  }

  _findMinNode(node) {
    while (node.left !== null) {
      node = node.left;
    }
    return node;
  }
}

示例用法

以下是一个简单的示例，展示如何使用上述代码创建和操作二叉树。

const tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);

console.log("前序遍历:");
tree.preOrderTraversal();

console.log("中序遍历:");
tree.inOrderTraversal();

console.log("后序遍历:");
tree.postOrderTraversal();

console.log("查找7:", tree.search(7));
console.log("查找20:", tree.search(20));

tree.delete(5);
console.log("删除5后的中序遍历:");
tree.inOrderTraversal();