企业官网建设流程全解析

二叉树这东西，说实话很多人一开始学的时候容易迷，左子树右子树、前中后序遍历，看着挺绕，但等真上手写过几遍完整代码，你会发现它其实是一个非常顺的逻辑结构。这篇笔记我打算从二叉树的基本概念出发，重点讲透它的两种主流存储方式，也就是顺序存储和链式存储，每一种我都会给出完整的代码实现，包括建树、遍历、求深度、统计节点这些常规操作。适合正在学数据结构的学生、准备面试刷题的人，以及工作中需要手写树结构但好久没碰过的同学参考。

1. 二叉树到底解决了什么问题

1.1 先分清楚这些基本术语

在写任何代码之前，先得把二叉树里的几个词捋顺了。二叉树是每个节点最多有两个子节点的树结构，这两个子节点一般叫作左孩子和右孩子，左右是有顺序的，互换一下就变成另一棵树了，这一点和一般的树有明显区别。

节点、根节点、叶子节点这些概念比较基础，我重点说一下容易混淆的“深度”和“高度”。不同的教材定义不完全一样，有的把根节点深度记为 0，有的记为 1。我个人建议参考大部分考研教材和面试中的惯例：深度就是从根节点到该节点经过的边的条数，根节点深度为 0；高度是从该节点到叶子节点的最长路径边的条数，单个节点的树高度为 0。只要自己代码里口径统一，写起来不会出问题，但和别人沟通时最好先确认用的是哪种定义，我踩过这个坑。

还有两个术语必须分清：“度”和“层”。度指一个节点拥有的子节点个数，二叉树的节点度只能是 0、1、2；层数一般从 1 开始，根节点是第一层。搞清楚这些术语，后边理解性质和推导公式会顺畅很多。

1.2 三个必须记住的性质

二叉树有几个性质，考试和面试都喜欢考，代码里也经常用到。

第一个性质：第 i 层最多有 2^(i-1) 个节点，其中 i 从 1 开始。这个很好推导，第一层最多 1 个，第二层最多 2 个，第三层最多 4 个，每层翻倍，所以是等比数列 2^(i-1)。

第二个性质：深度为 k 的二叉树最多有 2^k - 1 个节点。这就是把第一层到第 k 层的最大节点数加起来，等比数列求和，结果等于 2^k - 1。

第三个性质：对于任意非空二叉树，叶子节点数 n0 和度为 2 的节点数 n2 满足 n0 = n2 + 1。这个证明思路值得说一说。假设总节点数 n = n0 + n1 + n2，其中 n1 是度为 1 的节点数。再看边的数量，除了根节点外每个节点都有一条边连着父节点，所以总边数是 n - 1。从另一个角度看，度为 1 的节点贡献 1 条出边，度为 2 的节点贡献 2 条出边，于是 n1 + 2*n2 = n - 1。联立两个式子，就能推出 n0 = n2 + 1。

这个性质在做选择题和算法题时非常有用，比如给定完全二叉树的节点总数，可以快速推出叶子节点的个数范围。

1.3 满二叉树、完全二叉树、二叉排序树

实际使用中最常遇到的几种二叉树形态得搞清楚。

满二叉树是每一层节点都达到最大数量，也就是深度为 k 时正好有 2^k - 1 个节点。这种树的形状非常整齐，适合用数组来存。

完全二叉树稍微宽松一点：除了最后一层，其他层都是满的，并且最后一层的节点都连续地集中在左侧。这个“从左往右连续分布”是判断完全二叉树的核心标准。为什么要费劲定义这种形态？因为它恰好适合顺序存储，父节点和子节点的下标关系非常干净，后面我写顺序存储代码就是基于这个特点。

二叉排序树（也叫二叉搜索树）则是把数据的顺序关系利用起来：左子树所有节点的值都小于根节点，右子树所有节点的值都大于根节点。查找效率在平衡的情况下能达到 O(log n)，这也是二叉树在工程里最广泛的应用场景之一。

2. 存储方式：不同存法背后的账本

2.1 顺序存储：数组的直白与空间陷阱

顺序存储的思路很直接：用一个一维数组来记录二叉树的所有节点，然后通过下标关系找到某个节点的左孩子、右孩子和父节点。

以下标从 1 开始为例，某个节点在数组中的下标为 i，那么它的左孩子下标是 2i，右孩子下标是 2i + 1，父节点下标是 i/2 向下取整。如果用下标从 0 开始，左孩子就是 2i + 1，右孩子是 2i + 2，父节点是 (i-1)/2。我习惯用从 1 开始的版本，因为计算式更干净，有时候题目也默认这套规则。

这种存储方式的优点非常明显：结构简单，存完全二叉树时几乎没有空间浪费，还能通过下标快速跳转到任意位置的父节点和子节点，缓存命中率也高。

