数据结构与算法6课件.pptVIP

　Chap 6 　树（二） 　　 ?树与森林 ?有哪些信誉好的足球投注网站二叉树 ?哈夫曼树 　　?堆 　 §1 树与森林 ▲树的存储结构 ▲树的实现 1.1 树的存储结构 　　　 　　　关于树的存储结构有许多种，这里介绍常用的两种。 　　　■ 父结点数组表示法 　　　■ 左孩子右兄弟表示法　 1. 父结点数组表示法 　　　这是一种顺序结构与链结构相结合的树存储方法，它以一组连续的存储单元（数组）来存放树中的结点。每个结点有两个域：data域，存放数据元素；parent域，存放其父结点在数组中的位置序号（下标），相当于父结点的指针，其数值为0（或-1），则表示该结点无父结点，即它是根结点。 　　　如图6-1所示树，图6-2所示该树的父结点数组表示法结构。 　　　树中结点的存放顺序一般不做特殊要求。如图6-2中使用的是层次方法。 2. 左孩子右兄弟表示法 　　　左孩子右兄弟表示法是目前已知的最节省存储空间的树的链式存储结构方法，它是一种基于递归的定义方式。它的每一个结点由三个域组成：data、leftChild和rightSibling。leftChild域存放的是该结点最左（第一个）孩子的地址，rightSibling域存放的是该结点右兄弟的地址。 　　　 　　　在图6-1中，树的根结点是A，它没有兄弟，所以它的rightSibling值为空。A有三个孩子，分别为B、C和D，因此它的leftChild值是其最左孩子——结点B的地址。B既有孩子又有兄弟，它的rightSibling指向的是右邻兄弟C，而leftChild指向的是其孩子E。结点E是B的唯一孩子且为叶子，所以它的leftChild值和rightSibling值均为空。依照上述规则可以很方便地建立起树形结构的存储模式。 　　　理解该表示方法的关键在于理解它的递归本质。为了帮助理解为什么仅通过每个结点的3个域就能实现整棵树的存储，下面给出对以图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不入栈，并访问I的右兄弟J； 　　 →结点J是叶子，也无兄弟，且此时栈为空，至此整个遍历过程结束。 　　由此可见，尽管左孩子右兄弟表示法的每个结点单元仅有3个域，但它们对构建树形结构的复杂模型已经足够了。 1.2 树的实现 　 以左孩子右兄弟树为例。 　 1. 树结点 templatetypename Type struct TreeNode{ Type data; TreeNode *leftChild, *rightSibling; //左孩子右兄弟指针 }; 2.树类 　templatetypename Type class Tree{ private: TreeNodeType *root, *current; //根指针与当前指针 基本操作的内部成员函数原型声明 public: 基本操作的外部成员函数原型声明 }; 　 3. 基本操作的算法 　　 　SetCurNode 　　　ParentElem 　　　LeftChild 　　　RightSibling 　　　AddNewChild 　　　InsertLeftChild 　　　InsertSibling 算法6.1 SetCurNode功能：设置当前结点 　bool SetCurNode(Type e) 　{ //将值为e的结点设置为当前结点 　　return CurNode(root, e); 　} 算法6.2 CurNode 功能：设置当前结点 bool CurNode(TreeNode *r, Type e) {//在根为r的树中查找值为e的结点，将其设置为当前结点 if(r==NULL)return FALSE; if(r-data==e){ current=r; return TRUE;} if(CurNode(r-leftChild, e)==TRUE) //递归