企业官网建设流程全解析

摘要：本文是数据结构系列中关于树与二叉树的入门讲解。文章先介绍树的基本概念——一种非线性的层次结构，由根节点和互不相交的子树递归定义，并梳理了父节点、度、层次、高度等核心术语，以及「左孩子、右兄弟」的孩子兄弟表示法。随后重点讲解最常用的二叉树：每个节点最多两个孩子且左右有序，并区分了满二叉树（每层都满，2 K − 1 2^K-12K−1个节点）与完全二叉树（除最后一层外全满、最后一层从左到右连续）两种特殊形态。文章还推导了二叉树的关键性质（如n 0 = n 2 + 1 n_0=n_2+1n0​=n2​+1），并对比了顺序存储（数组，适合完全二叉树，下标可算父子关系）与链式存储（二叉链/三叉链，适合任意形状）两种存储结构的适用场景与取舍。

1. 树

1.1 概念与结构

前面五篇讲的都是线性表：元素一个挨一个排成一条线，每个元素最多一个前驱、一个后继。这一篇开始换一种数据结构——树。它是非线性的：一个节点可以有多个后继，于是元素之间不再是一条线，而是一层一层的层次关系。

树：由 n（n ≥ 0）个有限节点组成的一个具有层次关系的集合。它叫「树」，是因为画出来像一棵倒挂的树——根朝上，叶朝下。

• 有一个特殊的节点，称为根节点，它没有前驱；
• 除根节点外，其余节点被分成 M（M > 0）个互不相交的集合 T1、T2、……、Tm，其中每个集合又是一棵结构与树类似的子树。

第二条里藏着树最重要的特征：树是递归定义的——一棵树由根加上若干棵子树构成，而每棵子树本身又是树。后面讲遍历时会看到，树的几乎所有操作都是「先处理根，再对每棵子树做同样的事」。

树形结构里，子树之间不能有交集，否则就不是树形结构了——下面左图那种「两个父节点共用一个孩子」的情况，已经越出了树的定义：

三条关键性质

• 子树是不相交的（一旦相交，就变成「图」了）；
• 除根节点外，每个节点有且仅有一个父节点；
• 一棵有 N 个节点的树，恰好有N − 1 条边。

最后一条很好理解：除根以外的每个节点，都有且仅有一条边把它和父节点连起来。

1.2 相关术语

树的术语比较多，但都很好记——大部分借用了家谱里的说法：

几个容易混的点

• 节点的度和树的度：前者是单个节点有几个孩子，后者是全树的最大值；
• 层次从 1 开始数，所以「高度为 4」和「有 4 层」是同一件事；
• 叶子只看「有没有孩子」，与它在第几层无关。

1.3 树的表示

线性表存起来很省心：一块连续空间（或一串节点）就是全部。树就麻烦了——既要存值，又要存节点之间的关系。常见的表示法有双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等，这里只介绍最常用的孩子兄弟表示法。

思路是「左孩子、右兄弟」：每个节点只保留两个指针，一个指向第一个孩子，一个指向右边的下一个兄弟。

