第六讲 树-精品ppt课件

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

1、非线性结构树结构二叉树结构图树的定义和基本操作二叉树遍历二叉树哈夫曼树及其应用树结构树的定义和基本操作树是一类重要的非线性数据结构，应用广泛，如目录管理，下棋等。树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则:1、有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；2、除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0,1,…,m-1）又是一棵树，称为根的子树(subTree)，每棵子树的根结点有且仅有一个直接

2、前驱，但可以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。1、树的逻辑定义例1:树根：A子树：T1={B,E,F}T2={C,I}T3={D,G,H,J}ABDCJGHIFE节点，叶子（终端节点），分支节点，节点的度，树的度，子节点（孩子），父节点（双亲），兄弟，堂兄弟，祖先，子孙，节点的层次，树的深度，森林，有序树和无序树。2、树的基本术语ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0I的双亲：DL的双亲：E树的度：3A的层次：1M的层次：4树的

3、深度：4节点，叶子（终端节点），分支节点，节点的度，树的度，子节点（孩子），父节点（双亲），兄弟，堂兄弟，祖先，子孙，节点的层次，树的深度，森林，有序树和无序树。树形结构表示法嵌套集合表示法：凹入法表示法：广义表表示法：3、树的表示方法二叉树二叉树的定义：和树结构定义类似，二叉树的定义也可以递归形式给出：二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。特点：二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中不存在度大于2的结点，二叉树是有序树，其

4、子树的顺序不能颠倒。因此，二叉树有五种不同的形态。ABCDEFGHIJKLM123456思考题任意三个结点可构造多少二叉树?性质1：在二叉树的第i层上至多有2i-1个结点（i>=1）。证明：数学归纳法二叉树的性质i=1时，只有一个根结点，假设对所有j(1j=1)。证明：由性质1，可得深度为k的二叉树最大结点数是[证明用求等

5、比级数前k项和的公式]证明：设n1为二叉树T中度为1的结点数因为：二叉树中所有结点的度均小于或等于2所以：其结点总数n=n0+n1+n2又二叉树中，除根结点外，其余结点都只有一个分支进入设B为分支总数，则n=B+1又：分支由度为1和度为2的结点发出，B=n1+2n2于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。几种特殊形式的二叉树：1、满二叉树：一颗深度为k，且有2k-1个节点的二叉树称为满二叉树。

6、特点：每一层上的结点数都是最大结点数。12311458912136710141512345672、完全二叉树若一棵二叉树至少只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树实际上，完全二叉树是在满二叉树上减少一些结点，减少的结点只能是最后一层且从右边开始减少，不满足该条件的都是非完全二叉树。123114589126710123456思考题:第五层有5个叶子结点的完全二叉树，有多少个结点？2、二叉排序树或者是空二叉树，或者是具有如下性质的二叉树：左

7、子树上所有节点的关键字均小于根节点的关键字；右子树上所有节点的关键字均大于等于根节点的关键字；左子树和右子树本身又各是一棵二叉排序树。841061412917顺序存储结构可用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中。(空支用“0”填)二叉树的存储结构abcdefg特点：结点间关系蕴含在其存储位置中浪费空间，适于存储满二叉树和完全二叉树abcde0000fg012345678910BCDAEFGA

8、BDCEFrootG二叉链表顺序存储结构typedefstructnode{elemtypedata;structnode*lchild,*rchild;}TREENODE;lchilddatarchild二叉树的建立动画三叉链表（双向链表）typedefstructnode{elemtypedata;structnode*lchild,*rchild,*p