第五六章程序题.ppt

第五章、数组和广义表习题 typedef char ElemType; typedef enum{ATOM,LIST}ElemTag; typedef struct GLNode { ElemTag tag; union{ ElemType e; struct{ struct GLNode *hp,*tp; }ptr; }; }*GList; 1、求广义表的表头 GList Head(GList ls) { GList p; if(ls-tag==ATOM) p=ls-ptr.hp; return p; } 2、求广义表的表尾 GList Tail(GList ls) { GList p; if(ls-tag==LIST) p=ls-ptr.tp; return p; } 3、求广义表的深度 int Depth(GList ls) { int max,dep; GList p; if(!ls) return 1; if(ls-tag==ATOM) return 0; else for(max=0,p=ls;p;p=p-ptr.tp) { dep=Depth(p-ptr.hp); if(depmax) max=dep; } return max+1; } 第六章程序设计题 1、统计二叉树中叶子结点的个数 方法1. void CountLeaf (BiTree T, int count)　{　　// 先序遍历二叉树，以 count 返回二叉树中叶子结点的数目 　　if ( T ) {　　　if ((!T-Lchild) (!T-Rchild))　　　　count++; 　　　　 　　　// 对叶子结点计数 　　　　CountLeaf( T-Lchild, count); 　　　　CountLeaf( T-Rchild, count); 　　} // if　} 求二叉树的深度 void BiTreeDepth(BiTree T, int level, int depth)　{// T指向二叉树的根，level 为 T 所指结点所在层次，其初值为1，depth 为当前求得的最大层次,其初值为0　　if (T){　　　if (leveldepth) depth=level; 　　　BiTreeDepth(T-Lchild, level+1, depth);　　　BiTreeDepth(T-Rchild, level+1, depth);　　}　} 4、在二叉树上查询某个结点 void locate(BiTree T,ElemType x,BiTree p){　// 若二叉树 T 中存在和 x 相同的元素，则 p 指向该结点，否则 p 的值不变，p 的初值为 NULL　if (T)　{ if (T-data==x) p=T;　　locate(T-lchild, x, p);　　locate(T-rchild, x, p);　}} 例6: 编写按层次（同一层从左至右）遍历二叉树的算 法。 void LayerOrder(Bitree T)//层序遍历二叉树 {??InitQueue(Q); ?? 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); ?} } 例7、具有n个结点的完全二叉树，已经顺序存储在一维数组A[1..n]中，下面的算法是将A中顺序存储的二叉树变为二叉链表存储的完全二叉树 #define n 10 TElemType A[n+1]; void CreaBiTree(BiTree T,int i) { T=(BiTree)malloc(sizeof(BiTNode)); T-data=A[i]; if(i*2=n) CreaBiTree(T-lchild,i*2); else T-lchild=NULL; if(i*2+1=n) CreaBiTree(T-rchild,i*2+1); else T-rchild=NULL; } 例8、统