但它也有一个很大的坑：对于普通二叉树，尤其是只有右子树不断延伸的退化树，数组里会留下大量空闲位置，因为你要为不存在的左子树保留空间。极端情况下，一个深度为 k 的“斜树”用数组存储，需要 2^k - 1 个位置，却只放了 k 个节点，空间浪费极其严重。

提示：所以顺序存储基本只用于完全二叉树，或者节点数量不大、形态接近完全的二叉树。如果你的树是随意建的，动不动就缺左孩子缺右孩子，老老实实走链式存储。

2.2 链式存储：最主流的二叉链表

链式存储把每个节点设计成一个小结构体，里面保存数据，外加两个指针，分别指向左孩子和右孩子，这种结构叫二叉链表。

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

这种存法摆脱了数组下标的限制，任意形态的二叉树都能自然表示，插入和删除节点只需要改几个指针，非常灵活。它的缺点是每个节点要额外存两个指针，内存开销比纯数组大，而且查找父节点比较麻烦，因为节点本身没有记录父节点是谁。

链式存储还有一个有趣的数学结论：n 个节点的二叉链表里，总共有 2n 个指针域，其中真正用来指向孩子的指针是 n-1 个，因此空指针域有 n+1 个。这些空指针后来被“线索二叉树”利用起来，用来加速遍历，这个我后边单独讲。

2.3 进阶存储：三叉链表与线索二叉树

如果经常需要从某个节点回溯到它的父节点，二叉链表就不够用了。三叉链表在节点里再加一个 parent 指针，指向上级节点，这样向上向下都能走，代价是存储空间进一步增加。

另一个进阶方案是线索二叉树，它的核心思路是复用空指针域。叶子节点的左右指针本来都是空的，我们可以把左空指针指向某种遍历序列中的“前驱节点”，把右空指针指向“后继节点”。前序、中序、后序都可以做线索化，但最常用的是中序线索化，因为中序遍历的结果是有序的。

做线索化时，需要一个全局变量 pre 记录上一次访问的节点。如果当前节点左指针为空，就把左指针指向 pre；如果 pre 的右指针为空，就把 pre 的右指针指向当前节点。为了避免指针方向混淆，还需要加两个标志位来区分指针是指向孩子还是指向前驱/后继。

