《数据结构C语言版》----第08章ppt课件.ppt

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

1、第8章树和二叉树树二叉树二叉树设计二叉树遍历线索二叉树哈夫曼树等价问题树与二叉树的转换树的遍历主要知识点8.1树1.树的定义树是由n(n≥0)个结点组成的有限集合T。n=0的树称为空树；对n>0的树，有:(1)仅有一个特殊的结点称为根结点，根结点没有前驱结点；(2)当n>1时，除根结点外其余的结点分为m(m>0)个互不相交的有限集合T1,T2，…，Tm，其中每个集合Ti本身又是一棵结构和树类似的子树。注：树的定义具有递归性，即“树中还有树”。若干术语结点：由数据元素和构造数据元素之间关系的指针组成ABCGEIDHFJFLK结点的度：结点所拥

2、有的子树的个数叶结点：度为0的结点，也称作终端结点分支结点：度不为0的结点孩子结点：树中一个结点的子树的根结点双亲结点：若树中某结点有孩子结点，则这个结点就称作它的孩子结点的双亲结点兄弟结点：具有相同的双亲结点的结点树的度：树中所有结点的度的最大值结点的层次：从根结点到树中某结点所经路径上的分支数树的深度：树中所有结点的层次的最大值无序树：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树有序树：树中任意一个结点的各孩子结点有严格排列次序的树森林：m（m≥0）棵树的集合2.树的表示方法(1)直观表示法(2)形式化表示法(3)凹入表示法T

3、=（D，R）DF=D1∪D2∪…∪Dm（1≤i,j≤m,Di∩Dj=￠）R={,i=1,2,…,n-1}ABCDEFGHIJKL3.树的抽象数据类型数据集合:树的结点集合，每个结点由数据元素和构造数　　　　　据元素之间关系的指针组成。操作集合:（1）创建MakeTree(T)（2）撤消DestroyTree(T)（3）双亲结点Parent(T,curr)（4）左孩子结点LeftChild(T,curr)（5）右兄弟结点RightSibling(T,curr)（6）遍历树Traverse(T,Visit())4.树的存储结构

4、树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。指针有常规指针和仿真指针4H2G1F1E1D0C0B-1AI4dataparent012345678ABDEFHICG(1)双亲表示法(a)一棵树（b)仿真指针的双亲表示法存储结构树及其使用仿真指针的双亲表示法(2)孩子表示法常规指针的孩子表示法rootBA∧CDEFGHI∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧双亲孩子表示法存储结构(3)双亲孩子表示法∧4H2G1F1E1D0C

5、0B-1AI4dataparenthead012345678∧∧∧∧childnext∧87∧∧∧123456(4)孩子兄弟表示法常规指针的孩子兄弟表示法root∧BCDEFGHI∧∧∧∧∧∧∧∧∧A8.2二叉树一、二叉树：是n(n≥0)个结点的有限集合。n=0的树称为空二叉树；n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1:2）基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒。所以下面是两棵不同的树1.二叉树的定义BACEDFGBACEDFG

6、二、满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。三、完全二叉树：如果一棵深度为k，有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应的二叉树称为完全二叉树。如下图所示BACEDFGHIJKLMNO(a)满二叉树BACEDFGHIJ(b)完全二叉树问题:一个高度为h的完全二叉树最多有多少个结点?最少有多少个结点?数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。操作集合：（1）创建MakeTree(T)（

7、2）撤消DestroyTree(T)（3）左插入结点InsertLeftNode(curr,x)（4）右插入结点InsertRightNode(curr,x)（5）左删除子树DeleteLeftTree(curr)（6）右删除子树DeleteRightTree(curr)（7）遍历二叉树Traverse(T,Visit())2.二叉树抽象数据类型3.二叉树的性质性质1:在一棵非空二叉树的第i层上至多有2i个结点（i≥0）。性质2:深度为k的二叉树至多有2k+1-1个结点。说明：深度k=-1，表示没有一个结点；深度k=0，表示只有一个根结点。

8、性质3:具有n个结点的完全二叉树的深度k为log2(n+1)-1。证明：根据性质2，对于有n个接点的深度为k的完全二叉树有2k-1