算法与数据结构第6章ppt课件.ppt

《算法与数据结构第6章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树主要内容：树二叉树赫夫曼树家族成员关系表父亲女儿儿子孙子孙女孙子外孙外孙女§6.1树一、定义树T是由n个结点组成的有限集合。有一个特定的称之为根(root)的结点，其它结点划分为m(m0)个互不相交的有限集合T1,T2,…,Tm，每个集合本身又是一棵树，并且称之为根的子树(subTree)。特点：除根节点外，每个元素最多只有一个前驱，但可能有多个后继bacghdefij二、表示树结构的形式图形法:如下图所示嵌套集合表示法（文氏图表示法）凹入表表示法：括号表示法：图形表示法：教师学生其他人员99级2

2、000级2001级2002级……华中科技大学计算机系电信系自控系……叶子根子树三、与树有关的概念度（次数、级）结点的度：一个结点所拥有孩子数目树的度：树内各结点的度的最大值描述上下及左右的关系孩子结点双亲结点兄弟结点祖先节点后代节点层次树的深度（高度）：树最大的层次数。根的层次为1。森林bacghdefij§6.2二叉树一、二叉树的定义二叉树T是n个结点有限集合，其中n>=0,当n=0时为空树。否则是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。特点：1）每个结点的度≤2；2）是有序树

3、ACDEFBGHIKJMLA的TLB的TL树与二叉树的区别二叉树每个结点的孩子都有左右之分，每个结点都有左右两个子树，与树结构明显不同。以三个节点的树为例说明：ACBCBAACBCBACBACBACBA三个节点的树（两棵）三个节点的二叉树（五棵）二叉树的五种形态空树，节点数为0单节点二叉树，只有一个结点左子树为空，右子树不空右子树为空，左子树不空左右子树均不空性质1二叉树的第i层最多有2i-1个结点。(i1)性质2深度为h的二叉树最多有2h-1个结点。(h1)性质3对任何一棵二叉树,如果其叶结点个数为n

4、0,度为2的非叶结点个数为n2,则有n0＝n2＋1二、二叉树的性质证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+1定义1满二叉树定义2完全二叉树：若设二叉树的深度为h，则共有h层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。性质4具有n个结点的完全二叉树的深度为log2n+1证明：设完全二叉树的深度

5、为k，则有2k-1-1

6、序存储结构（数组表示）由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。单支树2.链式存储结构typedefstructBiNode{ElemTypedata;structBiNode*lchild,*rchild;}BiNode,*BiTree;二叉树链表表示的示例7个结点的二叉链表有（）个指针域为空，n个节点的二叉链表有（）指针域为空6.3二叉树遍历遍历二叉树是指按某种次序访问二叉树中每个节点一次且仅一次。TLR二叉树的一般形式示意图一、遍历算法的实现先序遍历：根

7、左右TLR中序遍历：左根右LTR后序遍历：左右根LRT例1：根据遍历方法分别写出下面二叉树先序、中序、后序的遍历序列ABCDEFGIJH先序：中序：后序：ABCDEFGHIJCBEDAGHFJICEDBHGJIFA先序遍历二叉树的递归算法若二叉树T不空，则：1、访问根节点；2、先序遍历T的左子树3、先序遍历T的右子树思考：请结合后序和中序的遍历思想，以及先序遍历的算法，写出后序和中序的遍历算法voidPreOrder(BiTreeT){if(T){printf("%c",T->data);PreOrder(

8、T->lchild);PreOrder(T->rchild);}}中序遍历二叉树的递归算法voidInOrder(BiTreeT){}if(T!=NULL){InOrder(T->lchild);printf("%c",T->data);InOrder(T->rchild);}后序遍历二叉树的递归算法voidPostOrder(BiTreeT){}if(T!=NULL){PostOrder(T->lchild);