资源描述：
《济南大学数据结构-第六章.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章树和二叉树族谱曾祖父张三父亲二叔大伯大爷爷爷三爷树结构是一类重要的非线性结构(层次结构)。学习重点:Ø树的基本概念Ø二叉树的基本概念、相关操作Ø树和森林与二叉树之间的相互转换Ø二叉树的应用6.1树的定义和基本术语树(Tree):是具有层次结构的n(n≥0)个结点的有限集。ABCDEFGHIJKLM树(Tree):是n(n≥0)个结点的有限集。n＝0，空树Φ。n＝1，有且仅有一个称为根的结点的树。n＞1，除根结点外，其余结点可分为m(m＞0)个互不相交的有限子集，每个子集都称为根结点的子树。只有根结点的树
2、AABCDEFGHIKLM基本术语:树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的分支数（子树数）称为结点的度。例，A的度为3，F的度为0。度为0的结点称为叶子结点或终端结点。度不为0的结点称为分支结点或非终端结点。例，K,L,F,G,M,I,J为叶子；A,B,C,D,E,H为分支结点。除根结点外，其余分支结点又称为内部结点。例，B,C,D,E,H为内部结点。树的度是指树内各结点的度的最大值。例，树的度为3。结点的子树的根称为该结点的儿子。该结点称为儿子的父亲。例，B,C,D是A的儿子，A是B,C
3、,D的父亲。同一个父亲的儿子之间互称兄弟。例，B,C,D互为兄弟。其父亲在同一层的结点互为堂兄弟。例，G与E,F,H,I,J互为堂兄弟。从根到结点所经分支上的所有结点称为该结点的祖先。例，M的祖先为H,D,A。以某结点为根的子树中的任一结点都称为该结点的子孙。例，B的子孙有E,K,L,F。结点的层次从根开始定义起，根为第一层，根的儿子为第二层。例，A在第一层，B,C,D在第二层。树中结点的最大层次称为树的深度或高度。例，树的深度为4。如果将树中结点的各子树看成从左到右是有序的(即不能互换)，则称该树为有序树，
4、否则称为无序树。一个有序树，父亲结点的儿子也是从左至右有序的。例，B,C,D分别称为A的第1，2，3个儿子。6.2二叉树6.2.1二叉树的定义二叉树是n(n≥0)个结点的有限集，它或者是空集，或者是由一个根和称为左、右子树的两个互不相交的二叉树组成。Φ空二叉树ABCDEF一般二叉树根左子树右子树二叉树是一个递归定义。根据定义，二叉树通常具有5种基本形态:Φ空二叉树A仅有根结点的二叉树右子树为空的二叉树左、右子树均非空的二叉树左子树为空的二叉树AAA6.1节关于树的基本术语也都适用于二叉树。树的子树次序不作规定
5、，树中结点的度没有限制，二叉树的两个子树有左、右之分。二叉树中结点的度只能取0、1、2。抽象数据类型—二叉树的定义:ADTBinaryTree数据对象D:D是具有相同结构的数据元素的集合。数据关系R:D＝Φ，则为空二叉树。D≠Φ，则D＝(root，DL，DR)。root:根结点DL:root的左子树DR:root的右子树基本操作P:6.2.2二叉树的性质性质1:在二叉树的第i层上至多有2i-1个结点(i≥1)。归纳法证明:(1)i=1，只有一个根结点，2i-1=20=1，正确；(2)假设i-1成立，即第i-1
6、层上至多有2i-2个结点；(3)由于二叉树的结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2×2i-2=2i-1。a1a2a2i-2…i-1i性质2:深度为k的二叉树至多有2k–1个结点(k≥1)。∑i=1k(第i层上的最大结点数)＝∑i=1k2i-1＝2k–1作业:归纳法证明。引论:一棵树有n个结点，则必有n–1条分支。证明:除根结点外，其它结点都有一个分支进入，设B为分支总数，则B=n-1ABCDEF性质3:对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，
7、则n0=n2+1。证明:(1)已知，终端结点数为n0，度为2的结点数为n2，设度为1的结点数为n1，由于二叉树中的所有结点的度只能为0、1、2，故二叉树的结点总数为n=n0+n1+n2；(2)除根结点外，其它结点都有一个分支进入，设B为分支总数，故n=B+1，由于这些分支均是由度为1或2的结点发出的，所以有B=n1+2n2，故n=n1+2n2+1，由(1)和(2)，可得n0+n1+n2=n1+2n2+1，故有n0=n2+1。两种特殊形态二叉树:满二叉树、完全二叉树。一棵深度为k且有2k-1个结点的二叉树称为满
8、二叉树。1245满二叉树367特点:(1)每一层的结点数都达到最大结点数。(2)叶子(终端)结点一定在最大层。(3)任一结点，其左、右分支下的子孙的最大层次相等。对满二叉树的结点进行连续编号，从根结点起，自上而下，自左至右，1、2、3、……、2k-1。深度为k的，有n£k个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。12453612345非
