数据结构(第二版)课件 包振宇 第五章 树.ppt

《数据结构(第二版)课件 包振宇 第五章 树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章树5.1树的定义和术语5.2二叉树5.3遍历二叉树5.4线索二叉树5.5树和森林5.6树的应用5.7典型例题5.1树的定义和术语一、树的定义树（tree）是n(n≥0)个结点的有限集。在一棵非空树中：（1）有且仅有一个特定的称为根（root）的结点；（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集（T1,T2,…Tm），其中每一集合本身又是一棵树，并且称为根的子树（subtree）。举例例5．1（a）只有根结点的树（b）一般的树图5-1-1的（b）中A为根结点，其余结点分成三个互

2、不相交的子集：T1={B，E，F，K，L}，T2={C，G}，T3={D，H，I，J}而T1，T2，T3本身又都是只有一个根结点的树。ALKEFGHIJDCBAM二、树结构中的一些基本术语：（1）结点：包含一个数据元素及若干指向其子树的分支（2）结点的度：结点拥有子树数目称为结点的度。如图5-1-1的（b）中，A的度为3；C的度为1；M的度为0。（3）叶子（或终端）结点：度为零的结点。（4）分支结点（或非终端结点）：除根结点外度不为零的结点，也称为内部结点。（5）树的度：树内各结点的度的最大值。基本

3、术语(续)（6）孩子：结点的子树的根称为该结点的孩子。如图5-1-1的（b）中，D为A的子树T3的根，则D是A的孩子。（7）双亲：和孩子定义相应地该结点称为孩子的双亲。如图5-1-1的（b）中，A为D的双亲。（8）兄弟：同一个双亲的孩子之间互称兄弟。如图5-1-1的（b）中的H，I，J。（9）祖先：从根到该结点所经过分支上的所有结点。如：M的祖先为A，D，H（10）子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如图5-1-1的（b）中B的子孙为E，F，K，L基本术语(续)（11）层次：从根

4、开始定义为第一层，根的孩子为第二层，依次例推。（12）深度（或高度）：树中结点的最大层次。（13）有序树：将树中结点的各子树看成从左到右是有序的。无序树：树中结点的各子树没有次序的。有序树中最左边的子树的根称第一个孩子，最右边的称为最后一个孩子。（14）森林：是m(m≥0)棵互不相交的树的集合，对树中每个结点而言，其子树的集合即为森林。5.2二叉树一、二叉树的定义和性质：1、定义：二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点）并且二叉树的子树有左右之分，

5、其次序不能任意颠倒。2、如图5-2-1所示二叉树的五种基本形态（a）(b)(c)(d)(e)二叉树的性质(1)性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。(2)性质2：深度为k的二叉树的最大结点数为2k-1(k≥1)。(3)性质3：对任何一棵二叉树T，如果其终端结点数为n,度为2的结点数为n2,则n0=n2+1(4)一棵深度为k且有2k-1个结点的二叉树称满二叉树。特点：每层上的结点数都为最大结点数，除终端结点外，每个结点都有两棵子树。二叉树的性质(续)（5）完全二叉树：如深度为k，有

6、N个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到N的结点一一对时，称之为完全二叉树。完全二叉树的特点是：深度为k的完全二叉树，其前k-1层是一棵满二叉树，最后第k层结点都尽量排在靠左的位置上。显然一棵满二叉树一定是完全二叉树，但一棵完全二叉树不一定是满二叉树。二叉树的性质(续)（6）完全二叉树的两个特性：性质4：具有n个结点的完全二叉树的深度为└Log2n┘+1。性质5：如果对一棵有n个结点的完全二叉树（其深度为└Log2n┘+1）的结按顺序编号，则任一结点i(1≤i≤n)有

7、：①如i=1,则结点i是二叉树的根结点，若i>1，则i的双亲结点为结点┗i/2┛;②如2i≤n，则i的左孩子是结点2i，否则无左孩子；③若2i+1≤n，则i的右孩子是结点2i+1,否则无右孩子。二叉树二、二叉树的存储结构（一）顺序存储结构用一组连续的存储单元存储二叉树的数据元素，按满二叉树的结点顺序编号依次存放二叉树中数据元素。012345T(6)图5-3完全二叉树ABCDEFABCDEF二叉树的存储结构（二）链式存储结构链表的结点至少包含：数据域和左右指针域的链有时还需增一指向双亲的指针域，有两个

8、指针域的链表称为二叉链表，有三个指针域的链表称为三叉链表，如图5-5所示：例5-3分别画出二叉树链式存储结构5.3遍历二叉树一、定义：遍历二叉树：是指如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。简言之，以一定规则将二叉树中结点排列成一个线性序列。一般情况下，树以二叉链表的形式存储，其结点类型中定义如下：typedefstructnode2{chardata;structnode2*lchild;structnode2*rchild;