typedef struct ThreadNode { char data; struct ThreadNode *lchild, *rchild; int ltag, rtag; // 0表示指向孩子，1表示指向前驱/后继 } ThreadNode, *ThreadTree;

线索化的好处是遍历时不需要递归，也不需要显式栈，只要沿着线索往后走就行，时间复杂度和空间复杂度都很理想。代价是建树和维护线索的逻辑变复杂，日常大多数场景用不到，但面试中偶尔会考到原理。

2.4 如何选：一张表讲清

不同存储方式没有绝对的好坏，关键看场景。我整理了一张对照表，方便你在写代码前快速决策。

如果你只是单纯学习二叉树，链式存储是最推荐的，后边我的代码也以它为核心。

3. 完整代码实现：用C语言从零建一棵二叉树

3.1 节点定义与前序建树

我在这一节会用 C 语言演示一套完整的链式存储实现，包括建树、遍历和统计操作。C 的指针操作最贴近二叉树存储的本质，理解了 C 版本，再看其他语言的实现会容易很多。

建树的方式很多，最常用的是通过扩展的前序遍历序列来建树：把空子树用特殊符号#表示。比如序列A B # # C # #表示根节点 A，左孩子 B（B 的左右孩子都是空），右孩子 C（C 的左右孩子都是空）。建树过程递归进行，读取一个字符，如果不是#，就创建节点，然后递归创建左子树和右子树。

#include <stdio.h> #include <stdlib.h> typedef struct BiTNode { char data; struct BiTNode *lchild; struct BiTNode *rchild; } BiTNode, *BiTree; // 用扩展前序序列建树，#表示空 BiTree CreateTree() { char ch; scanf(" %c", &ch); if (ch == '#') { return NULL; } BiTree T = (BiTree)malloc(sizeof(BiTNode)); T->data = ch; T->lchild = CreateTree(); T->rchild = CreateTree(); return T; }

有人问为什么要用扩展前序序列，而不是直接用标准的前序序列？因为标准前序序列无法唯一确定一棵二叉树，只有补上所有空位置变成扩展序列，递归才能知道什么时候该停。这个思路在序列化和反序列化二叉树时也会用到。

3.2 三种递归遍历：前序、中序、后序

前中后序遍历指的是根节点被访问的时机：前序是先访问根，再递归访问左子树，最后右子树；中序是左子树、根、右子树；后序是左子树、右子树、根。

代码结构几乎一模一样，区别只是 visit 的位置：

void PreOrder(BiTree T) { if (T != NULL) { printf("%c ", T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(BiTree T) { if (T != NULL) { InOrder(T->lchild); printf("%c ", T->data); InOrder(T->rchild); } } void PostOrder(BiTree T) { if (T != NULL) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%c ", T->data); } }

这三段代码看似简单，但它是理解递归遍历的根基。你要关注的不是代码本身，而是递归调用时的“执行栈”：每次递归调用都会把当前现场保存到系统栈里，等子树处理完再弹出来继续。这也是后边非递归遍历要手动维护栈来模拟的东西。

3.3 层序遍历：队列的经典用法

层序遍历是按“从上到下、从左到右”的顺序逐层访问节点。它和深度优先遍历的思路完全不同，要用队列实现。

算法流程：先把根节点入队，然后循环处理，每次从队首取出一个节点访问它，再把它的左孩子和右孩子依次入队。因为队列是先进先出，所以同一层的节点会按顺序被访问完，然后才轮到下一层。

#include <stdbool.h> // 假设队列已经实现好，这里只写核心逻辑 void LevelOrder(BiTree T) { if (T == NULL) return; BiTree queue[100]; // 简化处理，实际可用动态队列 int front = 0, rear = 0; queue[rear++] = T; while (front < rear) { BiTree p = queue[front++]; printf("%c ", p->data); if (p->lchild != NULL) { queue[rear++] = p->lchild; } if (p->rchild != NULL) { queue[rear++] = p->rchild; } } }

层序遍历在很多算法题里是基础操作，比如求二叉树最大宽度、按层打印、判断完全二叉树，都是在层序遍历框架上加一些统计逻辑。

3.4 核心统计操作：深度、节点数、叶子数

这几个操作是二叉树最常问的“基础能力”，实现起来也适合用来检验对递归的理解。

求树的高度/深度，典型做法是递归：如果树为空，深度为 0；否则深度等于左子树深度和右子树深度中的较大值再加 1。

int TreeDepth(BiTree T) { if (T == NULL) return 0; int leftDepth = TreeDepth(T->lchild); int rightDepth = TreeDepth(T->rchild); return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; }

求节点总数也很直观：空树为 0，否则节点数等于左子树节点数加右子树节点数再加 1。

int CountNode(BiTree T) { if (T == NULL) return 0; return CountNode(T->lchild) + CountNode(T->rchild) + 1; }

统计叶子节点数时，判断条件要清楚：一个节点是叶子，当且仅当左右孩子都为空。

int CountLeaf(BiTree T) { if (T == NULL) return 0; if (T->lchild == NULL && T->rchild == NULL) return 1; return CountLeaf(T->lchild) + CountLeaf(T->rchild); }

这三个操作的共同点是：把大问题拆成左右两个子问题，再把子问题的结果合并。二叉树的很多算法题走的都是这个套路，熟练之后你会发现万变不离其宗。

4. 进阶代码：非递归遍历与还原二叉树

4.1 非递归遍历：手写栈把递归吃透

递归好写，但有隐患。当二叉树退化成一条链时，递归深度等于节点数，如果节点很多，很容易把系统栈打爆。非递归遍历就是用显式的栈模拟系统栈的行为，常见的有两种思路。

先看中序非递归，这是最经典的一个。核心逻辑：从根节点开始，一路向左把节点压栈；当走到空节点时，弹出栈顶节点并访问它，然后转向该节点的右子树，重复这个过程。

void InOrderNonRec(BiTree T) { BiTree stack[100]; int top = -1; BiTree p = T; while (p != NULL || top >= 0) { if (p != NULL) { stack[++top] = p; p = p->lchild; } else { p = stack[top--]; printf("%c ", p->data); p = p->rchild; } } }

前序非递归的代码和中序很接近，区别只是访问时机。你可以在压栈之前先访问根节点，这样节点顺序就是“根左右”。

后序非递归稍微麻烦，因为要等左右子树都访问完才能访问根，需要额外记录上一个访问的节点，或者给每个节点加一个“是否已访问右子树”的标记。

void PostOrderNonRec(BiTree T) { BiTree stack[100]; int top = -1; BiTree p = T; BiTree lastVisited = NULL; while (p != NULL || top >= 0) { if (p != NULL) { stack[++top] = p; p = p->lchild; } else { BiTree peek = stack[top]; if (peek->rchild != NULL && peek->rchild != lastVisited) { p = peek->rchild; } else { printf("%c ", peek->data); lastVisited = peek; top--; } } } }

这套代码的难点是理解lastVisited的作用：它用来判断右子树是否已经处理过。如果右孩子存在且没有被访问过，就先去处理右子树；否则说明左右子树都处理完了，才能弹出并访问根节点。

注意：非递归遍历的空间复杂度和递归一样都是 O(n)，实际运行却不一定会更快，因为手动栈操作有额外开销。它最大的价值在于避免系统栈溢出，以及让你真正搞懂遍历的顺序是怎么来的。

4.2 由前序+中序还原二叉树

在面试和学习中经常遇到这样一道题：给出前序序列和中序序列，还原整棵二叉树。原理很简单，但自己写代码时容易在下标边界上出错。

思路是：前序序列的第一个元素一定是根节点；在中序序列中找到这个根节点的位置，它左边的是左子树的中序序列，右边的是右子树的中序序列；根据中序左右子树的长度，把前序序列也切成左子树和右子树两段；然后递归还原。

BiTree BuildByPreIn(char pre[], int preL, int preR, char in[], int inL, int inR) { if (preL > preR) return NULL; BiTree T = (BiTree)malloc(sizeof(BiTNode)); T->data = pre[preL]; int k = inL; while (in[k] != pre[preL]) k++; int leftCount = k - inL; // 左子树节点个数 T->lchild = BuildByPreIn(pre, preL + 1, preL + leftCount, in, inL, k - 1); T->rchild = BuildByPreIn(pre, preL + leftCount + 1, preR, in, k + 1, inR); return T; }

用前序序列A B D E C和中序序列D B E A C来试。根是 A，中序里 A 左边是D B E，右边是C，说明左子树有 3 个节点，右子树有 1 个节点。前序里 A 后面紧跟的 3 个元素B D E就是左子树的前序，C是右子树的前序。递归还原后得到：

A / \ B C / \ D E

中序 + 后序也能还原，思路类似。但前序 + 后序不行，因为无法区分左右子树，树形会有歧义。这是一个高频易错点，我建议专门记一下。

5. 工程实践：Python版本与调试心得

5.1 Python版本：面试和刷题更常用

C 语言版适合理解原理，但实际刷题或者工作里，Python 的简洁写法更常用。我用 Python 重新实现一遍核心逻辑，你会发现结构其实一模一样，只是指针换成了对象引用。

class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def build_tree(seq): """根据扩展前序序列构建二叉树，'#' 表示空节点""" if not seq: return None val = seq.pop(0) if val == '#': return None root = TreeNode(val) root.left = build_tree(seq) root.right = build_tree(seq) return root def preorder(root): if root is None: return [] return [root.val] + preorder(root.left) + preorder(root.right) def inorder(root): if root is None: return [] return inorder(root.left) + [root.val] + inorder(root.right) def postorder(root): if root is None: return [] return postorder(root.left) + postorder(root.right) + [root.val] def level_order(root): if root is None: return [] result = [] queue = [root] while queue: node = queue.pop(0) result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result

Python 版本里有个小坑要注意：build_tree里用了seq.pop(0)，会直接修改传入的列表。在测试时，你需要确保调用前序列是可变且不会被其他代码共享的状态，否则会拿到意外结果。

5.2 调试二叉树的三板斧

我自己在学习和调二叉树代码时，总结了三件非常好用的工具，强烈建议你用起来。

第一个是“带空标记的先序输出”。写一个专门用于调试的函数，把空孩子也打印出来：

def debug_print(root): if root is None: print('#', end=' ') return print(root.val, end=' ') debug_print(root.left) debug_print(root.right)

这个函数能把你构建的树完整输出成一个唯一的“序列化”字符串，可以用来验证建树是否正确，也可以作为树的回文校验手段。

第二个是“层序输出带层数”。层序遍历时，把每一层的节点括在一起打印，能够非常直观地看到树的总体形状。

def debug_level(root): if not root: return queue = [root] while queue: size = len(queue) for _ in range(size): node = queue.pop(0) print(node.val, end=' ') if node.left: queue.append(node.left) if node.right: queue.append(node.right) print() # 每一层换行

第三个是“先用小树练手”。我强烈建议测试时从空树、单节点树、完全二叉树、只有左子树的退化链状树这四类用例开始。空树和单节点树能查边界条件，完全二叉树能验证层序逻辑，退化链状树能验证递归是否会爆栈。

5.3 常见问题速查表

我把二叉树学习和代码实现中容易踩的坑整理成一张速查表，方便你写代码时对照自查。

关于判断完全二叉树，我再多说一句。正确的做法是层序遍历，遇到第一个空节点后设置一个标记，如果标记已设置且后面又出现非空节点，说明这不是完全二叉树。很多人在这一步卡住，是因为只判断了空节点的位置，没有做“标记后检查”的处理。

最后分享一个我自己的习惯：写二叉树的递归函数时，第一行永远写递归出口，也就是判空返回的语句，然后才写递归逻辑。这样能避免一半的野指针和空引用问题。每次写完代码，先用最小测试用例跑一遍，再逐渐叠加树的高度，确认没有隐藏问题。这个习惯帮我省了很多排查时间，也让我在面试时写树上代码更加从容。