数据结构课件习题6

题 6.33,题 6.45,题 6.39,题 6.51,题 6.47,题 6.59,题 6.60,题 6.43,题 6.48,题 6.50,题 6.54,题 6.66,6.33 已知Li和Ri(i=0,1,n-1)分别指示二叉树中第i个结点的左孩子和右孩子结点，0表示空。试写判别结点u是否是结点v的子孙的算法。,分析：,1。u是否是结点v的子孙 从结点v出发遍历能否到达结点u; “访问” 判结点u是否是结点v的孩子,2。给出的存储结构实质上是一个二叉链表,Status descendent(int L, int R, int u, int v) if (u ,返回,6.45 编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。,分析:,1。在先序遍历二叉树的过程中查找每一个元素值为x的结点；,2。修改其双亲结点的相应指针；,3。释放以它为根的子树上的所有结点，则应该后序遍历以它为根的子树。,void Delete-X( BiTree / if ,返回,6.51 编写一个算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则在输出时应添上。,分析：,1。原表达式即为带括弧的中缀表达式，则解此题应该进行中序遍历；,2。表达式求值应该进行后序遍历，则表明左、右子树的运算应该先于根结点的运算进行；因此，若左、右子树根的运算符的优先数低于根结点运算符的优先数，则应对左子树或右子树的表达式加上括弧。,void Expression(BiTree T) if (T) if (!Isoprator(T-data) ) printf(T-data); / 操作数 else if ( precede(T-data, T-Lchild-data) ) / 根结点运算符的优先数 左子树根结点的优先数 printf(“(”); Expression(T-Lchild); printf(“)”); else Expression(T-Lchild); / 遍历左子树 printf(T-data); / 访问根结点,继续,if (!precede(T - Rchild - data, T- data) ) / 根结点运算符的优先数右子树根结点的优先数 printf(“(”); Expression(T-Rchild); printf(“)”); else Expression(T-Rchild); / 遍历右子树 /else /if(T) / Expression,注：设操作数的优先数的级别最高。,返回,6.59 编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T中所有的边。输出的形式为(k1,k2),(ki,kj),，其中，ki和kj为树结点中的结点标识。,在孩子兄弟链表中,哪一些结点是根的孩子?,void OutEdge(CSTree T) if (T) p=T-firstchild; while (p) printf( T-data, p-data); OutEdge(p); p=p-nextsibling; / 先根遍历输出树中各条边,返回,6.60 编写算法,对一棵以孩子兄弟链表存储的树 T ，统计树中所含叶子结点的个数。,void CountLeaf (BiTree T, int / if / CountLeaf,CSTree T,T-firstchild,T-nextsibling,返回,问:这个算法对吗？,(!T-firstchild ),深度优先搜索遍历的非递归形式的算法： 一般情况下，需要一个“栈”保留一些信息。,例如：遍历二叉树时，需要利用栈保留曾经路过的根结点（中序）；或者保留尚未遍历的右子树的根结点（先序）以便从左子树返回时继续遍历右子树；,后序遍历二叉树的情况要复杂一些，由于根结点的访问在左、右子树的遍历之后，则不仅要保存结点的信息，还应保存“标志”,反之，如果在存储结构中加上适当信息，则可以省略栈。,6.39 假设在二叉链表的结点中增设两个域：双亲域(parent)以指示其双亲结点；标志域(mark:02)以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。,mark域的作用在于识别当前的状态： mark=0 表示当前状态是对结点作第一次访问 mark=1 表示当前状态是对结点作第二次访问 mark=2 表示当前状态是对结点作第三次访问,void postorder( BiTree T) p=T; while (p) switch (p-mark) case 0: p-mark=1; if (p-Lchild) p=p-Lchild; break; case 1: p-mark=2; if (p-Rchild) p=p-Rchild; break; case 2: p-mark=0; visit (p); p=p-parent; break; /switch /postorder,返回,647 编写按层次顺序(同一层自左至右)遍历二叉树的算法。,分析: 按层次遍历的定义: 若树不空，则首先访问根结点， 然后，依照其双亲结点访问的顺序， 依次访问它们的左、右孩子结点; 因此， 需要一个“队列”保存已被访问的结点,void BFSTraverse(BiTree T) InitQueue(Q); / 置空的辅助队列Q if (T) EnQueue(Q, T); / 根结点入队列 while (!QueueEmpty(Q) DeQueue(Q, p); / 队头元素出队并置为p Visit(p); if (p-Lchild) EnQueue(Q, p-Lchild); / 左子树根入队列 if (p-Rchild) EnQueue(Q, p-Rchild); / 右子树根入队列 / while ,继续,若要编写按层次顺序(同一层自左至右)遍历树的算法，则应如何？,分析: 因两者层次遍历的定义相同，则算法雷同， 差别仅在于: 二叉树至多只有左、右两棵子树，而树的子树个数不定，因此，当以孩子-兄弟链表表示树时，需要顺第一个孩子结点的右指针一直往于找到所有孩子结点。,void BFSTraverse(CSTree T) InitQueue(Q); / 置空的辅助队列Q if (T) EnQueue(Q, T); / 根结点入队列 while (!QueueEmpty(Q) DeQueue(Q, p); / 队头元素出队并置为p Visit(p); for (q=p-firstchild; !q; q=q-nextsibling;) EnQueue(Q, q); / 子树根入队列 / while ,返回,6.43 编写递归算法，交换二叉树中所有结点的左右子树,注意：此题不能依中序遍历的次序进行,void swap( BiTree BT ) if (BT) BT-lchild BT-rchild; swap( BT-lchild); swap( BT-rchild); ,返回,6.66 编写算法，由树的双亲表示建孩子-兄弟链表。,算法分析: 假设已建好根结点，则只要在已知双亲链表中找到它的孩子结点，递归依次建各棵子树。,CSTree CrtCSTree( Ptree T ) / 已知树的双亲表，返回树的孩子-兄弟链表 rt = new CSNode; rt-data = T.nodesT.r.data; rt-firstchild = rt-nextsibling = NULL; CrtTree( T, rt, T.r ); /递归建各棵子树 return rt; / CrtCSTree,void CrtTree( Ptree T, CSTree rt, int k ) / 已知树的双亲链表 T 和已建立的指向根的指针rt / 递归建立树的孩子-兄弟链表, k为根在T中的序号 for ( i=0; idata = T.nodesi.data; p-firstchild = p-nextsibling = NULL; if ( !rt-firstchild) rt-firstchild = p; else rt-nextsibling = p; q = p; /if /CrtTree,返回,6.48 编写算法，求二叉树中两个结点“最靠近”的共同祖先。,分析: 由二叉树中结点的子孙的定义“以 t 为根的子树中所有结点均为它的子孙”可以推出共同祖先的定义，由此可得到递归算法，显然，这个递归形式的算法效率不高。 另一种分析方法是，从根到该结点路径上所有的点都是它的祖先，则比较两条“路径”上的结点便可找到最靠近的共同祖先。 如何求得路径是本题的关键，显然出要利用“栈”记下遍历到已知结点时历经的结点。,栈的数据元素类型定义: typedef struct BiTree ptr; / 指向二叉树中结点的指针 int tag; / 标志，向左为“0”,向右为“1” ElemType;,其它变量说明: succ : 初值为“假”，找到两个结点之后设为“真”; a : 初值为空，找到第一个结点时，指向它的双亲，之 后指向最靠近它们的共同祖先; k : 指示栈中元素个数(即路径长度),初值为“0”;,BiTNode *ancestor( BiTree rt, BiTNode *p, BiTNode *q ) / p 和q 分别指向以 rt 为根指针的二叉树上两个结点， / 若它们在此二叉树中存在共同祖先，则返回指向最 / 靠近这两个结点的共同祖先，否则返回 NULL InitStack(S); w.ptr=rt; w.tag=0; a = NULL; / a 指向最靠近的共同祖先 succ=FALSE; k=0; do / 先序遍历二叉树 while ( StackEmpty(S) | succ); if (succ) return a ; else return NULL; / *ancestor,返回,while (w.ptr w.ptr:=w.ptr-lc /if /while if (! Succ),返回上一页, / 继续向右遍历 ,right:=true; while( !StackEmpty(S) w.tag=0 /else ,返回上一页,6.50 编写算法，由按层次输入的三元组(表示二叉树中一个分支)建二叉树的二叉链表。,分析: 根据二叉树结点的信息是按层次(自上而下，自左至右)次序输入，自然建立二叉链表可在“层次遍历”中进行。 除了根结点之外，在建立每个结点的同时，必须修改其双亲指针域的值，为了便于找到当前建立的结点的双亲，需要一个和输入顺序特点“先进先出”相一致的结构-“队列”保存已建好的结点的“地址”。 则此题不能递归求解。,void Crt_BT(BiTree /else /Crt_BT, / 继续输入其余结点信息,返回,cin e.f e.c e.tag; while (e.f != #) /while,返回上一页,6.54 编写算法，由已知的完全二叉树的顺序存储表示 sa 建二叉链表。,分析: 根据完全二叉树的特性， sa.elm1是二叉树的根结点; sa.elem2i是sa.elemi的左孩子(2i sa.last) sa.elem2i+1是sa.elemi的右孩子(2i+1sa.last) 则此题可以递归求解。,BiTree Build(SqList sa, int i