数据结构与算法6.ppt

《数据结构与算法6.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构（数据结构及其算法）冯耀霖Chap6树（二）树与森林搜索二叉树哈夫曼树堆§1树与森林▲树的存储结构▲树的实现1.1树的存储结构关于树的存储结构有许多种，这里介绍常用的两种。■父结点数组表示法■左孩子右兄弟表示法1.父结点数组表示法这是一种顺序结构与链结构相结合的树存储方法，它以一组连续的存储单元（数组）来存放树中的结点。每个结点有两个域：data域，存放数据元素；parent域，存放其父结点在数组中的位置序号（下标），相当于父结点的指针，其数值为0（或-1），则表示该结点无父结点，即它是根结点。如图6-1所示树，图6-2所示该树的父结点数组

2、表示法结构。树中结点的存放顺序一般不做特殊要求。如图6-2中使用的是层次方法。ABCDEFGIHJdataparentA0B1C1D1E2F3G4H7I7J7下标12345678910图6.1树图6.2树的父结点表示法2.左孩子右兄弟表示法左孩子右兄弟表示法是目前已知的最节省存储空间的树的链式存储结构方法，它是一种基于递归的定义方式。它的每一个结点由三个域组成：data、leftChild和rightSibling。leftChild域存放的是该结点最左（第一个）孩子的地址，rightSibling域存放的是该结点右兄弟的地址。leftChilddatar

3、ightSibling在图6-1中，树的根结点是A，它没有兄弟，所以它的rightSibling值为空。A有三个孩子，分别为B、C和D，因此它的leftChild值是其最左孩子——结点B的地址。B既有孩子又有兄弟，它的rightSibling指向的是右邻兄弟C，而leftChild指向的是其孩子E。结点E是B的唯一孩子且为叶子，所以它的leftChild值和rightSibling值均为空。依照上述规则可以很方便地建立起树形结构的存储模式。理解该表示方法的关键在于理解它的递归本质。为了帮助理解为什么仅通过每个结点的3个域就能实现整棵树的存储，下面给出对以图

4、6-1中树的基于先序的遍历过程。→先访问根结点A。A无兄弟有左孩子，所以A不入栈，并访问A的左孩子B；→结点B既有孩子也有兄弟，于是B入栈，并访问它的左孩子E；→结点E是叶子，且无兄弟，所以遍历过程回退到结点B；→访问B的右兄弟C，C既有兄弟又有孩子，所以C入栈，并访问C的左孩子F；→结点F是叶子，且无兄弟，所以遍历过程回退到结点C；→访问C的右兄弟D，D无兄弟但有孩子，所以D不入栈，并访问D的左孩子G；→结点G无兄弟有孩子，所以G不入栈，并访问G的左孩子H；→结点H是叶子，但有兄弟，所以H不入栈，并访问H的右兄弟I;→结点I是叶子，但有兄弟，所以I不入栈

5、，并访问I的右兄弟J；→结点J是叶子，也无兄弟，且此时栈为空，至此整个遍历过程结束。由此可见，尽管左孩子右兄弟表示法的每个结点单元仅有3个域，但它们对构建树形结构的复杂模型已经足够了。1.2树的实现以左孩子右兄弟树为例。1.树结点templatestructTreeNode{Typedata;TreeNode*leftChild,*rightSibling;//左孩子右兄弟指针};2.树类templateclassTree{private:TreeNode*root,*current;//

6、根指针与当前指针<基本操作的内部成员函数原型声明>public:<基本操作的外部成员函数原型声明>};3.基本操作的算法SetCurNodeParentElemLeftChildRightSiblingAddNewChildInsertLeftChildInsertSibling算法6.1SetCurNode功能：设置当前结点boolSetCurNode(Typee){//将值为e的结点设置为当前结点returnCurNode(root,e);}算法6.2CurNode功能：设置当前结点boolCurNode(TreeNode*r,Typee){//在根为

7、r的树中查找值为e的结点，将其设置为当前结点if(r==NULL)returnFALSE;if(r->data==e){current=r;returnTRUE;}if(CurNode(r->leftChild,e)==TRUE)//递归遍历r的左孩子returnTRUE;TreeNode*p=r->rightSibling;while(p!=NULL){//递归遍历r的右兄弟if(CurNode(p,e)==TRUE)returnTRUE;p=r->rightSibling;}returnFALSE;}算法6.3ParentElem功能：查找父结点并读取

8、其元素boolParentElem(Typev,Type&e){/