树与二叉树

概念

树（tree）是 n（n ≥ 0）个结点的有限集合。n = 0 时为空树；非空树满足：有且仅有一个根（root）结点，其余结点分为若干互不相交的子集，每个子集本身又是一棵树（子树）。

二叉树（binary tree）是每个结点最多有两棵子树、且子树有左右之分、次序不可颠倒的树。二叉树与度为 2 的树是两回事：度为 2 的树不区分左右，且结点可以只有一棵子树（此时度为 1）。

一句话区分：树是"层级结构"，二叉树是"每个结点最多两个岔路、且岔路分左右"的有序树。

原理

基本术语

术语	含义
结点的度	该结点拥有的子树个数
树的度	树中结点的最大度数
叶子（终端结点）	度为 0 的结点
分支结点	度不为 0 的结点
深度 / 高度	树中结点的最大层数（通常根算第 1 层）
路径长度	路径上所经过的边的条数
森林	m（m ≥ 0）棵互不相交的树的集合

树的结点数 = 所有结点的度之和 + 1（每条边贡献一个"孩子"，再加根）。

二叉树的五条性质（必背）

性质 1：第 i 层上至多有 $2^{i - 1}$ 个结点（i ≥ 1）。

性质 2：深度为 k 的二叉树至多有 $2^{k} - 1$ 个结点（满二叉树达到上限）。

性质 3：对任何二叉树，若叶子数为 $n_{0}$ 、度为 2 的结点数为 $n_{2}$ ，则

n_{0} = n_{2} + 1

推导：设总结点 n = n₀ + n₁ + n₂；边数 = n − 1 = n₁ + 2n₂（每个结点向下连的边数等于它的度）。两式联立即得。

性质 4：具有 n 个结点的完全二叉树的深度为

⌊ \log_{2} n ⌋ + 1 (或 ⌈ \log_{2} (n + 1) ⌉)

性质 5：完全二叉树按层序从 1 开始编号，对任一结点 i：

若 i = 1，则为根，无双亲；否则双亲为 $⌊ i / 2 ⌋$
左孩子为 $2 i$ （若 $2 i \leq n$ ，否则无左孩子）
右孩子为 $2 i + 1$ （若 $2 i + 1 \leq n$ ，否则无右孩子）

性质 5 就是堆和顺序存储二叉树的数学基础，到堆那一章会直接用。

两种特殊二叉树

类型	定义	特点
满二叉树	每层结点数都达最大值	深度 k 恰有 $2^{k} - 1$ 个结点
完全二叉树	除最后一层外均满，最后一层结点集中在最左边	可用数组紧凑存储，无空洞

存储结构

顺序存储：按层序编号把结点存入数组（下标从 1 起便于套用性质 5）。只适合完全二叉树，普通二叉树会产生大量空洞（数组位置空着但必须留）。

链式存储（主流）：

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

含 n 个结点的二叉链表共有 2n 个指针域，其中 n − 1 个指向孩子，剩下 n + 1 个为空——这 n + 1 个空指针正是线索二叉树要利用的资源。若加一个指向双亲的指针域，就是三叉链表。

遍历：把树变成线性序列

按"访问根"的时机分为三种：

遍历	顺序	典型用途
先序（preorder）	根 → 左 → 右	复制树、求前缀表达式
中序（inorder）	左 → 根 → 右	二叉排序树得到有序序列
后序（postorder）	左 → 右 → 根	释放整棵树、求后缀表达式
层序（level order）	从上到下、从左到右	用队列实现，求树高/宽度

关键结论：先序、中序、后序的访问路径完全相同（都是沿着同一条路线走一圈），区别仅在何时访问根结点。这句话解释了为什么"知道遍历路径 + 访问时机"就能手推序列。

示例

例 1：由遍历序列还原二叉树

已知先序序列 A B D E C F、中序序列 D B E A C F，还原这棵二叉树并写出后序序列。

完整推导过程：

