数据结构：树，二叉树_数据关系r:若d为空集 则称为空树

1 树

1.0 基本概念

树是n（$n\ge 0$）个结点的有限集合T。当n=0时，称为空树，当n>0时，该集合满足如下条件：

• 其中必有一个称为根(root)特定结点，没有直接前驱，但有零个或多个直接后继。
• 其余n-1个结点可以划分为m个互不相交的有限集$T_1,T_2,...,T_m$，其中$T_i$又是一棵树，称为根root的子树，每棵子树的根结点有且仅有一个前驱，但有零个或多个直接后继。

1.2 示意图

图1.0 树结构示意图

1.3 引申概念

1.4 树的抽象数据类型

数据对象D：一个集合，该集合中所有元素具有相同的特性
数据关系R：若D为空集，则为空树，若D中仅含一个数据元素，则R为空集，否则R={H}，H是如下的二元关系：

• 在D中存在唯一的称为根的数据元素root，在关系H下没有前驱；
• 除root外，D中每个节点在关系H下有且仅有一个前驱；

1.5 树的基本操作

2 二叉树

2.1 概念

满足以下两个条件的树型结构称为二叉树(Binary Tree)。

• 每个结点的度都不大于2
• 每个结点的孩子结点次序不能任意颠倒

2.2 二叉树结构

二叉树有如下4种结构:

图2.1 二叉树结构

2.3 基本操作

2.4 二叉树性质

• 二叉树的第i层上至多有$2^{i-1}$个结点，$i\ge 1$；
• 深度为k的二叉树，最多有$2^k-1$个结点；
• 对任意一颗二叉树T，若终端结点数为$n_0$，度数为2的结点数为$n_2$，则$n_0=n_2+1$
• 具有n个结点的完全二叉树深度为${\log }_{2}n+1$;
• 满二叉树：深度为k且共有$2^k-1$个结点的二叉树，每层结点都是满的，即每层结点都具有最大结点数；
  

图2.2 满二叉树

• 完全二叉树：除最后一层外，其余层均满；
  

图2.3 完全二叉树

2.5 二叉树存储结构

二叉树的结构是非线性的,每一个结点最多可有两个后继,二叉树有两种存储结构:顺序存储结构和链式存储结构.

2.5.1 顺序存储结构

用一组连续的存储单元来存放二叉树的数据元素.

图2.4 二叉树顺序存储

• 顺序存储

• 单支树
  对于一般的二叉树,必须按照完全二叉树的形式来存储,这样会造成空间的浪费,单支树是一个极端情况.
  

图2.5 单支树

2.5.2 链式存储结构

对于任意的二叉树来说,每个结点只有两个孩子,一个双亲结点,可以设计每个结点至少包括三个域:数据域,左孩子域和右孩子域.

图2.5 链式存储数据结构

图2.6 链式存储

2.5.3 三叉链表

图2.7 三叉链表树结构

2.6 二叉树的遍历与线索化

2.6.1 二叉树的遍历规定

按一定规律对二叉树中的每个结点进行访问且仅访问一次.二叉树结构如图2.5所示,现定义如下:

• 遍历规定

根据对根的访问顺序,分别规定先序遍历(先根遍历),中序遍历(对称遍历)和后序遍历;

2.6.2 遍历

图2.7 二叉树结构

• 说明

• 遍历结果
  先序遍历DLR:
  $$A\mapsto B\mapsto D\mapsto F\mapsto G\mapsto C\mapsto E\mapsto H$$
  中序遍历LDR:
  $$B\mapsto F\mapsto D\mapsto G\mapsto A\mapsto C\mapsto E\mapsto H$$
  后序遍历LRD:
  $$F\mapsto G\mapsto D\mapsto B\mapsto H\mapsto E\mapsto C\mapsto A$$
• 遍历过程
  先序遍历
  

图2.8 先序遍历过程 更新ing

---

【参考文献】
[1]https://wenku.baidu.com/view/57d26d1ab80d6c85ec3a87c24028915f804d84be.html?from=search
[2]https://wenku.baidu.com/view/c74bb0184693daef5ff73dc9.html?from=search