chap006树和二叉树习题讲解

1、Chap006树和二叉树习题讲解二叉树的二叉链表类型定义：二叉树的二叉链表类型定义：typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;树的二叉链表类型定义：树的二叉链表类型定义：typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;1.(6.33) 假定用两个一维数组Ln+1和Rn+1作为有n个结点的二叉树的存储结

2、构，Li和Ri分别指示结点i(i=1,2,n)的左孩子和右孩子，0表示空。试写一个算法判别结点u是否为结点v的子孙。o 分析：u是否为v的子孙从结点v出发遍历是否能达到u， “访问”判断u是否为v的孩子Status Descendant(int L,int R,int u,int v)/在孩子存储结构上判断u是否v的子孙 if(u&v) if(Lv=u|Rv=u) return true; else if(descendent(L,R,u,Lv) return true; else return(descendent(L,R,u,Rv); else return false; 2.（6

3、.41）编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值。 int c,k; /这里把k和计数器c作为全局变量处理 void Get_PreSeq(Bitree T)/求先序序列为k的结点的值 if(T) c+; /每访问一个子树的根都会使先序序号计数器加1 if(c=k) printf(Value is %dn,T-data); exit (1); else Get_PreSeq(T-lchild); /在左子树中查找 Get_PreSeq(T-rchild); /在右子树中查找 /if/Get_PreSeq main() . scanf(%d,&k); c=0; /在主

4、函数中调用前,要给计数器赋初值0 Get_PreSeq(T,k); ./main 3.（6.45）编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。分析:1.在先序遍历二叉树的过程中查找每一个元素值为x的结点2.修改其双亲结点的相应指针。3.释放以它为根的子树上的所有结点，则应该后序遍历以它为根的子树。void Del_Sub_x(Bitree &T,ElemType x)/删除所有以元素x为根的子树 if T if(T-data=x) Del_Sub(T); T=NULL; /删除该子树 else /在左右子树中继续查找 Del_Sub_x(T-

5、lchild,x); Del_Sub_x(T-rchild,x); /else /Del_Sub_x void Del_Sub(Bitree T)/删除子树T if(T-lchild) Del_Sub(T-lchild); if(T-rchild) Del_Sub(T-rchild); free(T);/Del_Sub 4.（6.47）编写按层次顺序（同一层自左至右）遍历二叉树的算法。分析： 按层次遍历的原则是先被访问的结点的左右孩子结点先被访问，因此在遍历过程中需利用具有先进先出特性的队列对二叉树：void LayerOrder(Bitree T)/层序遍历二叉树 InitQueue(Q);

6、 /置空的辅助队列Q if (T) EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild); /LayerOrder对树：即为孩子兄弟链表void LayerOrder(CStree T)/层序遍历二叉树 InitQueue(Q); /置空的辅助队列Q if (T) EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); for(q=p-f

7、irstchild;q;q=q-nextsibling) if(q) EnQueue(Q,q); /LayerOrder 5.（6.59）编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T中所有的边。输出的形式为（k1,k2）,（ki,kj）,，其中，ki和kj为树结点中的结点标识。o分析：在孩子兄弟链表中，哪些结点是根的孩子？abecgdVoid OutEdge(CSTree T)If (T) P=T-firstchild; While (p) Printf(T-data,p-data);OutEdge(p); p=p-nextsibling; /先根遍历输出树中各条边上图中的输出次

8、序：(a,b)(b,e)(b,g)(a,c)(a,d)或void Print_CSTree(CSTree T)/输出孩子兄弟链表表示的树T的各边 for(child=T-firstchild;child;child=child-nextsibling) printf(%c,%c),T-data,child-data); Print_CSTree(child); /Print_CSTree 6.编写非递归算法实现：在树T中查找结点X并求出其度数。 分析：度数为结点x的firstchild结点及孩子结点的所有nextsibling结点的个数和。xbcdstatus Degree_X_in_T(CS

9、Tree T,int &d) / 采用二叉链表存储结构，遍历树T查找结点X，若未找到，则返回ERROR，否则计算其度数并赋值给参数d，再返回OKinitStack(S); Push(S,T); /根指针进栈flag=0;while(!StackEmpty(S) /当栈S不空时 while(GetTop(S,p) &p) Push(S,p-firstchild); /孩子入栈，向左走到尽头 Pop(S,p); /空指针出栈 if (!StackEmpty(S) /访问结点，向右一步 Pop(S,p); if (p-data= =X) flag=1;break;/找到结点找到结点X Push(S,