数据结构第6章树.ppt

《数据结构第6章树.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章树9/4/20211上讲主要内容串定义存储算法应用数组定义存储算法应用线性与非线性数据结构9/4/20212第6章树6.1树6.2二叉树6.3二叉树的遍历6.4树和森林6.6二叉树的应用习题9/4/202136.1树树的定义（递归定义）：树（Tree）是n（n≥0）个结点的有限集合T，满足两个条件：（1）有且仅有一个特定的称为根（Root）的结点，它没有前趋；（2）其余的结点可分成m个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为根的子树。当n=0时的空集合定义为空树。CAEDBFIGJ

2、H9/4/20214树的表示方法直观表示法文氏图表示法目录表示法嵌套括号表示法树的直观表示法圆圈表示结点，结点的名字可写在圆圈内或圆圈旁。连线表示结点之间的关系，树的文氏图表示法圆圈表示结点圆圈的相互包含表示结点之间的关系。树的目录表示法凹入的线条表示结点线条的长短表示结点间的关系，长线条包含短线条。树的嵌套括号表示法括号表示结点括号的相互包含表示结点间的关系。树的基本术语结点：指树中的一个元素，包含数据项及若干指向其子树的分支。结点的度：指结点拥有的子树个数。树的度：指树中最大结点度数。叶子：指度为零的结点，又称为

3、终端结点。孩子：一个结点的子树的根称为该结点的孩子。双亲：一个结点的直接上层结点称为该结点的双亲。兄弟：同一双亲的孩子互称为兄弟。堂兄弟：双亲在同一层上的结点互称为堂兄弟。CAEDBFIGJH9/4/202110结点的层次：从根结点开始，根结点为第一层，根的孩子为第二层，根的孩子的孩子为第三层，依次类推。树的深度：树中结点的最大层次数。9/4/202111路径：若存在一个结点序列k1,k2,…,kj,可使k1到达kj,则称这个结序序列是k1到达kj的一条路径。子孙和祖先：若存在k1到kj的一条路径k1,k2,…,kj

4、，则k1,…,kj-1为kj的祖先，而k2,…,kj为k1的子孙。森林：m(m≥0)棵互不相交的树的集合构成森林。有序树和无序树：若将树中每个结点的各个子树都看成是从左到右有次序的（即不能互换），则称该树为有序树，否则为无序树。CAEDBFIGJH9/4/202112顺序存储顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，使之成为一个线性序列，然后存储。链式存储链式存储时，使用多指针域的结点形式，每一个指针域指向一棵子树的根结点。由于树的分支数不固定，很难给出一种固定的存储结构，通常采用二叉树的形式存储树。

5、树的存储结构9/4/2021136.2二叉树定义（二叉树的递归定义）：二叉树是n（n≥0）个结点的有限集，它或为空树（n=0），或由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树构成。二叉树的五种基本形态：二叉树与度为2的树的区别：二叉树的子树有左右之分，而树的子树不分左右；二叉树与有序树？9/4/202114满二叉树和完全二叉树一棵深度为k且有2k-1个结点的二叉树称为满二叉树。满二叉树的特点是每一层的结点数都达到该层可具有的最大结点数。如果一个深度为k的二叉树，它的结点按照从根结点开始，自

6、上而下，从左至右进行连续编号后，得到的顺序与满二叉树相应结点编号顺序一致，则称这个二叉树为完全二叉树。完全二叉树的1至k-1层上共有2k-1-1个结点，第k层的结点集中在最左边。满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。9/4/202115二叉树的性质-1性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。证明：可用数学归纳法予以证明。当i=1时，有2i-1=20=1，同时第一层上只有一个根结点，故命题成立。设当i=k时成立，即第k层上至多有2k-1个结点。当i=k+1时，由于二叉树的每个结点至多

7、有两个孩子，所以第k+1层上至多有22k-1=2k个结点，故命题成立。9/4/202116二叉树的性质-2性质2：深度为k的二叉树至多有2k-1个结点(k≥1)。证明：性质1给出了二叉树每一层中含有的最大结点数，深度为k的二叉树的结点总数至多为故命题成立。9/4/202117二叉树的性质-3性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设度为1的结点数为n1，则一棵二叉树的结点总数为：n=n0+n1+n2因为除根结点外，其余结点都有一个进入的分支(边)，设B为分支总

8、数，则n=B+1。又考虑到分支是由度为1和2的结点发出的，故有B=2n2+n1，即n=2n2+n1+1比较两式可得n0=n2+1，证毕。9/4/202118二叉树的性质-4性质4：具有n个结点的完全二叉树的深度为log2n+1或log2(n+1)。(其中x表示不大于x的最大整数，x表示不小于x的最小整数。)证明：设完全二叉树的深