数据结构课件(树及二叉树).ppt

数据结构;A;6.1 树的类型定义;6.1 树的类型定义;6.1 树的类型定义;A;基本术语;6.2 二叉树的类型定义;(a) 空二叉树;二叉树的主要基本操作：;性质1： 在二叉树的第i层上至多有2i-1个结点(i=1)。 证明：采用归纳法证明此性质。 当i=1时，只有一个根结点，2i-1=20 =1,命题成立。 现在假定第i－1层上命题成立，则第i－1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i－1层上最大结点数的二倍， 即2×2i-2＝2i-1。 命题得到证明。;性质2：深度为k的二叉树至多有2k－1个结点（k=1). 证明：深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数2i-1（第i层上的最大结点数）;二叉树的重要特性：;满二叉树;两种特殊形态的二叉树： 一棵深度为k且由2k-1个结点的二叉树称为满二叉树。 如果深度为k、由n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树。 完全二叉树的特点是： （1）所有的叶结点都出现在第k层或k－1层。 （2）对任一结点，如果其右子树的最大层次为h，则其左子树的最大层次为h或h＋1。; 性质4：具有n个结点的完全二叉树的深度为[log2n]＋1。 符号[x]表示不大于x的最大整数。 证明：假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1n=2k-1 或 2k-1=n2k 取对数得到：k－1log2nk 因为k是整数。所以有：k＝[log2n]＋1。;性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第[log2n]+1层，每层从左到右),则对任一结点i（1=i=n),有： （1）如果i＝1，则结点i无双亲，是二叉树的根；如果i1，则其双亲是结点[i/2]。 （2）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。 （3）如果2i＋1n，则结点i无右孩子；否则，其右孩子是结点2i＋1。 证明：略！;6.3 二叉树的存储结构;L;?;1.顺序存储结构;1.顺序存储结构;;Typedef struct BiTNode  { TelemType data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree;;Status CreateBiTree(BiTree *T) { /*创建一棵二叉树*/  scanf(ch); if(ch= =) T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))  exit(OVERFLOW); T–data=ch; CreateBiTree(T–lchild);  CreateBiTree(T–rchildd); } return OK; };三叉链表法;Typedef struct TBiTNode { TelemType data; struct TBiTNode *lchild,*rchild,*parent; } BiTNode,*BiTree;;6.4 二叉树的遍历;6.4 二叉树的遍历;6.4 二叉树的遍历;6.4 二叉树的遍历;void InOrderTraverse (BiTree T, void( *visit)(TElemType e)){//中序遍历 if(T){ InOrderTraverse (T-lchild, visit); visit(T-data）; // 访问结点 InOrderTraverse (T-rchild, visit); }} void PostOrderTraverse (BiTree T, void( *visit)(TElemType e)){//后序遍历 if(T){ PostOrderTraverse (T-lchild, visit); PostOrderTraverse (T-rchild, visit); visit(T-data）; // 访问结点 }};四、先序遍历算法的非递归描述;6.4 二叉树的遍历;中序遍历的非递归算法;输出 信息;五、遍历算法的应用举例:;五、遍历算法的应用举例;五、遍历算法的应用举例;五、遍历算法的应用举例;6.5 线索二叉树;6.5 线索二叉树;6.5 线索二叉树;6.