数据结构二叉树ppt.ppt

校长 一系 二系 三系 六系 教务处 科研处 总务处 601 602 教务科 603 A B C D 例1 工厂 例3 1树的基本概念 2树的存储结构 3二叉树 4二叉树的存储结构 5二叉树的遍历 6线索二叉树 6 1树的基本概念 1 有且仅有一个结点没有前驱结点 该结点为树的根结点 2 除了根结点外 每个结点有且仅有一个直接前驱结点 3 包括根结点在内 每个结点可以有多个后继结点 4 树形表示法 1 结点的度 2 树的度 3 叶结点 4 分支结点 5 层次的定义 该结点拥有的子树的数目 树中结点度的最大值 度为0的结点 度非0的结点 根结点为第一层 若某结点在第i层 则其孩子结点 若存在 为第i 1层 7 树林 森林 m 0棵不相交的树组成的树的集合 8 树的有序性 6 树的深度 树中结点所处的最大层次数 若树中结点的子树的相对位置不能随意改变 则称该树为有序树 否则称该树为无序树 二叉树的基本形态 空 6 2二叉树 二 两种特殊形态的二叉树 1 一棵非空二叉树的第i层最多有2i 1个结点 i 1 2 深度为h的非空二叉树最多有2h 1个结点 3 若非空二叉树有n0个叶结点 有n2个度为2的结点 则n0 n2 1 4 具有n个结点的完全二叉树的深度h log2n 1 二叉树的存储结构 一 二叉树的顺序存储结构 1 完全二叉树的顺序存储结构 2 一般二叉树的顺序存储结构 二 二叉树的链式存储结构 二叉链表 二 前序遍历 三 中序遍历 四 后序遍历 前序遍历序列 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 2020 3 17 23 可编辑 6 3 2线索二叉树 1 何谓线索二叉树 遍历结果是求得结点的一个线性序列 指向该线性序列 前驱 和 后继 的指针 称 线索 包含 线索 的存储结构 称为 线索链表 与其相应的二叉树 称为 线索二叉树 对二叉树以某种次序遍历 使其变为线索二叉树的过程 称为 线索化 2 线索链表中结点的结构 在二叉链表的结点结构中增加两个标志域 并规定 其中 LTag 0lchild域指示结点的左孩子1lchild域指示结点的前驱 RTag 0rchild域指示结点的右孩子1rchild域指示结点的后继 二叉树二叉线索存储表示 typedefenum Link Thread PointerThr Link 0 指针 Thread 1 线索typedefstructBiThrNode TElemTypedata StructBiThrNode lchild rchild 左右孩子指针PointerThrLTag RTag 左右标志 BiThrNode BiThrTree 3 线索二叉树图例 线索二叉树及其存储结构 a 中序线索二叉树 b 中序线索链表 如何在线索树中找结点的后继 结合中序线索树若其右标志为 1 右链是线索 右链直接指示了结点的后继 若其右标志为 0 右链是指针 其后继为右子树中最左下的结点 如何在线索树中找结点的前驱 结合中序线索树若其左标志为 1 左链为线索 直接指示其前驱 若其左标志为 0 左子树中最右下的结点为其前驱 线索链表的中序遍历算法StatusIOTraver T BiThrTreeT Status Visit TElemTypee T指向头结点 头结点的左链lchild指向根结点 中序遍历 二叉线索树T的非递归算法 对每个数据元素调用函数Visit p T lchild p指向根结点while p T 空树或遍历结束时 p Twhile p LTag Link p p lchild if Visit p data returnERROR 访问其左子树为空的结点while p RTag Thread IOTraver T 6 4 2森林和二叉树的转换 1 树和二叉树的对应关系由于二叉树和树都可用二叉链表作为存储结构 则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系 树转换为二叉树方法 1 对每个孩子进行从左到右的排序 2 在兄弟之间加一条连线 3 对每个结点 除了左孩子外 去除其与其余孩子之间的联系 4 以根结点为轴心 将整个树顺时针转45 2 森林和二叉树的对应关系从树的二叉链表表示的定义可知 任何一棵和树对应的二叉树 其右子树必空 若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟 则同样可导出森林和二叉树的对应关系 已知条件 森林和二叉树的对应关系设森林F T1 T2 Tn T1 root t11 t12 t1m 二叉树B LBT Node root 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之外的森林 6 4 3树和森林的遍历 1 树的遍历 有三条搜索路径先根 序 遍历 若树不空 则先访问根结点 然后依次先根遍历各棵子树 后根 序 遍历 若树不空 则先依次后根遍历各棵子树 然后访问根结点 按层次遍历 若树不空 则自上而下自左至右访问树中每个结点 例对树进行先根遍历 获得的先根序列是 对树进行后根遍历 获得的后根序列是 ABEFCDGHI EFBCGHIDA 2 森林的遍历 先序遍历 对森林中的每一棵树进行先根遍历 1 若森林不空 访问森林中第一棵树的根结点 2 先序遍历森林中第一棵树的子树森林 3 先序遍历森林中 除第一棵树外 其余树构成的森林 后序遍历 对森林中的每一棵树进行后根遍历 1 若森林不空 后序遍历森林中第一棵树的子树森林 2 访问森林中第一棵树的根结点 3 后序遍历森林中 除第一棵树外 其余树构成的森林 例 对森林进行先序遍历 获得的先序序列是 对森林进行后序遍历 获得的后序序列是 BEFCDGHI EFBCGHID 总结 1 二叉树的线索化2 树的表