第11讲 树和二叉树2.pptx

数据结构;知识点回顾 树与二叉树的相关定义 二叉树的性质 每层最多结点数 总的结点数最多多少个 度为2的结点数与叶子数的关系 完全二叉树的结点数目和深度 完全二叉树中结点的双亲和孩子 二叉树的顺序存储结构;;第11讲; 单支树; A;分析：必有2n个链域。除根结点外，每个结点有且仅有一个双亲，所以只会有n－1个结点的链域存放指针，指向非空子女结点。;A;5.5 遍历二叉树和线索二叉树;一棵二叉树由 根结点、根结点的左子树（简称左子树）和 根结点的右子树（简称右子树）三部分组成。先左后右和先右后左相互对称，牢记约定顺序先左后右。 令L：遍历左子树；D：访问根结点；R：遍历右子树 D L R（先序遍历） L D R（中序遍历） L R D（后序遍历） 注：“先、中、后”的意思是指 访问的结点D是先于子树出现 还是后于子树出现。;;;先序:先根再左再右 ;从???结点开始，沿着虚线的出发点到终点的路径上，每个结点经过3次。;A;一个遍历序列与二叉树是不是一一对应的？ 例：画出先序序列为123所对应的所有二叉树。;遍历序列还原二叉树（唯一） 先序序列和中序序列 后序序列和中序序列 由先序序列和后序序列不能唯一确定一棵二叉树。;①由先序遍历特征，根结点必在先序序列头部（A）； ②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（BC），其右部必全部是右子树子孙（EDF）； ③继而，根据先序序列中的BC可确定B为A的左孩子，根据DEF可确定D为A的右孩子；以此类推。;先序：A B C D E F 中序：B C A E D F ;练习： 1、已知二叉树的先序遍历序列为DCBAEF，中序遍历序列为BACDEF，画出这棵二叉树。 2、已知二叉树的中序序列BDAEFC , 后序序列DBFECA，请画出这棵二叉树。;先序:先根再左再右