《树与二叉树 》ppt课件

《《树与二叉树 》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章树与二叉树1.树的定义及其基本概念2.二叉树的基本概念和存储结构3.二叉树的遍历4.线索二叉树的概念及其遍历6.哈夫曼树及其构造方法7.树与森林5.二叉排序树8.1树的概念和基本术语一、树的定义树是由n(n0)个结点的有限集合。如果n=0，称为空树；如果n>0，则有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n>1，除根以外的其它结点划分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。A只有根结点的树AB

2、CDEFGHIJKLM有子树的树根子树Ø空树特点：树中至少有一个结点——根树中各子树是互不相交的集合二、树的表示1．树形结构表示法2.凹入法表示法3.嵌套集合表示法（文氏图表示法）4.广义表表示法（括号表现法）对树结构，广义表表示法可表示为：(A(B(E(J，K，L)，F)，C(G)，D(H(M)，I))))分支(branch)：结点之间的二元关系（序偶）。结点(node)：一个数据元素及指向其子树的分支。结点的度(degree)：结点拥有的子树个数。叶结点(leaf)：度为零的结点。分支结点(branchnode

3、):有后继的结点称为分支结点。儿子(sons)：结点x的子树的根。父亲(parent):结点x的前驱结点称为x的父亲。兄弟(brother)：同一父亲的结点的子女结点。祖先(ancestor)：根到该结点路径上的所有结点。子孙(descendant)：某结点为根的子树上的任意结点。堂兄弟(cousin):父亲是兄弟关系或堂兄弟关系的结点。结点层次(level)：从根开始，根为第一层，根的子女为第二层，以此类推。树的深度（高度）(depth)：树中结点的最大层次数树的度：一棵树中最大的结点度数。结点按层编号（层中编号

4、）：将树中结点按从上层到下层，同层从左到右的次序排成一个线性序列，依次给他们编以连续的自然数。祖辈（上层）：层号比结点x小的结点，称为x的祖辈。后辈（下层）：层号比结点x大的结点，称为x的后辈。有序树：若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。无序树：若一棵树中所有子树的次序无关紧要，则称为无序树。森林(forest)：m(m0)棵互不相交的树。三、树的基本术语1层2层4层3层height=4ACGBDEFKLHMIJ结点结点的度叶结点分支结点子女双亲兄弟祖先子孙结点层次树的深度树

5、的度有序树无序树森林ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的父亲：D结点L的父亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先8.2二叉树(BinaryTree)定义:五种形态:一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。LLRR特点:每个

6、结点至多只有两棵子树（二叉树中不存在度大于2的结点）二叉树的基本操作（1）creat_tree(bt,str)根据二叉树的括号表示法str建立一棵二叉树bt。（2）disptree(bt)以凹入法显示一棵二叉树bt。（3）depth_bttree(bt)求一棵二叉树bt的深度。（4）count_bttree(bt)求一棵二叉树bt的结点个数。（5）leafcount_bttree(bt)求一棵二叉树bt的叶子结点个数。（6）nleafcount_bttree(bt)求一棵二叉树bt的非叶子结点个数。性质1在二叉树的

7、第i层上至多有2i－1个结点。(i1)[证明用归纳法]证明：当i=1时，只有根结点，2i-1=20=1。假设对所有j，i>j1，命题成立，即第j层上至多有2j-1个结点。由归纳假设第i-1层上至多有2i－2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i－2=2i-1。二叉树的性质性质2深度为k的二叉树至多有2k-1个结点(k1)。证明：由性质1可见，深度为k的二叉树的最大结点数为＝20+21+…+2k-1=2k-1＝性质3对任何一棵二叉树T,如果

8、其叶结点数为n0,度为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满二叉树(FullBinaryTree)一棵深度为k且有2k-1个结点的二叉树称为满二叉树。两种特殊形态