数据结构-树与二叉树

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

1、Chapter6Tree&BinaryTree教学内容1、树和森林的概念2、二叉树的定义、性质及运算；3、二叉树的存储结构4、遍历二叉树、树、森林5、森林与二叉树的转换6、哈夫曼树、哈夫曼编码树型结构（非线性结构）结点之间有分支具有层次关系生活中的哪些实例是树型结构呢？例自然界:树人类社会家谱院系组织机构锦城学院电子系计科系文传系…通信信息工程微电子…通1班通2班通3班树的概念树的定义树是n(n0)个结点的有限集。若n=0，称为空树；若n>0，则它满足如下两个条件：有且仅有一个称之为根(Root)的结点。当n>1，除根以外的其它结点分为m(m>0)个

2、互不相交的有限集T1,T2,…,Tm，其中每个集合又是一棵符合本定义的树，并且称为根的子树。ACGBDEFKLHMIJ例如A只有根结点的树有13个结点的树A是根；其余数据元素分成三个互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子树，且本身也是一棵树。根结点T1R={,,,,,,,,,,,}ACGBDEFKLHMIJ线性结构树结构存在唯一的没有前驱的“首元素”存在唯

3、一的没有前驱的“根结点”存在唯一的没有后继的“尾元素”存在多个没有后继的“叶子”其余元素均存在唯一的“前驱元素”和唯一的“后继元素”其余结点均存在唯一的“前驱（双亲）结点”和多个“后继（孩子）结点”树结构和线性结构作如下对照：树的基本术语1层2层4层3层height=4ACGBDEFKLHMIJ结点结点的度叶子结点分支结点儿子结点父亲结点兄弟结点祖先结点树的度结点的层次树的深度森林有序树子树之间存在确定的次序关系无序树子树之间不存在确定的次序关系家族树就属于有序树。森林是m(m≥0)棵互不相交的树的集合root给森林中的各子树加上一个父亲结点,森林就变成了

4、树。T3T2T1ABEFKLDHMIJCGCG二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成。二叉树为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。BDEGHCILFA根结点右子树左子树(a)空二叉树(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树注：虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。二叉树的五种基本形态性质1在二叉树的第i层上至多有2i－1个结点。(i1)证明：当i=1时，只有根结点，

5、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,如果其叶子结点数为n0,度为2的结点数为n2,则n0＝n2＋1。证明：n=n0+n1+n2①e=n–1=2n2+n1②因此，2n2+

6、n1=n0+n1+n2-1n0=n2+1满二叉树(FullBinaryTree)定义1:一棵深度为k且有2k-1个结点的二叉树称为满二叉树。两种特殊形态的二叉树754389101113141512126特点:每一层上的结点数都达到最大,叶子全部在最底层非完全二叉树完全二叉树(CompleteBinaryTree)若设二叉树的深度为h，除第h层外，其它各层(0h-1)的结点数都达到最大值，第h层从右向左连续缺若干结点。完全二叉树621543BACDEGF性质4具有n(n0)个结点的完全二叉树的深度为log2(n)＋1。证明：设完全二叉树的深度为h，则

7、根据性质2和完全二叉树的定义有2h-1-1n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点。(3)若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。3.深度为9的二叉树中至少有个结点。Ａ)２9

8、Ｂ)２8Ｃ)９Ｄ)２9－12.深度为Ｋ的二叉树的结点总数，最多为个