引入

前面，我们说过，二叉树的遍历方法，以及如何使用代码创建二叉树并将三种遍历顺序都输出出来。如果你还对单链表有印象，我们会发现上节我们树的创建过程其实就是根结点指向左右子树，很像单链表指向唯一后继，对不对？还记得为什么我们要使用双向链表嘛？因为双向链表在找寻唯一前驱的时候方便。因此，二叉树也遇到了相同的问题，左右子树不知道自己的双亲是谁，我们该怎么解决呢？

问题

现在的二叉树

• 一个结点下，数据域和指针域
• 数据域，存放数据
• 指针域，指向该结点下的左右子树

问题一

如果我要找这个结点的双亲该怎么办呢？

• 麻烦了！我们要重新遍历这个棵二叉树
• 直到遇到这个结点，然后记录它得双亲

问题二

引入

上一节，我们详细说明了二叉树的 4 种遍历方式，根据根的位置不同，我们分为前序遍历、中序遍历和后序遍历以及最常用的层序遍历。今天我们就来实战一下， 看看如何建立一棵树，并且按照我们需要的方式遍历树上的结点。

需求

• 根据输入建立一棵二叉树
• 输出其前序遍历、中序遍历和后序遍历结果

代码分析

首先要构建一棵树，因为是二叉树，所以结构体中包含左右两棵子树

• 存放数据的data
• 存放左右子树的指针域

1
2
3
4
5
6
7
8
9

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

struct BiTNode{
    char data;   //用于存放结点数据
    struct BiTNode *Lchild;   //存放左孩子地址
    struct BiTNode *Rchild;   //存放右孩子地址
};

引入

这节课是二叉树的考试重点，通过什么样的方式遍历二叉树，这里需要把内容搞清楚，不要混淆。

二叉树遍历

二叉树遍历(traversing binary tree)，指的是

• 从根结点出发，按照某种次序
• 依次访问二叉树中的所有结点
• 使得每个结点都被访问一次，且仅有一次。

二叉树跟线性结构的不同

线性结构的便利，最多是

• 顺序
• 循环
• 双向
• 都是简单的遍历方式

树就不一样了

• 树的结点之间不存在唯一的前驱和后继这样的关系
• 一个结点后面会跟着左子树和右子树两个结点，不是唯一的
• 所以下一个结点的选择是不同的

二叉树的遍历方式

如果都是从左到右的话，遍历方式分为 4 种

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

引入

前面，我们学习了二叉树的五大特性，那么既然说了这么久的二叉树，是时候讲一讲二叉树的数据结构该如何定义了。

回顾

如果你忘了之前的内容，点击下面的链接回顾：
数据结构之树-树的存储结构（一）-学习笔记-47
数据结构之树-树的存储结构（二）-学习笔记-47

思考

根据我们之前讨论树的存储结构，我们可以直到，树和结点里面包含的元素可以很灵活，我们甚至可以将链式存储结构跟顺序存储结构结合在一起使用。因为这样表达树这个数据结构才方便。但是

• 二叉树是一种特殊的树，由于它的特殊性，使得
• 顺序存储结构和链式存储结构都可以轻松的实现二叉树

二叉树的顺序存储结构

引入

我们上节课我们讲了三条性质，从层数、层节点数、深度、总结点数、以及度的概念了解了二叉树的一些有趣的性质，今天我们继续看看，二叉树还有什么有趣的特性。

从节点数判断深度，从深度判断节点数

预习一下取整符号：

• $\left \lfloor 这是向下取整符号 \right \rfloor$
• $\left \lfloor 2.4 \right \rfloor=2$ 向下取整到2
• $\left \lceil 2.4 \right \rceil=3$ 向上取整到3

具有 n 个结点的完全二叉树的深度 K 为$\left \lfloor \log_{2}n \right \rfloor+1$

