JS二叉树的简单实现方法示例

二叉树是一种非常重要的数据结构，在计算机科学中有广泛的应用。JS作为一门常用的编程语言，也可以利用其语言特性来实现二叉树。

一、二叉树简介

二叉树是一种最常用的树形数据结构之一，满足以下几个特点：

• 每个节点最多只有两个子节点，分别为左子节点和右子节点；
• 左子节点的值小于或等于父节点的值；
• 右子节点的值大于或等于父节点的值。

二叉树的示意图如下：

      6
     / \
    4   8
   / \
  2   5

二、二叉树的实现

我们可以使用JS的class来实现一个基础的二叉树数据结构。

代码如下：

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

上面的代码定义了一个名为TreeNode的类，它有三个属性：

• val：表示节点的值；
• left：表示节点的左子节点；
• right：表示节点的右子节点。

三、二叉树的操作

1.建立二叉树

我们可以通过建立一个方法，按照给定的顺序将值插入二叉树中，从而建立一个完整的二叉树。

示例代码如下：

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

  // 向树中插入节点
  insert(val) {
    if (this.root === null) {
      this.root = new TreeNode(val);
      return;
    }

    let node = this.root;

    while (node) {
      if (val < node.val) {
        if (node.left === null) {
          node.left = new TreeNode(val);
          return;
        } else {
          node = node.left;
        }
      } else {
        if (node.right === null) {
          node.right = new TreeNode(val);
          return;
        } else {
          node = node.right;
        }
      }
    }
  }
}

上面的代码定义了一个名为BinaryTree的类，它有一个属性root，表示二叉树的根节点。它还有一个名为insert的方法，用来将一个值插入二叉树中。

2.二叉树的遍历

二叉树的遍历是指按照一定顺序依次访问二叉树中的所有节点。常用的有前序遍历、中序遍历和后序遍历。下面是它们的详细介绍：

前序遍历：

前序遍历的顺序是根节点 -> 左子节点 -> 右子节点。代码示例如下：

class BinaryTree {
  // ...

  // 前序遍历
  preOrderTraversal(node) {
    if (node === null) {
      return;
    }

    console.log(node.val);
    this.preOrderTraversal(node.left);
    this.preOrderTraversal(node.right);
  }
}

中序遍历：

中序遍历的顺序是左子节点 -> 根节点 -> 右子节点。代码示例如下：

class BinaryTree {
  // ...

  // 中序遍历
  inOrderTraversal(node) {
    if (node === null) {
      return;
    }

    this.inOrderTraversal(node.left);
    console.log(node.val);
    this.inOrderTraversal(node.right);
  }
}

后序遍历：

后序遍历的顺序是左子节点 -> 右子节点 -> 根节点。代码示例如下：

class BinaryTree {
  // ...

  // 后序遍历
  postOrderTraversal(node) {
    if (node === null) {
      return;
    }

    this.postOrderTraversal(node.left);
    this.postOrderTraversal(node.right);
    console.log(node.val);
  }
}

四、二叉树的示例

示例一

下面给定了一棵二叉树：

      5
     / \
    3   8
   / \
  1   4

通过上面的代码，我们可以轻松地建立这棵二叉树，并进行前、中、后序遍历。

let binaryTree = new BinaryTree();

binaryTree.insert(5);
binaryTree.insert(3);
binaryTree.insert(8);
binaryTree.insert(1);
binaryTree.insert(4);

console.log('前序遍历');
binaryTree.preOrderTraversal(binaryTree.root);

console.log('中序遍历');
binaryTree.inOrderTraversal(binaryTree.root);

console.log('后序遍历');
binaryTree.postOrderTraversal(binaryTree.root);

输出结果为：

前序遍历
5
3
1
4
8
中序遍历
1
3
4
5
8
后序遍历
1
4
3
8
5

示例二

下面给定了一棵二叉树：

      10
     /  \
    5    20
   /    /  \
  2    15   30

同样地，我们可以通过上面的代码来建立这棵二叉树，并进行前、中、后序遍历。

let binaryTree = new BinaryTree();

binaryTree.insert(10);
binaryTree.insert(5);
binaryTree.insert(20);
binaryTree.insert(2);
binaryTree.insert(15);
binaryTree.insert(30);

console.log('前序遍历');
binaryTree.preOrderTraversal(binaryTree.root);

console.log('中序遍历');
binaryTree.inOrderTraversal(binaryTree.root);

console.log('后序遍历');
binaryTree.postOrderTraversal(binaryTree.root);

输出结果为：

前序遍历
10
5
2
20
15
30
中序遍历
2
5
10
15
20
30
后序遍历
2
5
15
30
20
10

至此，我们就成功地实现了二叉树的基础操作。