《数据结构二叉树ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构二叉树ppt课件.ppt（43页珍藏版）》请在金锄头文库上搜索。
1、第6章 树与二叉树 1 校长 一 系 二 系 三 系 六 系 教 务 处 科 研 处 总 务 处 601 602教 务 科 603 A B CD 张 三 李 四 王 五 例1 工 厂 2 根目录 f1f2f3fnd1d2dm 例2 f11f12f1kd11d12 3 例3 4 1 树的基本概念 2 树的存储结构 3 二叉树 4 二叉树的存储结构 5 二叉树的遍历 6 线索二叉树 5 6 1 树的基本概念 树是由n 0 个结点组成的有穷集合 不妨用D表示 以及结点之间关系组成的集合构成的结构 当n 0 时 称该树为空树 在任何一棵非空的树中 有一个特殊的结点t D 称之为该树的根结点 其余结点D
2、 t 被分割成m 0个 不相交的子集D1 D2 Dm 其中每一个子集Di又为一棵 树 分别称之为t 的子树 递归定义 一 树的定义 6 JIHGFE A CX B A的第1棵子树A的第3棵子树 A的第2棵子树 二 树 逻辑上 的特点 1 有且仅有一个结点没有前驱结点 该结点为树的根结点 2 除了根结点外 每个结点有且仅有一个直接前驱结点 3 包括根结点在内 每个结点可以有多个后继结点 7 JIHGFE A CX B 4 树形表示法 借助自然界中一棵倒置的树的形状来表示数 据元素之间层次关系的方法 8 1 结点的度 2 树的度 3 叶结点 4 分支结点 5 层次的定义 JIHGFE A CX B
3、 该结点拥有的子树的数目 树中结点度的最大值 度为0 的结点 度非0 的结点 根结点为第一层 若某结点在第i 层 则其孩子结点 若存在 为第i 1层 四 基本名词术语 第1层 第2层 第3层 9 7 树林 森林 m 0 棵不相交的树组成的树的集合 8 树的有序性 6 树的深度 树中结点所处的最大层次数 若树中结点的子树的相对位置不能 随意改变 则称该树为有序树 否 则称该树为无序树 JIHGFE A CX B 深度为3的树 10 二叉树的基本形态 空 根根 左 子 树 根 右 子 树 根 左 子 树 右 子 树 6 2 二叉树 11 二 两种特殊形态的二叉树 若一棵二叉树中的结点 或者为叶结点
4、 或者具有两 棵非空子树 并且叶结点都集 中在二叉树的最下面一层 这 样的二叉树为满二叉树 1 满二叉树 若一棵二叉树中只有最下 面两层的结点的度可以小于2 并且最下面一层的结点 叶结 点 都依次排列在该层从左至 右的位置上 这样的二叉树为 完全二叉树 2 完全二叉树 12 1 一棵非空二叉树的第i 层最多有2i 1个结点 i 1 三 二叉树的性质 2 深度为h 的非空二叉树最多有2h 1个结点 3 若非空二叉树有n0个叶结点 有n2个度为2的结点 则 n0 n2 1 4 具有n个结点的完全二叉树的深度h log2n 1 13 二叉树的存储结构 一 二叉树的顺序存储结构 1 23 45 67
5、8910 A BC DEFG HIJ BT 1 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I J 根据完全二叉树的性质 对于深度为h 的完全二叉树 将树中所有结点的数据信息按照编号的顺序依次存储到一 维数组BT 1 2h 1 中 由于编号与数组的下标一一对应 该 数组就是该完全二叉树的顺序存储结构 1 完全二叉树的顺序存储结构 14 1 23 4 5 67 8910 A BC D E FG H IJ 111213 BT 1 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G
6、 H J I A BC DEFG HIJ 2 一般二叉树的顺序存储结构 15 对于一般二叉树 只须在二叉树中 添加 一些实际上 二叉树中并不存在的 虚结点 可以认为这些结点的数据 信息为空 使其在形式上成为一棵 完全二叉树 然后 按照完全二叉树的顺序存储结构的构造方法将所有结点的 数据信息依次存放于数组BT 1 2h 1 中 16 二 二叉树的链式存储结构 二叉链表 链结点的构造为 lchilddatarchild 其中 data 为数据域 lchild 与rchild 分别为指向左 右子树的指针域 A BC DEF G I J A BC DEFG J I T 17 6 3 3 二叉树的遍历
7、18 二 前序遍历 19 三 中序遍历 20 四 后序遍历 21 A BC DKF G I J E H 前序遍历序列 A B D K J G C F I E H 中序遍历序列 D B G J K A F I E C H 后序遍历序列 D G J K B E I F H C A 按层次遍历序列 A B C D K F H J I G E 例 22 6 3 2 线索二叉树 1 何谓线索二叉树 遍历结果是求得结点的一个线性序列 指向 该线性序列 前驱 和 后继 的指针 称 线索 包含 线索 的存储结构 称为 线索链表 与其 相应的二叉树 称为 线索二叉树 对二叉树以 某种次序遍历 使其变为线索二叉树
8、的过程 称 为 线索化 23 2 线索链表中结点的结构 在二叉链表的结点结构中增加两个在二叉链表的结点结构中增加两个标志域 并 并 规定 规定 lchildLTagdataRTag rchild 其中 LTag 0 lchild 域指示结点的左孩子 1 lchild 域指示结点的前驱 RTag 0 rchild 域指示结点的右孩子 1 rchild 域指示结点的后继 二叉树二叉线索存储表示 typedef enum Link Thread PointerThr Link 0 指针 Thread 1 线索 typedef struct BiThrNode TElemType data Struc
9、t BiThrNode lchild rchild 左右孩子指针 PointerThr LTag RTag 左右标志 BiThrNode BiThrTree 25 3 线索二叉树图例 线索二叉树及其存储结构 a 中序线索二叉树 b 中序线索链表 1 23 4 5 67 0 1 0 0 2 01 3 1 1 4 10 5 0 1 6 11 7 1 thrt0 1 26 如何在线索树中找结点的后继 结合中序线索树 若其右标志为 1 右链是线索 右链直接指 示了结点的后继 若其右标志为 0 右链是指针 其后继为右 子树中最左下的结点 1 23 4 5 67 27 如何在线索树中找结点的前驱 结合中序
10、线索树 若其左标志为 1 左链为线索 直接指示其 前驱 若其左标志为 0 左子树中最右下的结点为 其前驱 1 23 4 5 67 28 线索链表的中序遍历算法 Status IOTraver T BiThrTree T Status Visit TElemType e T指向头结点 头结点的左链lchild指向根结点 中序遍历 二叉线索树T的非递归算法 对每个数据元素调用函数Visit p T lchild p指向根结点 while p T 空树或遍历结束时 p T while p LTag Link p p lchild if Visit p data return ERROR 访问其左子树
11、为空的结点 while p RTag Thread Visit p data 访问后继结点 p p rchild return OK IOTraver T 0 1 0 0 2 01 3 1 1 4 10 5 0 1 6 11 7 1 T0 1 1 29 6 4 2 森林和二叉树的转换 1 树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为存储结 构 则以二叉链表作为媒介可导出树与二叉树之 间的一个对应关系 30 31 树转换为二叉树方法 1 对每个孩子进行从左到右的排序 2 在兄弟之间加一条连线 3 对每个结点 除了左孩子外 去除其与其余 孩子之间的联系 4 以根结点为轴心 将整个树顺时针
12、转45 32 A BCD EGHFIa A BCD EGHFIb A BCD EGHFI c A B C D E G H F I d 33 2 森林和二叉树的对应关系 从树的二叉链表表示的定义可知 任何一棵 和树对应的二叉树 其右子树必空 若把森林中第二棵树的根结点看成是第一棵 树的根结点的兄弟 则同样可导出森林和二叉树 的对应关系 34 35 BCD EGHFIa BCD EGHFIb BCD EGHFI c B C D E G H F I d 36 已知条件 森林和二叉树的对应关系设 森 林 F T1 T2 Tn T1 root t11 t12 t1m 二叉树 B LBT Node roo
13、t RBT 由森林转换成二叉树的转换规则为 若 F 则 B 否则 由 Root T1 对应得到 Node root 由 t11 t12 t1m 对应得到 LBT 由 T2 T3 Tn 对应得到 RBT 由二叉树转换为森林的转换规则为 若 B 则 F 否则 由 Node root 对应得到 Root T1 由LBT 对应得到 t11 t12 t1m T1除根以外所 构成的森林 由RBT 对应得到 T2 T3 Tn 除T1之外的森林 37 6 4 3 树和森林的遍历 1 树的遍历 有三条搜索路径 先根 序 遍历 若树不空 则先访问根结点 然后依次先根遍历各棵子树 后根 序 遍历 若树不空 则先依次
14、后根遍历 各棵子树 然后访问根结点 按层次遍历 若树不空 则自上而下自左至 右访问树中每个结点 38 例 对树进行先根遍历 获得的先根序列是 对树进行后根遍历 获得的后根序列是 A BCD EGHFI A B E F C D G H I E F B C G H I D A 39 2 森林的遍历 先序遍历 对森林中的每一棵树进行先根遍历 1 若森林不空 访问森林中第一棵树的根结点 2 先序遍历森林中第一棵树的子树森林 3 先序遍历森林中 除第一棵树外 其余树构成的森林 后序遍历 对森林中的每一棵树进行后根遍历 1 若森林不空 后序遍历森林中第一棵树的子树森林 2 访问森林中第一棵树的根结点 3 后序遍历森林中 除第一棵树外 其余树构成的森林 40 例 对森林进行先序遍历 获得的先序序列是 对森林进行后序遍历 获得的后序序列是 BCD EGHFI B E F C D G H I E F B C G H I D 41 总结 1 二叉树的线索化 2 树的表示及其遍历操作 3 建立森林与二叉树的对应关系 由于在树和森林中 一个结点的孩子的个数 不定 它们在计算机中的表示以及在各种操作计 算机中的算法实现均不易实现 因此将树和森林 表示为二叉树 并将对树和森林的操作转化为对 二叉树的操作是通常采用的方法 42 此课件下载可自行编辑修改 供参考 感谢您的支持 我们努力做得更好 43
