数据结构-第6章-数和二叉树.ppt

课前思考 概述 树型结构是一类重要的非线性结构 树是以分支关系定义的层次结构 树的应用 人类社会的族谱 社会组织结构 在编译程序中的语法树 在数据库系统中，可用树来组织信息 树的定义 树基本操作（P119）： 树的基本术语 树的基本术语 树的基本术语 树的基本术语 树与线性结构的区别 练习1 列出下图所示树的叶结点、分支结点和每个结点的层次。 什么是二叉树？ 一个典型的二叉树 练习 回顾 树的基本特点、基本术语 有一棵树的括号表示为A(B,C(E,F(G)),D)，回答下面的问题： 1、这棵树的根结点是多少 2、这棵树的叶子结点是什么 3、结点C的度是多少 4、这棵树的度是多少 5、这棵树的深度是多少 6、结点C的孩子结点是哪些 7、结点C的双亲结点是谁 若一棵度为4的树中度为1、2、3、4的结点个数分别为4、3、2、2，则该树叶子结点的个数是多少？总结点个数是多少？ 二叉树的性质1 二叉树的性质2 二叉树的性质3 两种特殊形态的二叉树 两种特殊形态的二叉树 实例 二叉树的性质4 二叉树的性质5 练习 1、具有100个结点的完全二叉树的深度为(从1层开始计数)( ) A.6 B.5 C.4 D.7 2、二叉树第i（i=1）层上至多有（ ）结点。 A. 2i B. 2i C. 2i-1 D. 2i-1 3、将一棵有50个结点的完全二叉树按层编号(从1开始)，则对编号为25的结点x，该结点（ ） A.无左、右孩子 B.有左孩子，无右孩子 C.有右孩子，无左孩子 D.有左、右孩子 回顾 二叉树的5个性质 某一层上的最大结点数为： K深度的二叉树最多结点数为： n0=n2+1 n结点完全二叉树深度： n结点完全二叉树任一结点i有： 4. 二叉树的存储结构 顺序存储结构 链式存储结构 二叉链表 三叉链表 线索链表 二叉树的顺序存储结构 完全二叉树的数组表示 一般二叉树的树组表示 若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。如图给出了顺序存贮形式。 设二叉树的顺序存储结构如下： 二叉树的存储结构—链式存储结构 适用范围： 一般的二叉树，并且如果在一棵树中进行添加删除时，要移动许多结点。 二叉链表 与单链表类似…… 整个二叉树可以 以一个指向根结点的指针(表头指针)表示 也可以有类似于双向链表的结构-三叉链表 二叉链表和三叉链表 三叉链表 三叉链表结构图 可以证明 在含有n个结点的二叉链表中有n+1个空链域。 何为遍历二叉树 先序遍历 前序遍历动画演示 中序遍历 中序遍历动画演示 后序遍历 后序遍历动画演示 前序遍历算法实现-递规算法 　void?Preorder (BiTree T，void(*visit)( BiTree ))　{　　//?先序遍历以T为根指针的二叉树?　　if?(T)?{　　　　　　　　　　 //?T=NULL时，二叉树为空树，不做任何操作　　visit(T);?//?通过函数指针 *visit 访问根结点?　　Preorder(T-Lchild, visit);?//?先序遍历左子树　　Preorder(T-Rchild, visit);?//?先序遍历右子树　　}?//?if　} a+b*(c-d)-e/f 练习 经典题：写出三个结点的二叉树的前序、中序、后序遍历的序列 画出和下列已知序列对应的二叉树 二叉树的前序访问序列为:EBADCFHGIKJ 二叉树的中序访问序列为:ABCDEFGHIJK 2.二叉树的中序访问序列为:DCBGEAHFIJK 二叉树的后序访问序列为:DCEGBFHKJIA 写出前、中、后序遍历 画出和下列已知序列对应的二叉树 前：A B E F C D G H 中：F E B A D C G H 线索二叉树 线索二叉树的结构如下： 如何在中序线索树中找结点的后继、前趋？ 结点的后继：应该是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。 结点的前趋：若其左标志为“1”，则左链为线索，指示其前驱，否则遍历左子树时的最后访问的一个结点（左子树最右下的结点）为其前驱。 什么时候采用线索链表做存储结构？ 程序中所用二叉树需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继时。 树的存储结构1-双亲表示法 双亲表示法示例 孩子表示法——多重链表 2 树的孩子表示法 孩子表示法示例 为了方便我们可以…… 4 二叉链表表示法（孩子兄弟表示法） 练习 画出此树的 双亲表示、孩子链表表示、二叉链表