大学数据结构课件6.树及二叉树.ppt

第6章 树和二叉树;6.1.1 树的定义; 6.1.2 若干术语 （从结构上分）; 6.1.2.若干术语 （从关系上分）;无序树：树中任意一个结点的各孩子结点之间的次序构成 无关紧要的树 有序树：树中任意一个结点的各孩子结点有严格排列次序的树;;6.1.4 树的抽象数据类型;6.1.5 树的存储结构 ;4;(2)孩子表示法;双亲孩子表示法;(4)孩子兄弟表示法;6.2 二叉树;基本特征: ① 每个结点最多只有两棵子树（不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒。所以下面是两棵不同的树;满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。;完全二叉树：如果一棵深度为k，有n个结点的二叉树中各 结点能够与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应的二叉树称为完全二叉树。如下图所示;数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。 操作集合： （1）创建MakeTree(T) （2）撤消DestroyTree(T) （3）左插入结点InsertLeftNode(curr, x) （4）右插入结点InsertRightNode(curr, x) （5）左删除子树DeleteLeftTree(curr) （6）右删除子树DeleteRightTree(curr) （7）遍历二叉树Traverse(T, Visit());k=i;6.2.3 二叉树的重要性质;性质3 对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，则有n0= n2+1。;性质4: 具有n个结点的完全二叉树的深度为?log2(n) ? +1。 ;性质5:对于一棵有n个结点的完全二叉树，按照从上至下和从左至右的顺序对所有结点从1开始顺序编号。; 完全二叉树的结点可按从上到下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。下面两棵树在数组中的存储结构分别为：;B;完全二叉树：;对于一般的非完全二叉树;二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树最常用的的链式表储结构是二叉链和三叉链。二叉链存储结构的每个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。二叉链存储结构中每个结点的图示结构为：;A;二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。;6.2.5 二叉树二叉链表的一个生成算法;Bnode *creat() { Bnode *t=NULL; printf(“\n i,x=”);scanf(“%d%d”,i,x); while(i!=0x!=0) { q=(Bnode *)malloc(sizeof(Bnode)); q-data=x;q-lch=NULL;q-rch=NULL; s[i]=q; /* Bnode *s[20] */ if(i==1)t=q; /* t为树根结点 */ else{ j=i/2; /* j为双亲结点编号 */ if((i%2)==0)s[j]-lch=q;else s[j]-rch=q; } printf(“\n i,x=”); scanf(“%d%d”,i,x); } return t; } /* creat end */;6.3 二叉树遍历; 从二叉树的定义知，一棵二叉树由三部分组成：根结点、左子树和右子树。;A;二叉树选择不同的存储结构，遍历算法的程序代码会有所不同。这里确定用二叉链表作为存储结构，树中结点的结构定义为：;若根为空则结束；否则： （1）访问根结点； （2）按先根次序遍历左子树； （3）按先根次序遍历右子树。;A;若根为空则结束；否则： （1）按中根次序遍历左子树； （2）访问根结点； （3）按中根次序遍历右子树。;;6.3.3 后根遍历;void levelorder(Bnode *p) { Bnode *q[20]; front =0; rear=0; if(p!=NULL){rear++;q[rear]=p;} /*根结点不空，进队*/ while(front!=rear) { front++; p=q[front]; printf(“%6c”,p-data); /* 出队并访问*/