• n 表示完全二叉数的结点数，上面的图中 n=5
• 上图的完全二叉树的深度为：$\left \lfloor \log_{2}5 \right \rfloor+1$
• $2^n=5$然后 n 再加 1。
• $n \approx 2.3$，再加上向下取整$\left \lfloor 2.3 \right \rfloor=2$
• 得到$2+1=3$，这棵完全二叉树有 3 层

引入

我们介绍了树，介绍了树中使用最多的二叉树，以及一些特殊的二叉树。今天我们就来看看二叉树为什么很好的体现了树的特性，二叉树有哪些有趣的特点呢？

每一层最大的节点数

• 在二叉树的第 i 层，至多有$2^{i-1} (i \geq 1)$ 个结点
• 上面这张图中
• 第一层$2^0=1$个结点
• 第二层$2^1=2$个结点
• 第三层$2^2=4$个结点
• 第四层$2^3=8$个结点

引入

我们介绍了什么是二叉树、以及二叉树一些与众不同的特点，例如只能有两个孩子，两个孩子还分为左子树和右子树，那么今天我们来看看特殊的二叉树。

斜树

¡¡™
顾名思义，斜树一定要倾斜。也就是说，一棵树

• 只有左子树
• 只有右子树

这样就不是斜树了。

引入

前面，我们从只能表示父母的双亲表示法，升级到了能同时表示双亲和孩子的双亲父母表示法，在学习孩子兄弟表示法之前，我们先来看看二叉树是什么。

二叉树

树形数据结构有很多种树，但二叉树是使用范围最广的，也最具有代表意义，所以学习树，我们不能不提二叉树。
对于二叉树（Binary Tree），你应该知道

• 二叉树是 n($n \geq 0$)个结点的有限集合
• 如果集合为空，我们就说这是一个空二叉树
• 如果不是空，那就是由两棵互不相交的二叉树组成
• 我们称这两棵树分别是根的左子树和右子树。

这个定义，是一个递归的形式

• 树有一个根
• 根下有两棵树，左子树、右子树
• 两个棵树各自有一个根
• 两个根又都有左子树和右子树。

引入

前面，我们介绍了双亲表示法，每个结点中出了节点的值，还保存了parent的信息。今天我们换个角度，用孩子表示法来看看如何构建树的存储结构。

想一想

现在双亲表示发的问题在哪？

• 只能体现双亲信息和该结点信息
• 没有孩子的信息
• 增加节点内的结构只能增加部分孩子信息，如3个、5个
• 如果某个子节点大量孩子加入，会造成内存空间浪费

想达到什么效果？

• 能体现孩子的信息
• 孩子无论增加多少，都可以只浪费一定的内存空间
• 如果能再包含双亲的信息就更好了！

我们看着这张图，然后想，能不能将链表和顺序存储结构结合起来

引入

前面，我们学习了树的一些基础内容，今天我们就来看看，树有哪些存储结构。说到存储结构我们会想到线性表中的顺序存储结构和链式存储结构，那么树会怎么设计自己的存储结构呢？我们一起来看一看~

树的存储结构

要存储树，用简单的顺序存储结构和链式存储结构都不行。因为树中有双亲、孩子、兄弟这些概念，我们不能用简单的顺序、链式存储结构表达树中各个结点的情况。所以，根据不同的角度，我们有三种存储结构表示一棵树

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

双亲表示法

双亲表示法，顾名思义，就是以双亲作为索引的关键词的一种存储方式。

• 我们先划出一段连续存储空间，类似数组，存储每一个结点
• 在每个结点中，附设一个指示其双亲结点在数组中位置的元素
• 也就是说，每个结点直到自己和自己的双亲

1
2
3
4
5
6
7
8
9
10
11
12

#define MAXTREE 100

struct pt{
int data;  // 结点的数据
int parent;  //每个结点父母的位置，也就是数组下标
};

struct tree{
struct pt pointer[MAXTREE];  //100个包含 pt 结构体的数组
int r;  //根的位置，一般是 0，也就是数组第一个元素
int n;  //结点数目
}