《数据结构与算法》第6章+树与二叉树新

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

1、数据结构与算法（C++语言版）第6章树与二叉树树的相关概念树的递归定义和逻辑表示法树（Tree）是n（n≥0）个结点的有限集T，当T为空时称为空树，否则它满足以下两个条件：①有且仅有一个特定的数据元素称为根（root）的结点，根结点没有前驱结点；②其余的结点可分为m（m＞0）个互不相交的子集Tl,T2,…,Tm，其中每个集合Ti（1≤i≤m）本身又是一棵树，并称其为根的子树（subtree）。树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。因此，树结构的很多算法都使用了递归方法。树的相关概念例如，下图所示

2、的是一棵具有10个结点的树，其中A是根，其余结点分成两个互不相交的子集：T1={B,D,E,H,I}，T2={C,F,G,J}；T1和T2都是根A的子树，且本身也是一棵树。例如T1，其根为B，其余结点分为两个互不相交的子集；T11={D}，T12={E,H,I}。T11和T12都是B的子树，而T12中E是根，{H}和{I}是两棵互不相交的子树，其本身又是只有一个根结点的树。树的相关概念树的基本术语（1）结点的度（degree）：结点拥有的子树数。例如，图6.1中A的度为2，G的度为1，H的度为0。（2）叶子（终端结点）：度为0的结点。图6.1中，结点D、

3、H、I、F、J都是树的叶子。（3）非终端结点：度不为0的结点。（4）结点的层次：树中根结点的层次为1，其子树的根为第2层，其余类推。（5）树的度：树中所有结点的最大度数。例如，如图6.1所示的树的度为2。树的相关概念（6）树的深度：树中所有结点层次的最大值。例如，如图6.1所示的树深度为4。（7）有序树、无序树：如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树；否则称为无序树。（8）森林：m（m≥0）棵互不相交的树的集合。在树结构中，结点之间的关系又可用家族关系描述，定义如下。（9）孩子、双亲：结点子树的根称为这个结点的孩子，而这个结

4、点又被称为孩子的双亲。例如，在如图6.1所示的树中，B为A的子树T1的根，则B是A的孩子，而A则是B的双亲。树的相关概念（10）子孙：以某结点为根的子树中的所有结点都被称为是该结点的子孙。图6.1中，B的子孙为E、D、H和I。（11）祖先：从根结点到该结点路径上的所有结点。图6.1中，H的祖先为A、B和E。（12）兄弟：同一个双亲的孩子之间互为兄弟。图6.1中，D和E互为兄弟，F和G互为兄弟。（13）堂兄弟：双亲在同一层的结点互为堂兄弟。图6.1中，I和J互为堂兄弟。树的相关概念树的抽象类型定义树的抽象数据类型定义见以下ADT。树的相关概念树的相关概念树

5、的相关概念树的存储结构与遍历树的存储结构1.双亲表示法由树的定义可知，树中任意一个结点的双亲只有一个，因此，在用一组连续空间存储树中结点的信息时，在每个结点中附设一个指向其双亲的指针来指示其双亲结点在链表中的位置。这种方式就是双亲表示法，其形式说明见以下程序。该类成员函数没有完整给出。树的存储结构与遍历树的存储结构与遍历下图显示了一棵树及其双亲表示的存储结构。取某结点的双亲结点的操作PARENT(T,x)可在常量时间内实现。反复调用PARENT操作，直到遇见无双亲的结点为止，便找到了树的根，这就是ROOT(x)操作的执行过程。但是，在这种表示法中，求结点

6、的孩子则需要遍历整个结构。树的存储结构与遍历2.孩子表示法根据树的特点，它的每个结点都可能有子结点，且子结点的个数不确定，因此可给每个结点设置多个指针域，每个指针指向一棵子树的根结点，此方式称为孩子表示法。该表示法的存储方法之一是，采用多重链表的方式，即根据树的度d为每个结点设置d个指针域，如图（a）所示的结点格式。树的存储结构与遍历显然，这种多重链表中的结点是同构的。采用这种结构时，一棵具有n个结点、度为d的树中共有nd个指针域，由于树中只有n–1个分支，也就只用到n–1个指针域，因此必有nd–(n–1)=n(d–1)+1个空链域，空间浪费较大。若采用

7、图（b）所示的结点格式，即链表中的结点具有不同结构，其中d为结点的度，degree域的值同d，此时，虽能节约存储空间，但操作不方便。另一种方法是把每个结点的孩子结点排列起来，形成一个单链表，则n个结点就有n个链表，其中，叶子的孩子链表为空表，链表中增加一个头结点，为方便查找，将这些头结点采用顺序存储结构。树的存储结构与遍历图（a）所示是之前例子中树的孩子表示法。与双亲表示法相反，孩子表示法便于实现对孩子进行的操作，但却不适合对双亲结点进行的操作，为此，可把双亲表示法和孩子表示法结合起来，形成另一个表示方法，如图（b）所示。树的存储结构与遍历以下程序给出孩

8、子表示法的链存储结构的C++语言描述：树的存储结构与遍历3.孩子兄弟表示法此方法