树和二叉树数据结构解读.ppt

第六章 树和二叉树 一、树的基本概念 1、树的定义： 2、树的基本术语 （1）节点的度和树的度 （2）分支节点和叶节点 （3）路径和路径长度 （4）孩子节点、双亲结点和兄弟节点 （5）节点的层次和树的高度 （6）有序树和无序树 （7）森林 3、树的逻辑表示 （1）树形表示法 （2）文氏图表示法 （3）凹入表示法 （4）嵌套括号表示法 4、树的性质 （1）树中节点数等于所有节点的度加1。 （2）度为m的树中第i层至多有mi-1个节点。 （3）高度为h的m叉树至多有(mh-1)/(m-1)个节点。 （4）具有n个节点的m叉树的最小高度为logm(n(m-1)+1) 性质1的证明： 证明：根据树的定义，在一棵树中，除树根结点外，每个结点有且仅有一个前驱结点。也就是说，每个结点与指向它的一个分支一一对应，所以除树根之外的结点数等于所有结点的分支数(度数)，从而可得树中的结点数等于所有结点的度数加1。 性质2证明（数学归纳法）： （1）对于第一层，因为树中的第一层上只有一个结点，即整个树的根结点，而由i=l代入mi-1得mi-1 =1，也同样得到只有一个结点，显然结论成立。 （2）假设对于第(i-1)层(il)命题成立，即度为m的树中第(i-1)层上至多有mi-2结点，则根据树的度的定义，度为m的树中每个结点至多有m个孩子，所以第i层上的结点数至多为第(i-1)层上结点数的m倍，即至多为mi-2 *m= mi-1个，这与命题相同，故命题成立。 性质4的证明： 5、树的基本运算 树的运算主要分为三大类：第一类：寻找满足某种特定关系的的节点，如寻找当前节点的双亲结点；第二类：插入和删除某个节点；第三类：遍历树中的每一个节点。 树的遍历算法：按某种方式访问树中每一个节点且每一个节点只被访问一次。 注意：树的先根和后根遍历算法是递归的。 （1）先根遍历。例如：对前述图（a），先根遍历得到的节点序列为：ABEFCGJDHIKLM。 （2）后根遍历。例如：对前述图（a），后根遍历得到的节点序列为：EFBJGCHKLMIDA 6、树的存储结构 既要求存储节点的数据元素，又要存储节点之间的逻辑关系。常用的三种存储结构： （1）双亲存储结构：需一伪指针指示双亲结点的位置。 （2）孩子存储结构：按树的度设计节点的孩子节点的指针域的个数。 （3）孩子兄弟存储结构：为每个节点设计三个域：数据元素域、该节点的第一个孩子域、该节点的下一个兄弟节点指针域。 由于树的孩子兄弟存储结构有两个指针域，并且这两个指针是有序的，所以孩子兄弟存储结构是把树转换为二叉树的存储结构。我们在后面将会讨论到，把树转换为二叉树所对应的结构恰好就是这种孩子兄弟存储结构。所以，孩子兄弟存储结构的最大优点是可方便地实现树和二叉树的相互转换。 孩子兄弟存储结构的缺点也和孩子表示法的缺点一样：就是从前结点查找双亲结点比较麻烦，需要从树的根结点开始逐个结点比较查找。 树的基础要点 1、树最适合表示元素之间具有分支层次关系的数据。 2、一般树可以转换成二叉树是基于树的树形表示法。 3、树在计算机内的存储方式有三种方法：双亲、孩子和孩子兄弟存储结构。 4、利用树的孩子兄弟表示法，可以将一棵树转换为二叉树。 5、高度为k的m（m=2）叉树至少有（ ）个节点，最多有（ ）个节点。 6、在线性表、m叉树、栈和队列中，不可以利用顺序存储结构的是（ ）。 7、高度为h的满m叉树的第k层有（ ）个节点。 8、按后序遍历树或森林，等同于按（ ）遍历对应的二叉树。 9、在树中，一个节点的直接孩子节点的个数称为该节点的度。 10、一棵有n个节点的树，树中的所有节点的度之和为（ ）。 11、节点最少的树为（ ），节点最少的二叉树为（ ）。 【例1】含有n个节点和n个叶子节点的完全三叉树的高度各是多少？ 【例2】以孩子兄弟链表为存储结构，请设计递归和非递归算法求树的高度。 二、二叉树的概念和性质 1、二叉树的概念 二叉树是有限的结点的集合，此集合或者为空，或者是由一个根节点和两棵互不相交的称为左子树和右子树的二叉树组成。 特点：（1）每个节点至多有两个子树，任何结点的度数不能大于2。（2）二叉树的结点有严格的左右之分，其次序不能任意颠倒。 二叉树的表示方法：与树的表示方法一样，有：树形表示法、文氏图表示法、凹入表示法和嵌套括号表示法。 满二叉树的概念。 完全二叉树的概念。 满二叉树是完全二叉树的一种特例，并且完全二叉树与同高度的满二叉树对应位置结点有同一编号。 2、二叉树的性质 （1）非空二叉树上叶节点数等于双分支节点数加1。（会证明） （2）非