二叉树
最后更新
二叉树是一种层级结构，每个节点最多有两个子节点，分别叫左子节点和右子节点。最顶端的节点是根节点，没有子节点的节点是叶子节点，从根节点到最深叶子节点的边数就是树的高度。和二叉搜索树不同，普通二叉树没有顺序规则，它只是一种形状。点击上方的“播放”，观察一棵树逐层填满，然后按中序（左、节点、右）被遍历。
很多结构都建立在二叉树之上：二叉搜索树、堆、表达式树等。遍历按照确定的顺序访问每个节点：中序、前序和后序是三种深度优先遍历，各自适合不同的任务。
术语
| 术语 | 含义 |
|---|---|
| 根节点 | 最顶端的节点，没有父节点 |
| 叶子节点 | 没有子节点的节点 |
| 高度 | 从根节点到叶子节点的最长路径（按边数计） |
| 深度 | 某个节点到根节点的距离 |
| 完全二叉树 | 除最后一层外每层都是满的，最后一层从左到右填充 |
三种深度优先遍历
| 遍历方式 | 顺序 | 常见用途 |
|---|---|---|
| 中序遍历 | 左、节点、右 | 按顺序输出 BST |
| 前序遍历 | 节点、左、右 | 复制或序列化一棵树 |
| 后序遍历 | 左、右、节点 | 删除一棵树或对其求值 |
示例演算
对由 [4, 2, 6, 1, 3, 5] 逐层填充构建的树进行中序遍历：
| 步骤 | 当前节点 | 操作 |
|---|---|---|
| 1 | 4 | 访问 4 之前，先递归进入它的左子树 |
| 2 | 2 | 访问 2 之前，先递归进入它的左子树 |
| 3 | 1 | 叶子节点，没有左子节点，访问 1，输出 [1] |
| 4 | 2 | 左边处理完毕，访问 2，输出 [1, 2]，然后递归进入右边 |
| 5 | 3 | 叶子节点，访问 3，输出 [1, 2, 3] |
| 6 | 4 | 左子树处理完毕，访问 4，输出 [1, 2, 3, 4]，然后递归进入右边 |
| 7 | 5 | 6 的左子节点，是叶子节点，访问 5，输出 [1, 2, 3, 4, 5] |
| 8 | 6 | 左边处理完毕，没有右子节点，访问 6，输出 [1, 2, 3, 4, 5, 6] |
什么时候使用二叉树
| 适合使用的情况 | 不适合使用的情况 |
|---|---|
| 需要表示本身就有层级的数据（文件系统、表达式树、DOM） | 数据是扁平的，用列表或数组就够了，树只会增加开销 |
| 需要有序操作，并且能保持树的平衡（BST 或自平衡树） | 需要按键平均 O(1) 查找，哈希表胜过任何树 |
| 需要按中序、前序或后序处理结构化数据 | 把有序的节点插入不平衡的 BST，它会退化成 O(n) 的链表 |
| 范围查询或有序迭代很重要，而哈希表做不到 | 内存紧张，每个节点除了数据还要存两个子节点指针 |
Binary Tree 代码
简洁、可运行的 Binary Tree 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Binary Tree 的 Python 代码
Python
1from collections import deque2
3
4class Node:5 def __init__(self, value):6 self.value = value7 self.left = None8 self.right = None9
10
11def insert(root, value):12 # Level-order insert: fill the first empty child slot found13 if root is None:14 return Node(value)15 queue = deque([root])16 while queue:17 node = queue.popleft()18 if node.left is None:19 node.left = Node(value)20 return root21 queue.append(node.left)22 if node.right is None:23 node.right = Node(value)24 return root25 queue.append(node.right)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36 root = insert(root, value)37
38print("Root: ", root.value)39print("Inorder:", inorder(root))Binary Tree 的 JavaScript 代码
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinaryTree {10 constructor() {11 this.root = null;12 }13
14 // Insert at the first free spot, top to bottom (level order)15 insert(value) {16 const node = new Node(value);17 if (!this.root) {18 this.root = node;19 return;20 }21 const queue = [this.root];22 while (queue.length > 0) {23 const current = queue.shift();24 if (!current.left) {25 current.left = node;26 return;27 }28 if (!current.right) {29 current.right = node;30 return;31 }32 queue.push(current.left, current.right);33 }34 }35
36 inorder(node = this.root, out = []) {37 if (!node) return out;38 this.inorder(node.left, out);39 out.push(node.value);40 this.inorder(node.right, out);41 return out;42 }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));Binary Tree 的 Java 代码
Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5 static class Node {6 int value;7 Node left, right;8 Node(int value) { this.value = value; }9 }10
11 static Node root;12
13 // Insert at the first free slot in level order (keeps the tree complete)14 static void insert(int value) {15 Node node = new Node(value);16 if (root == null) { root = node; return; }17 Queue<Node> queue = new ArrayDeque<>();18 queue.add(root);19 while (!queue.isEmpty()) {20 Node cur = queue.poll();21 if (cur.left == null) { cur.left = node; return; }22 if (cur.right == null) { cur.right = node; return; }23 queue.add(cur.left);24 queue.add(cur.right);25 }26 }27
28 // Inorder: left subtree, node, right subtree29 static void inorder(Node node, StringBuilder sb) {30 if (node == null) return;31 inorder(node.left, sb);32 sb.append(node.value).append(" ");33 inorder(node.right, sb);34 }35
36 public static void main(String[] args) {37 for (int v = 1; v <= 7; v++) insert(v);38 StringBuilder sb = new StringBuilder();39 inorder(root, sb);40 System.out.println("Root: " + root.value);41 System.out.println("Inorder: " + sb.toString().trim());42 }43}Binary Tree 的 C++ 代码
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else root->right = insert(root->right, value);14 return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19 if (node == nullptr) return;20 inorder(node->left);21 std::cout << node->value << " ";22 inorder(node->right);23}24
25int countNodes(const Node* node) {26 if (node == nullptr) return 0;27 return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31 Node* root = nullptr;32 for (int value : {8, 3, 10, 1, 6, 14, 4}) {33 root = insert(root, value);34 }35 std::cout << "In-order: ";36 inorder(root);37 std::cout << "\n";38 std::cout << "Node count: " << countNodes(root) << "\n";39 return 0;40}Binary Tree 的 C 代码
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* left;7 struct Node* right;8} Node;9
10Node* newNode(int value) {11 Node* n = malloc(sizeof(Node));12 n->value = value;13 n->left = n->right = NULL;14 return n;15}16
17Node* insert(Node* root, int value) {18 if (root == NULL) return newNode(value);19 if (value < root->value) root->left = insert(root->left, value);20 else root->right = insert(root->right, value);21 return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26 if (node == NULL) return;27 inorder(node->left);28 printf("%d ", node->value);29 inorder(node->right);30}31
32int countNodes(const Node* node) {33 if (node == NULL) return 0;34 return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38 int values[] = {8, 3, 10, 1, 6, 14, 4};39 Node* root = NULL;40 for (int i = 0; i < 7; i++) root = insert(root, values[i]);41 printf("In-order: ");42 inorder(root);43 printf("\n");44 printf("Node count: %d\n", countNodes(root));45 return 0;46}二叉树常见问题
二叉树和二叉搜索树有什么区别？
二叉树只是限制每个节点最多有两个子节点，没有顺序要求。二叉搜索树额外规定左子树中的值都更小、右子树中的值都更大，正是这条规则让查找变快。
什么是中序遍历？
中序遍历递归地先访问左子树，再访问节点本身，最后访问右子树。对于二叉搜索树，它会按升序输出所有值，这也是它最常被拿来演示的原因。
什么是完全二叉树？
完全二叉树除最后一层外，每一层都是满的，最后一层从左到右填充。这种形状让树可以紧凑地存放在数组中（不需要子节点指针），二叉堆就是这样实现的。
什么时候该用二叉树而不是数组或哈希表？
当数据天然具有层级结构，或者你需要范围查询、有序迭代这类哈希表做不到的有序操作时，就用树。如果只需要按键快速查找、不关心顺序，哈希表平均
O(1) 的访问胜过树；对于扁平数据，数组更简单，对缓存也更友好。二叉树的高度和深度有什么区别？
深度从根节点往下量到某个节点，即从根节点到该节点路径上的边数。高度从某个节点往下量到它最深的叶子节点，所以整棵树的高度等于最深节点的深度。只有一个节点的树高度为
0，这个唯一节点的深度也是 0。为什么不平衡的二叉树性能这么差？
在二叉搜索树中，查找、插入和删除的代价是
O(h)，其中 h 是树的高度。当键按顺序插入时，树会变成一条直线，h 增长到 n，每个操作都退化为 O(n)，并不比链表好。AVL 树、红黑树等自平衡树把高度保持在 O(log n)，从而避免这种情况。相关资源
更多可视化
