计算机软件技术基础 数据结构与算法（4）.

Presentation on theme: "计算机软件技术基础 数据结构与算法（4）."— Presentation transcript:

1 计算机软件技术基础 数据结构与算法（4）

2 数据结构研究的内容

3 2.4 树和二叉树 特点：非线性结构，一个直接前驱，但可能有多个直接后继。 （一对多或1:n） 2.4.1 树的基本概念 2.4.2 二叉树
树的基本概念 二叉树 遍历二叉树

4 树的基本概念 由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。 注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是树”的说法，但现在树的定义已修改。 注2：树的定义具有递归性，即“树中还有树”。

5 若干术语 根 叶子 森林 有序树 无序树 ——即根结点(没有前驱) ——即终端结点(没有后继)
A B C G E I D H F J L K 若干术语 根 叶子 森林 有序树 无序树 ——即根结点(没有前驱) ——即终端结点(没有后继) ——指m棵不相交的树的集合(例如删除A后的子树个数) ——结点各子树从左至右有序，不能互换（左为第一） ——结点各子树可互换位置。 双亲 孩子 兄弟 堂兄弟 祖先 子孙 ——即上层的那个结点(直接前驱) ——即下层结点的子树的根(直接后继) ——同一双亲下的同层结点（孩子之间互称兄弟） ——即双亲位于同一层的结点（但并非同一双亲） ——即从根到该结点所经分支的所有结点 ——即该结点下层子树中的任一结点

6 ——从根到该结点的层数（根结点算第一层） ——即度为0的结点，即叶子 ——即度不为0的结点（也称为内部结点）
A B C G E I D H F J L K 结点 结点的度 结点的层次 终端结点 分支结点 ——即树的数据元素 ——结点挂接的子树数 （有几个直接后继就是几度，亦称“次数”） ——从根到该结点的层数（根结点算第一层） ——即度为0的结点，即叶子 ——即度不为0的结点（也称为内部结点） 树的度 树的深度 (或高度) ——所有结点度中的最大值（Max{各结点的度}） ——指所有结点中最大的层数（Max{各结点的层次}） 问：右上图中的结点数＝ ；树的度＝ ；树的深度＝ 13 3 4

7 树的逻辑结构 特点： 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。 树的物理结构 一般树（即多叉树）的物理结构比较复杂，而且运算也很难实现。 解决方法： 将多叉树转化为等价的二叉树。

8 2.4.2 二叉树 为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强；
二叉树 为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。 1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构

9 1. 二叉树的定义 定义：是n（n≥0）个结点的有限集合，或者是（n=0），或者是由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构：一对二（1:2） 基本特征: ① 每个结点最多只有两棵子树（不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒。 基本形态： 问：具有3个结点的二叉树可能有几种不同形态？ 有5种。

10 性质1: 在二叉树的第i层上至多有2i-1个结点（i>0）。 性质2: 深度为k的二叉树至多有2k-1个结点（k>0）。
2. 二叉树的性质 (3+2) 2i-1个 讨论1：第i层的结点数最多是多少？ （利用二进制性质可轻松求出） 性质1: 在二叉树的第i层上至多有2i-1个结点（i>0）。 再提问：第i层上至少有 个结点？ 1 2k-1个 讨论2：深度为k的二叉树，最多有多少个结点？ （利用二进制性质可轻松求出） 性质2: 深度为k的二叉树至多有2k-1个结点（k>0）。

11 性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）
讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？ 性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1） 物理意义：叶子数＝2度结点数＋1 证明： ∵ 二叉树中全部结点数 n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数) 又∵二叉树中全部结点数 n＝B+1 ( 总分支数＋根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支） 而 总分支数 B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个) 三式联立可得： n0+n1+n2= n1+2n2 +1, 即 n0=n2+1

12 对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：
性质4: 具有n个结点的完全二叉树的深度必为log2n＋1 证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间， 即 2k-1-1<n≤2k-1 或2k-1≤n<2k 三边同时取对数，于是有：k-1≤log2n<k 因为k是整数，所以k= log2n +1 性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。 可根据归纳法证明。

