二叉树的定义

二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树在计算机科学中有广泛的应用，如表达式解析、排序、搜索等。

二叉树的正式定义

二叉树（Binary Tree）: 是一种树形数据结构，其中每个节点最多有两个子节点，这两个子节点分别称为左子节点和右子节点。

二叉树的特点

1. 每个节点最多有两个子节点：一个左子节点和一个右子节点。
2. 子节点的顺序是重要的：即使一个节点只有一个子节点，也需要区分它是左子节点还是右子节点。
3. 递归定义：二叉树是由一个根节点和两个分别为左子树和右子树的二叉树组成的。

二叉树的分类

根据不同的特性，二叉树可以进一步分类为：

1. 满二叉树（Full Binary Tree）：每个节点要么没有子节点，要么有两个子节点。
2. 完全二叉树（Complete Binary Tree）：除了最后一层，所有层的节点都是满的，且最后一层的节点尽可能地从左到右排列。
3. 完美二叉树（Perfect Binary Tree）：所有内部节点都有两个子节点，且所有叶节点在同一层。
4. 平衡二叉树（Balanced Binary Tree）：任何节点的两个子树的高度差不超过1。
5. 二叉搜索树（Binary Search Tree, BST）：对于每个节点，左子树的所有节点值小于该节点值，右子树的所有节点值大于该节点值。

二叉树的表示

二叉树可以通过多种方式表示，常见的表示方法包括：

1. 链式存储（链表）：每个节点包含数据和指向左、右子节点的指针。
2. 顺序存储（数组）：使用数组存储二叉树节点。

链式存储结构

在链式存储结构中，每个节点包含三个部分：数据、左子节点指针和右子节点指针。

class TreeNode {
  constructor(value) {
    this.value = value; // 节点数据
    this.left = null;   // 左子节点指针
    this.right = null;  // 右子节点指针
  }
}

// 创建根节点
const root = new TreeNode('root');

// 创建子节点
const leftChild = new TreeNode('left');
const rightChild = new TreeNode('right');

// 连接子节点
root.left = leftChild;
root.right = rightChild;

console.log(root);

顺序存储结构

在顺序存储结构中，二叉树节点按层级顺序存储在数组中。对于数组中的第 i 个节点：

• 左子节点索引为 2 * i + 1
• 右子节点索引为 2 * i + 2

// 使用数组表示二叉树
const tree = ['root', 'left', 'right', 'left.left', 'left.right', 'right.left', 'right.right'];

// 访问根节点
console.log(tree[0]); // 'root'

// 访问左子节点
console.log(tree[1]); // 'left'

// 访问右子节点
console.log(tree[2]); // 'right'

// 访问左子节点的左子节点
console.log(tree[3]); // 'left.left'