第一步，先序定根：先序第一个是 A，故 A 是整棵树的根。

第二步，中序分左右：在中序 D B E A C F 中，A 左边是 D B E（左子树），右边是 C F（右子树）。

第三步，递归处理左子树：左子树先序 = 先序中去掉根后取前 3 个 = B D E；中序 = D B E。

先序首元素 B → 左子树的根是 B。
中序中 B 左边 D（左孩子），右边 E（右孩子）。

第四步，递归处理右子树：右子树先序 = C F，中序 = C F。

根是 C；中序中 C 左边无元素（无左孩子），右边 F（右孩子）。

第五步，画出树并写后序（左→右→根）：

            A
          /   \
         B     C
        / \     \
       D   E     F

后序：D → E → B → F → C → A，即 D E B F C A。

判据：必须知道中序才能唯一确定一棵二叉树（先序 + 后序不行）。因为中序负责"分左右"，另两个只负责"找根"。

C 语言：二叉链表与四种遍历

#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

/* 按先序序列建树，'#' 表示空结点。例：ABD##E##CF### */
BiTree createByPre(void) {
    char c;
    scanf(" %c", &c);
    if (c == '#') return NULL;
    BiTree t = (BiTree)malloc(sizeof(BiTNode));
    t->data = c;
    t->lchild = createByPre();
    t->rchild = createByPre();
    return t;
}

void preOrder(BiTree t) {
    if (!t) return;
    printf("%c ", t->data);
    preOrder(t->lchild);
    preOrder(t->rchild);
}

void inOrder(BiTree t) {
    if (!t) return;
    inOrder(t->lchild);
    printf("%c ", t->data);
    inOrder(t->rchild);
}

void postOrder(BiTree t) {
    if (!t) return;
    postOrder(t->lchild);
    postOrder(t->rchild);
    printf("%c ", t->data);
}

/* 层序遍历：队列实现 */
void levelOrder(BiTree t) {
    if (!t) return;
    BiTree q[100];
    int front = 0, rear = 0;
    q[rear++] = t;
    while (front < rear) {
        BiTree p = q[front++];
        printf("%c ", p->data);
        if (p->lchild) q[rear++] = p->lchild;
        if (p->rchild) q[rear++] = p->rchild;
    }
}

