数据结构复习树与二叉树.ppt
《数据结构复习树与二叉树.ppt》由会员分享,可在线阅读,更多相关《数据结构复习树与二叉树.ppt(18页珍藏版)》请在三一文库上搜索。
1、数据结构复习 (树与二叉树),一、二叉树 或空,或由根和由互不相交的 左子树、右子树构成。 1、二叉链,第六章 树和二叉树,a,b,c,d,f,g,e,a,b,c,e,d,f,g,性质1: 在二叉树的第i (i0)层上至多有2i-1个结点。 性质2: 深度为k的二叉树中至多有2k-1个结点(k0)。 性质3: 对任何一棵二叉树T,如果其终端结点数为n0, 度为2的结点数为n2,则 n0=n2+1。 性质4: 有n个结点的完全二叉树的深度为 +1。,2、二叉树的性质,性质5: 如果对一棵有n个结点的完全二叉树按层序从1开始编号,则对任一结点(i1, 则其双亲结点是i/2。 (2)如果2i=n,
2、则结点i的左孩 子是结点2i ;否则结点i无 左孩子。 (3)如果2i+1=n, 则结点i的右 孩子是结点2i+1; 否则结 点i无右孩子 。,例.32个结点的完全二叉树,从根开始,按层次从左到右用1-32编号。请回答: (1)它共有多少层? (2)各层最左边的结点的编号是多少? (3)编号为6的结点的左孩子的编号是多少? 它的右孩子呢? (4)编号为16的结点的左孩子的编号是多少? 它的右孩子呢? (5)对于编号为8的结点,它的父结点的编号是多少? 编号为13的结点呢?编号为1的结点呢?,二叉树的遍历:按某条搜索路径访问二叉树中每一个结点,使得每个结点被访问一次且仅被访问一次。 遍历方法有4
3、种:先序遍历,中序遍历,后序遍历,层次遍历。,3、二叉树的遍历,先序遍历二叉树: (1)访问根结点 (2)先序遍历左子树 (3)先序遍历右子树 先序遍历序列: abcdfge,1,2,3,4,5,6,7,a,b,c,d,f,g,e,中序遍历二叉树: (1)中序遍历左子树 (2)访问根结点 (3)中序遍历右子树 中序遍历序列: bafgdce,a,b,c,d,f,g,e,1,2,3,4,5,6,7,后序遍历二叉树: (1)后序遍历左子树 (2)后序遍历右子树 (3)访问根结点 后序遍历序列: bgfdeca,a,b,c,d,f,g,e,1,2,3,4,5,6,7,a,b,c,d,f,g,e,1,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习 二叉
链接地址:https://www.31doc.com/p-3185657.html