typedefstructTreeNode{structTreeNode*child;// 左边开始的第一个孩子节点structTreeNode*brother;// 指向其右边的下一个兄弟节点intdata;// 节点中的数据域}TreeNode;

这样任意一棵树都能用二叉链表存下来：顺着child往下走是「进入下一层」，顺着brother往右走是「在同一层里找下一个兄弟」。

1.4 树形结构的实际应用

树不是抽象玩具，它就在你每天用的系统里。最典型的是文件系统：目录层层嵌套，正是一棵树。

除了文件系统，公司组织架构、网页的 DOM 树、编译器的语法树、数据库的索引，底层都是树形结构。

2. 二叉树

2.1 概念与结构

树的分支可以很多，研究起来太发散，于是我们限制一下：每个节点最多两个孩子。这就是用得最多的树形结构——二叉树。

二叉树：节点的有限集合，该集合或者为空，或者由一个根节点加上两棵分别称为左子树和右子树的二叉树组成。

这个定义本身就是递归的：二叉树 = 根 + 左子树（二叉树）+ 右子树（二叉树）。它有两条必须记住的特点：

1. 二叉树不存在度大于 2的节点；
2. 二叉树的子树有左右之分，次序不能颠倒——所以二叉树是有序树。

第 2 条经常被忽略：只有右孩子、和只有左孩子，是两棵不同的二叉树。

任意一棵二叉树，都是由下面五种基本形态复合出来的——写递归代码时，它们正好对应「空树返回」和「处理左右子树」两个分支：

2.2 特殊的二叉树

2.2.1 满二叉树

满二叉树：每一层的节点数都达到最大值。

换句话说，如果二叉树的层数为 K，节点总数是2 K − 1 2^K - 12K−1，它就是满二叉树——每一层都「塞满了」，没有任何空位。

2.2.2 完全二叉树

完全二叉树：深度为 K、有 n 个节点的二叉树，当且仅当它的每一个节点都与深度为 K 的满二叉树中编号从 1 至 n 的节点一一对应。

说人话就是：除了最后一层，上面每层都是满的；最后一层的节点从左到右连续排列，中间不能空。

完全二叉树的三条性质：

1. 除了最后一层，每层节点数都达到最大；
2. 最后一层的节点数不一定达到最大；
3. 最后一层的节点从左到右依次排列，不允许中间缺位。

满二叉树是特殊的完全二叉树
满二叉树一定满足「除最后一层外全满、最后一层连续」；反过来不成立——完全二叉树允许最后一层不满。所以「满二叉树 ⊂ 完全二叉树」，这个包含关系在判断类题目里经常用到。

2.3 二叉树的性质

这些性质不用死记，理解「每层最多翻倍」就能推出来。下面的层次都规定根节点为第 1 层：

第 4 条推导只用两个等式——按节点数和按边数各数一遍：

设度为 0、1、2 的节点数分别是n 0 n_0n0​、n 1 n_1n1​、n 2 n_2n2​。

• 按节点数：n = n 0 + n 1 + n 2 n = n_0 + n_1 + n_2n=n0​+n1​+n2​；
• 按边数：树的边数一定是n − 1 n-1n−1（1.1 节的性质）；另一方面，每条边都从某个节点「向下」连到自己的孩子，度为 1 的节点贡献 1 条边、度为 2 的贡献 2 条，所以边数= n 1 + 2 n 2 = n_1 + 2n_2=n1​+2n2​。

两式联立：

n 0 + n 1 + n 2 − 1 = n 1 + 2 n 2 ⟹ n 0 = n 2 + 1 n_0+n_1+n_2-1=n_1+2n_2 \;\Longrightarrow\; n_0=n_2+1n0​+n1​+n2​−1=n1​+2n2​⟹n0​=n2​+1

图中的例子两种数法都对得上：2 × 3 + 1 = 7 2\times3+1=72×3+1=7，而3 + 1 + 4 − 1 = 7 3+1+4-1=73+1+4−1=7。只要知道n 2 n_2n2​（或者知道总节点数），n 0 n_0n0​就能直接算出来。

2.4 二叉树的存储结构

二叉树一般可以用两种结构存储：顺序结构和链式结构。

2.4.1 顺序结构

顺序结构就是用数组存：把节点按「完全二叉树」的层序依次放进数组，根放在下标 0，然后一层一层、从左到右排下去。

因为数组下标是算出来的，父子关系不需要额外存——按下标就能直接跳到孩子或双亲（图中根在下标 0）：

两套编号，别混用
上面的公式是「根在下标 0」这一套；如果按「根编号为 1」来记，关系式会变成孩子2 i 2i2i、2 i + 1 2i+12i+1，父节点⌊ i / 2 ⌋ \lfloor i/2 \rfloor⌊i/2⌋。两套只差一个偏移量，同一段代码里只能用一套，否则算出来的下标会整体错位。

顺序存储的代价在空间上：数组必须按「满二叉树的编号」预留位置，所以它只适合完全二叉树。一旦树不完整，中间就会留下大量空位：

图中的树只有 6 个节点，却占了 10 个位置，空了下标 3、6、7、8 四处。更极端的情况是「只有右孩子的斜树」：h hh层的树只有h hh个节点，却要2 h − 1 2^h-12h−1个位置——指数级的浪费。

「堆」就是顺序存储的二叉树
现实中我们通常把堆（一种特殊的完全二叉树）用顺序结构的数组来存储，这也正是顺序结构最主流的用途。注意别和操作系统里那个「堆」混了：一个是数据结构，一个是管理内存的一块区域，只是名字撞了。

2.4.2 链式结构

链式结构用链表表示一棵二叉树：每个节点由三个域组成——数据域 + 左指针域 + 右指针域，两个指针分别指向左孩子和右孩子所在的节点。

链式结构又分二叉链和三叉链：二叉链只有左右两个指针，三叉链再多一个指向双亲的指针（后面的红黑树等结构会用到）。

三叉链多出来的「双亲指针」，换来的是「向上走」的能力：二叉链里想找父节点只能从根重新遍历，三叉链可以直接沿着双亲指针上去。代价是每个节点多一个指针，维护时也要多改一处。

2.5 两种存储结构怎么选

一句话：形状「满」就用数组，形状「随意」就用链表。

3. 小结

• 树是非线性的层次结构：一个根、互不相交的子树，递归定义；N 个节点恰好 N − 1 条边。
• 术语里最容易混的是节点的度 vs 树的度、层次 vs 高度；记牢「除根外每个节点只有一个父节点」这条，很多判断题就能反推。
• 二叉树是最常用的树：每个节点最多两个孩子，且左右有序，不是「有孩子就行」。
• 满二叉树每一层都满（2 K − 1 2^K-12K−1个节点）；完全二叉树只要求「除最后一层外全满、最后一层从左到右连续」，满二叉树是它的特例。
• 五个性质里最常考n 0 = n 2 + 1 n_0=n_2+1n0​=n2​+1，推导靠「按节点数」和「按边数」两个等式联立。
• 顺序存储用数组按层序放节点，下标就能算出父子关系（根在 0：左2 i + 1 2i+12i+1、右2 i + 2 2i+22i+2、父⌊ ( i − 1 ) / 2 ⌋ \lfloor (i-1)/2\rfloor⌊(i−1)/2⌋），但只适合完全二叉树；链式存储（二叉链 / 三叉链）能表示任意形状，代价是每个节点两个指针。
• 接下来会有两篇文章分别实现顺序结构二叉树（堆）与链式结构二叉树。