int main(void) {
    /* 输入：ABD##E##CF### 构造例 1 的树 */
    BiTree t = createByPre();
    preOrder(t);  printf("\n");   /* A B D E C F */
    inOrder(t);   printf("\n");   /* D B E A C F */
    postOrder(t); printf("\n");   /* D E B F C A */
    levelOrder(t);printf("\n");   /* A B C D E F */
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

C 语言：非递归中序遍历（栈模拟递归）

#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode { char data; struct BiTNode *l, *r; } BiTNode;

void inOrderIter(BiTNode *root) {
    BiTNode *stack[100];
    int top = -1;
    BiTNode *p = root;
    while (p || top != -1) {
        while (p) { stack[++top] = p; p = p->l; }   /* 一路向左，全部入栈 */
        p = stack[top--];                            /* 弹栈顶并访问 */
        printf("%c ", p->data);
        p = p->r;                                    /* 转向右子树 */
    }
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

非递归遍历是"递归转栈"的标准范例：外层 while 对应"栈不空或还有路可走"，内层 while 对应"一路向左到底"。

Python 对照

class Node:
    def __init__(self, data, l=None, r=None):
        self.data, self.l, self.r = data, l, r

# 构造例 1 的树
root = Node('A',
            Node('B', Node('D'), Node('E')),
            Node('C', None, Node('F')))

def pre(t):
    return [] if not t else [t.data] + pre(t.l) + pre(t.r)

def mid(t):
    return [] if not t else mid(t.l) + [t.data] + mid(t.r)

def post(t):
    return [] if not t else post(t.l) + post(t.r) + [t.data]

def level(t):
    from collections import deque
    q, out = deque([t]), []
    while q:
        p = q.popleft()
        out.append(p.data)
        if p.l: q.append(p.l)
        if p.r: q.append(p.r)
    return out

print(pre(root), mid(root), post(root), level(root))
# ['A','B','D','E','C','F'] ['D','B','E','A','C','F']
# ['D','E','B','F','C','A'] ['A','B','C','D','E','F']

# n0 = n2 + 1 的验证
def count(t):
    if not t: return 0, 0
    l0, l2 = count(t.l); r0, r2 = count(t.r)
    n0, n2 = l0 + r0, l2 + r2
    if t.l is None and t.r is None: return n0 + 1, n2
    if t.l and t.r: return n0, n2 + 1
    return n0, n2

n0, n2 = count(root)
print(n0, n2, n0 == n2 + 1)     # 3 2 True

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

1. 性质 3 的推广应用（选择/填空高频）

$n_{0} = n_{2} + 1$ 。变形考法：

已知完全二叉树有 n 个结点，求叶子数：完全二叉树中度为 1 的结点最多 1 个（n 为偶数时恰有 1 个）。
若一棵二叉树只有度为 0 和度为 2 的结点（即无度为 1 的结点），则总结点数 $= n_{0} + n_{2} = 2 n_{0} - 1$ ，必为奇数。
满二叉树没有度为 1 的结点；完全二叉树至多一个度为 1 的结点。

2. 遍历序列还原（必考大题小题）

先序 + 中序 → 唯一确定。
后序 + 中序 → 唯一确定（后序最后一个是根）。
层序 + 中序 → 唯一确定。
先序 + 后序 → 不能唯一确定（只有中序能分左右）。

3. 易错点

二叉树与度为 2 的树不同：二叉树可以为空，度为 2 的树至少 3 个结点；二叉树区分左右子树。
完全二叉树 vs 满二叉树：完全二叉树最后一层从左往右连续，出现"左边缺、右边有"就一定不是完全二叉树。
顺序存储只适合完全二叉树；普通二叉树用顺序存储会浪费大量空间。
含 n 个结点的二叉链表有 n + 1 个空指针域（不是 2n − (n−1) 算错）。
三种递归遍历时间复杂度均为 O(n)，空间复杂度 O(h)（h 为树高，来自递归栈）。

小结

树是递归定义的：一棵树 = 根 + 若干棵子树。
二叉树的五条性质中， $n_{0} = n_{2} + 1$ 和完全二叉树的编号关系（性质 5）考得最多。
遍历的本质是"同一条行走路线，不同的访问根时机"；中序负责分左右，因此是还原树的钥匙。
空着的 n + 1 个指针域不要浪费——下一章的线索二叉树正是拿它做文章。

下一篇：线索二叉树

树与二叉树

概念

原理

基本术语

二叉树的五条性质（必背）

两种特殊二叉树

存储结构

遍历：把树变成线性序列

示例

例 1：由遍历序列还原二叉树

C 语言：二叉链表与四种遍历

C 语言：非递归中序遍历（栈模拟递归）

Python 对照

考点

小结

我的笔记

评论（0）

树与二叉树 ​

概念 ​

原理 ​

基本术语 ​

二叉树的五条性质（必背） ​

两种特殊二叉树 ​

存储结构 ​

遍历：把树变成线性序列 ​

示例 ​

例 1：由遍历序列还原二叉树 ​

C 语言：二叉链表与四种遍历 ​

C 语言：非递归中序遍历（栈模拟递归） ​

Python 对照 ​

考点 ​

小结 ​

我的笔记

评论（0）

树与二叉树

概念

原理

基本术语

二叉树的五条性质（必背）

两种特殊二叉树

存储结构

遍历：把树变成线性序列

示例

例 1：由遍历序列还原二叉树

C 语言：二叉链表与四种遍历

C 语言：非递归中序遍历（栈模拟递归）

Python 对照

考点

小结