13 满二叉树：一棵深度为k 且有2k -1个结点的二叉树。 （特点：每层都“充满”了结点）
A O B C G E K D J F I H N M L 深度为4的满二叉树 完全二叉树：深度为k 的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。 满二叉树和完全二叉树有什么区别？ 答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。 完全二叉树 A B C G E I D H F J 为何要研究这两种特殊形式？ 因为它们在顺序存储方式下可以复原！

14 3. 二叉树的存储结构 [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C D E F G H I
T[0]一般不用 [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C D E F G H I A B C G E I D H F 一、顺序存储结构 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。 问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右 孩子的下标值必为2i＋1（即性质5）。 例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。

15 讨论：不是完全二叉树怎么办？ 答：一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。 [1] [2] [3]
[4] [5] [6] [7] [8] [9] … [16] A B ^ C D … E A B E C D 缺点：①浪费空间；②插入、删除不便

16 二、链式存储结构 用二叉链表即可方便表示。
data left_child right_child 一般从根结点开始存储。 （相应地，访问树中结点时也只能从根开始） 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。 data left_child right_child 二叉树结点数据类型定义： typedef struct node *tree_pointer; typedef struct node{ int data; tree_pointer left_child, right_child; } node;

17 二叉树链式存储举例： ^ A B D C E A B E C D 优点：①不浪费空间；②插入、删除方便

18 2.4.3 遍历二叉树 遍历定义—— 遍历用途—— 遍历方法—— Traversing Binary Tree
遍历二叉树 遍历定义—— 遍历用途—— 遍历方法—— 指按某条搜索路线遍访每个结点且不重复（又称周游）。 它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。 对每个结点的查看通常都是“先左后右” 。

19 遍历规则——— 二叉树由根、左子树、右子树构成，定义为D、L、R D、 L、R的组合定义了六种可能的遍历方案：
LDR, LRD, DLR, DRL, RDL, RLD 若限定先左后右，则有三种实现方案： DLR LDR LRD 先序/根遍历 中序/根遍历 后序/根遍历 注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。 以根结点为参照系

20 例1： 先序遍历的结果是： 中序遍历的结果是： 后序遍历的结果是： A B D E C A B C D E D B E A C D E B C A 口诀： DLR—先序遍历，即先根再左再右 LDR—中序遍历，即先左再根再右 LRD—后序遍历，即先左再右再根

21 先序遍历算法 DLR( node *root ) {if (root !=NULL) //非空二叉树 {printf(“%d”,root->data); //访问D DLR(root->lchild); //递归遍历左子树 DLR(root->rchild); //递归遍历右子树 } return(0); } 结点数据类型自定义 typedef struct node{ int data; struct node *lchild,*rchild； } node; node *root; 中序遍历算法 LDR(node *root) {if(root !=NULL) {LDR(root->lchild); printf(“%d”,root->data); LDR(root->rchild); } return(0);} 后序遍历算法 LRD (node *root) {if(root !=NULL) {LRD(root->lchild); LRD(root->rchild); printf(“%d”,root->data); } return(0);}

22 精确值：树深为k的递归遍历需要k+1个辅助单元
对遍历的分析： 1. 从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。 从虚线的出发点到终点的路径 上，每个结点经过3次。 A F E D C B G 第1次经过时访问，是先序遍历 第2次经过时访问，是中序遍历 第3次经过时访问，是后序遍历 2. 二叉树遍历的时间效率和空间效率 时间效率：O(n) //每个结点只访问一次 空间效率：O(n) //栈占用的最大辅助空间 精确值：树深为k的递归遍历需要k+1个辅助单元

23 特别讨论：若已知先序（或后序）遍历结果和中序遍历结果，能否“恢复”出二叉树？
例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 分析： ①由后序遍历特征，根结点必在后序序列尾部（即A）； ②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG）； ③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。

24 A B F G H C D E 已知中序遍历：B D C E A F H G 已知后序遍历：D E C B H G F A B D C E

25 小 结 第4节结束 1、定义和性质 1:2， 性质有3+2条 顺序结构 链式结构 树 2、存储结构 1 : n 中序遍历 后序遍历 先序遍历
小 结 1、定义和性质 1:2， 性质有3+2条 顺序结构 链式结构 树 二叉树 2、存储结构 二叉链表 三叉链表 1 : n 中序遍历 后序遍历 先序遍历 相关术语 3、遍历 第4节结束

26 作业2： P133 习题8 ，9，10，14