第11讲 二叉树的遍历.ppt

第11讲 二叉树的遍历 主讲人：陈红丽 (1)具有n个结点的非空二叉树的最小深度是多少？最大深度是多少？ 二叉树的存储结构 顺序存储结构 依照层序编号规则，存放各个结点。 存储位置隐含树的关系。 对于完全二叉树，将完全二叉树上编号为 i 的结点元素存储在一维数组中下标为 i-1 的分量中 练习： 将67个结点的完全二叉树，按顺序存储结构存于数组A[0…100]中，最小编号的叶子结点存储于A[ ]。 A、32 B、33 C、34 D、35 对于一般二叉树的顺序存储：将其每个结点与完全二叉树上的结点相对照，然后存储在数组的相应分量中，缺少的结点用“0”补齐。 画出二叉树分支图表示 写出结点c的父结点及其左、右孩子 采用顺序存储结构，深度为k且只有k个结点的右单枝树（每个非叶结点只有右孩子），需要（ ）个单元，即有（ ）个单元被浪费。 二叉链表 data 域存放该结点的数据信息；lchild域与rchild域分别存放指向左、右孩子的指针，当左、右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。 性质6：含有n个结点的二叉链表中，有（ ）个空链域。 三叉链表 若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点下标为k（起始下标为1）。那么______ 时采用顺序存储更节省空间。 A.d12n/(k-n)　　　B.d12n/(k-n) C.d12n/(k+n)　 　D.d12n/(k+n) 遍历二叉树 遍历：是指按照某种顺序访问二叉树中的每个结点，使得每个结点被访问且仅被访问一次。 深度遍历 层次（广度）遍历 访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。 一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。 深度遍历的次序： 一棵二叉树由 根结点、根结点的左子树（简称左子树）和 根结点的右子树（简称右子树）三部分组成。先左后右和先右后左相互对称，牢记约定顺序先左后右。 令L：遍历左子树；D：访问根结点；R：遍历右子树 D L R（先序遍历） L D R（中序遍历） L R D（后序遍历） 注：“先、中、后”的意思是指 访问的结点D是先于子树出现 还是后于子树出现。 深度遍历递归算法 遍历序列与二叉树是不是一一对应的？ 例：画出先序序列为123所对应的所有二叉树。 根据遍历序列还原二叉树 遍历序列和二叉树不具有一一对应的关系。根据各种遍历的特点，从相应的遍历序列中可以得到二叉树的结构信息。 遍历序列还原二叉树（唯一） 先序序列和中序序列 后序序列和中序序列 由先序序列和后序序列不能唯一确定一棵二叉树。 由两个遍历序列构造二叉树 1. 根据先序序列的第一个元素建立根结点； 2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列； 3. 在先序序列中确定左右子树的先序序列； 4. 由左子树的先序序列和中序序列建立左子树； 5. 由右子树的先序序列和中序序列建立右子树。 例：已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGHFI，如何构造该二叉树呢? 由两个遍历序列构造二叉树 1. 根据后序序列的最后一个元素建立根结点； 2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列； 3. 在后序序列中确定左右子树的后序序列； 4. 由左子树的后序序列和中序序列建立左子树； 5. 由右子树的后序序列和中序序列建立右子树。 ABECDFGHIJ EBCDAFHIGJ DECBHGFA BDCEAFHG 先序：EBADCFHGIKJ -根：E 根据根结点来划分中序序列 中序：ABCDEFGHIJK - ABCD + E + FGHIJK 由左右子树的结点集合来划分先序序列-先序：E + BADC + FHGIKJ 如图（a） 分别对左右子树运用相同的方法分解出根和其左右子树的结点集合。依次递归，如图（b）、（c）。 练习： 已知二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，画出这棵二叉树。 已知二叉树的中序序列BDCEAFHG , 后序序列DECBHGFA，请画出这棵二叉树。 已知一棵二叉树的中序序列为ABCDEFGHIJK，先序序列为EBADCFHGIKJ ，请画出该二叉树。 先序 中序 A B F E C G D J I H 后序 中序 F G H A B C D E