JavaScript实现二叉树定义、遍历及查找的方法详解

二叉树是一种常见的树形数据结构，由一个根节点和最多两个子节点组成，其中左子节点小于等于根节点，右子节点大于根节点。在JavaScript中，我们可以使用对象来模拟二叉树。

1. 二叉树的定义

我们可以定义一个二叉树的节点对象，包含三个属性：值(value)、左子节点(left)、右子节点(right)。定义二叉树类(Tree)，包含一个根节点(root)。

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

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

2. 二叉树的遍历

二叉树的遍历有三种方式：前序遍历、中序遍历和后序遍历。

前序遍历

前序遍历的方式是先遍历根节点，然后遍历左子节点，再遍历右子节点。

实现方式：

function preOrder(node) {
  if (node === null) return [];
  const res = [];
  res.push(node.value);
  res.push(...preOrder(node.left));
  res.push(...preOrder(node.right));
  return res;
}

中序遍历

中序遍历的方式是先遍历左子节点，然后遍历根节点，再遍历右子节点。

实现方式：

function inOrder(node) {
  if (node === null) return [];
  const res = [];
  res.push(...inOrder(node.left));
  res.push(node.value);
  res.push(...inOrder(node.right));
  return res;
}

后序遍历

后序遍历的方式是先遍历左子节点，然后遍历右子节点，再遍历根节点。

实现方式：

function postOrder(node) {
  if (node === null) return [];
  const res = [];
  res.push(...postOrder(node.left));
  res.push(...postOrder(node.right));
  res.push(node.value);
  return res;
}

3. 二叉树的查找

插入节点

二叉树的查找可以通过插入节点来实现，插入节点时需要遍历二叉树，找到插入的位置。这里以中序遍历为例：

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

  insert(value) {
    const node = new TreeNode(value);
    if (!this.root) {
      this.root = node;
      return this;
    }
    let cur = this.root;
    while (cur) {
      if (value < cur.value) {
        if (!cur.left) {
          cur.left = node;
          return this;
        }
        cur = cur.left;
      } else {
        if (!cur.right) {
          cur.right = node;
          return this;
        }
        cur = cur.right;
      }
    }
    return this;
  }
}

查找节点

查找节点的实现也可以通过遍历二叉树来实现，这里同样以中序遍历为例：

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

  find(value) {
    let cur = this.root;
    while (cur) {
      if (value === cur.value) {
        return cur;
      } else if (value < cur.value) {
        cur = cur.left;
      } else {
        cur = cur.right;
      }
    }
    return null;
  }
}

4. 示例

以下为一个简单的示例，展示了如何使用这些方法创建一个二叉树，并进行遍历和查找：

const tree = new Tree();
tree.insert(5)
    .insert(3)
    .insert(7)
    .insert(2)
    .insert(4)
    .insert(6)
    .insert(8);

console.log('preOrder:', preOrder(tree.root));   // [5, 3, 2, 4, 7, 6, 8]
console.log('inOrder:', inOrder(tree.root));     // [2, 3, 4, 5, 6, 7, 8]
console.log('postOrder:', postOrder(tree.root)); // [2, 4, 3, 6, 8, 7, 5]

const node = tree.find(4);
console.log(node);  // TreeNode { value: 4, left: [TreeNode], right: [TreeNode] }