页数：36页文件大小：570.2 KB来源： 数据结构-C#语言描述ppt课件
本课件讲解树形结构这一典型的一对多非线性结构。内容从树的递归定义与四类表示方法入手，梳理结点度、层次、深度等基本术语，进而讲解二叉树的五种基本形态、满二叉树与完全二叉树、顺序与链式三类存储结构，图解先序、中序、后序与广度优先四种遍历，并说明线索二叉树的构造及树、森林与二叉树的相互转换。
本页为第五章树封面。本章讲解树的基本概念、二叉树及其存储结构、二叉树的遍历、线索二叉树，以及树和森林的存储与相互转换。
数据结构中使用树形结构来表示元素间的一对多的关系。
课件以军队编制为例：司令之下辖若干军长，每个军长之下又辖若干师长，上下级之间形成清晰的分支层次，这正是树形结构的典型形态。
树（Tree）是 n（n≥0）个结点（Node）的有限集。在任意一棵非空树中，有且仅有一个特定的称为根（Root）的结点；当 n>1 时，其余结点分成 m（m>0）个互不相交的有限集 T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树。
树的定义是递归的，即在树的定义中又用到了树的概念，它刻画了树的固有特性，即一棵树由若干棵子树构成，而子树又由更小的若干棵子树构成。
同一棵树可以用四种方式表示：
如果树中结点的各子树从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。
图中 (a)(b) 两棵树的结点相同但左右子树次序不同，在有序树的意义下它们是两棵不同的树。
森林为有限棵树的集合。
对树而言，删去其根结点，就得到一个森林；对森林而言，加上一个结点作为根就变为一棵树。这一性质是树、森林与二叉树相互转换的基础。
二叉树的特点是每个结点至多有两棵子树（即二叉树不存在度大于 2 的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒，即如果将其左右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。
因此，二叉树具有五种基本形态：空二叉树、仅有根结点的二叉树、右子树为空的二叉树、左子树为空的二叉树、左右子树非空的二叉树。
在一棵二叉树中，如果所有分支结点都同时具有左孩子和右孩子，并且所有叶子结点都在同一层上，这种树的特点是每层上的结点数是最大结点数，称为满二叉树（Full Binary Tree）。
完全二叉树只允许树的最后一层出现空结点，且最下层的叶子结点集中在树的左部。
显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。图中右侧因最下层叶子未靠左连续排列，属于非完全二叉树。
把一个满二叉树自上而下、从左到右顺序编号，依次存放在数组内。设满二叉树结点在数组中的索引号为 i，那么有如下性质：
图中 (a) 为满二叉树，按层编号后数组下标与结点一一对应，空间利用率最高；(b) 为一般二叉树，缺失的结点在数组中留下空位，仍要占用存储单元。
一个深度为 k 的二叉树需要 2 的 k 次方减 1 个存储空间，因此顺序存储只适合形态接近满二叉树的情形。
二叉树的链式存储结构可分为二叉链表和三叉链表。二叉链表中，每个结点除了存储本身的数据外，还应该设置两个指针域 left 和 right，它们分别指向左孩子和右孩子。
图中给出二叉树与其对应的二叉链表：从 head 出发沿 left、right 指针即可访问整棵树，但无法直接找到双亲。
如果在二叉树中经常需要寻找某结点的双亲，每个结点还可以加一个指向双亲的指针域 parent，这就是三叉链表。
三叉链表的结点含 data、left、right 与 parent 四个域，代价是每个结点多占用一个指针空间。
双亲链表只存储结点的双亲信息而不存储孩子信息。下表给出双亲链表的存储结构：
| 数组下标 | data | parent | tag |
|---|---|---|---|
| 0 | A | -1 | — |
| 1 | B | 0 | L |
| 2 | C | 0 | R |
| 3 | D | 1 | L |
| 4 | E | 1 | R |
| 5 | F | 2 | R |
其中 parent 为 -1 表示根结点，tag 用 L、R 标记该结点是双亲的左孩子还是右孩子。
二叉树遍历（Traversal）就是按某种顺序对树中每个结点访问且只能访问一次的过程。访问的含义很广，如查询、计算、修改、输出结点的值。
树遍历本质上是将非线性结构线性化，它是二叉树各种运算和操作的实现基础。
本页给出二叉树的深度优先遍历路线：沿树的外围走一圈，每个结点被经过三次，分别在第一次、第二次、第三次经过时访问，就得到先序、中序、后序三种遍历序列。
先序遍历过程：
先序遍历中根结点最先被访问，因此得到的序列的第一个元素一定是整棵树的根。
按“根—左—右”的顺序访问，图中二叉树的先序遍历序列为：ABDECF。
先序遍历的特点是第一个访问到的必定是根结点，常用于复制树和输出树形目录。
中序遍历过程：
中序遍历把根结点夹在左右子树之间访问，序列次序为左子树、根、右子树。
按“左—根—右”的顺序访问，图中二叉树的中序遍历序列为：DBEACF。
对二叉查找树做中序遍历，可以得到按关键字递增排列的有序序列。
后序遍历过程：
后序遍历中左右子树的结点一律先于根结点被访问，根结点是序列的最后一项。
按“左—右—根”的顺序访问，图中二叉树的后序遍历序列为：DEBFCA。
后序遍历最后访问根结点，常用于释放整棵树、计算子树规模等需要先处理孩子的场景。
由于二叉树结点分属不同的层次，因此可以从上到下、从左到右依次按层访问每个结点。
它的访问顺序正好和二叉树顺序存储结构中结点在数组中的存放顺序相吻合。图中二叉树使用广度优先遍历访问的顺序为：ABCDEF。
线索二叉树的结点含 data、left、right 及两个标志位 ltag、rtag：
利用标志位可以把遍历中得到的线性前驱后继信息直接存入空的指针域。
图中 (a) 为原二叉树，(b) 为其中序遍历结果 DBEACF，(c) 为线索化后的二叉树。
线索化后，原本为空的指针域改为指向该结点在某种遍历序列中的前驱或后继，从而可以不用递归、不用栈地完成遍历。
在一棵树中，任意一个结点的双亲只有一个，这是由树的定义决定的。双亲表示法正是利用了树的这种性质，在存储结点信息的同时，在每个结点中附设一个指向其双亲的指针，指示双亲在链表中的位置。这种结构一般借助数组来实现，这样的链表也称为静态链表。
| 数组下标 | data | parent |
|---|---|---|
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 0 |
| 4 | E | 1 |
| 5 | F | 1 |
| 6 | G | 1 |
| 7 | H | 3 |
| 8 | I | 3 |
parent 为 -1 表示该结点为根结点。
树的每个结点都有自己的孩子，孩子表示法是指在树的每个结点中设置指针指向该结点的孩子。由于一般树中的结点可能存在多个孩子，因此需要使用链表依次存储结点的所有孩子。
孩子链表的存储结构需同时使用数组和单链表来实现：数组存放各结点，每个结点再挂一条由其孩子组成的单链表。
树的双亲孩子链表表示法把双亲表示法与孩子表示法结合起来：数组中的每个结点既保存其双亲的位置，又通过链表串起它所有的孩子。
这样既能快速找到双亲，也能方便地遍历某个结点的全部孩子。
孩子兄弟表示法在每个结点中设置两个指针域：firstChild 指向该结点的第一个孩子，nextSibling 指向该结点的下一个兄弟，二者与 data 共同构成结点结构。
由于每个结点只有两个指针域，这种表示法可以直接把一般树看成二叉树来处理，是树与二叉树转换的桥梁。
一般树转换为二叉树的步骤如下：
森林转换为二叉树时，先把森林中每一棵树各自转换为二叉树，再把各棵二叉树的根结点依次用右链相连，最后整体旋转即得到一棵二叉树。
转换后，二叉树的根的左子树对应第一棵树的子树，右链上依次挂着其余各棵树。
二叉树还原为一般树是一般树转换为二叉树的逆过程：沿左链把结点恢复为双亲的孩子，沿右链把结点恢复为兄弟关系，旋转后即得到原来的一般树。
将一棵由森林转化得到的二叉树还原为森林的步骤如下：
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}