数据结构与算法分析 C语言描述（原书第2版）课后习题参考答案

#include <stdio.h> #include <stdlib.h> #include "sqstack.h" #include "csqqueue.h" #include "childlisttree.h" /*===================内部接口===================*/ /*******根据合法的结点编号或指向它的指针*******/ //备注: 结点编号从0开始 /*验证运算: 验证用户提供的结点编号node_loc的合法性*/ int VerifyNode_Internal(ChildListTree T, int node_loc) { if(node_loc < 0 || node_loc > T.n - 1) return NOT_EXIST; return EXIST; } /*访问双亲运算: 返回给定结点的双亲编号或指向其双亲的指针*/ void GetParent_Internal(ChildListTree T, int node_loc, int *parent) { int i; Tree_ListNode *p = NULL; if(0 == node_loc) *parent = IS_ROOT; else { for(i = 0; i <= T.n - 1; i++) { p = T.nodes[i].first; while(NULL != p) { if(p->childno == node_loc) { *parent = i; break; } p = p->next; } if(NULL != p) break; } } } /*访问最左孩子运算: 返回给定结点的最左孩子编号或指向其最左孩子的指针*/ void GetLeftChild_Internal(ChildListTree T, int node_loc, int *leftchild) { Tree_ListNode *p = NULL; p = T.nodes[node_loc].first; //结点的最左孩子是它的孩子中编号最小的那个结点 *leftchild = T.n; while(NULL != p) { if(*leftchild > p->childno) *leftchild = p->childno; p = p->next; } if(*leftchild == T.n) *leftchild = NOT_EXIST; } /*访问右兄弟运算: 返回给定结点的右兄弟编号或指向其右兄弟的指针*/ void GetRightSibling_Internal(ChildListTree T, int node_loc, int *rightsibling) { Tree_ListNode *p = NULL; int parent; GetParent_Internal(T, node_loc, &parent); p = T.nodes[parent].first; while(NULL != p) { if(p->childno == node_loc + 1) //如果结点有右兄弟的话其编号一定比其大1 break; p = p->next; } if(NULL != p) *rightsibling = node_loc + 1; else *rightsibling = NOT_EXIST; } /*访问孩子运算: 输出给定结点的所有孩子的信息*/ void GetChild_Internal(ChildListTree T, int node_loc, int *num_children) { Tree_ListNode *p = NULL; *num_children = 0; p = T.nodes[node_loc].first; if(NULL == p) { printf("The node %c is leaf, it has no child!\n", T.nodes[node_loc].data); return; } printf("The node %c's children's (ID, value) are: ", T.nodes[node_loc].data); while(NULL != p) { (*num_children)++; printf("(%d, %c) ", p->childno, T.nodes[p->childno].data); p = p->next; } printf("\n"); } /*访问祖先运算: 输出给定结点的所有祖先的信息*/ void GetAncestor_Internal(ChildListTree T, int node_loc, int *num_ancestor) { int id_parent; *num_ancestor = 0; GetParent_Internal(T, node_loc, &id_parent); if(IS_ROOT == id_parent) { printf("The node is root, it has not ancestor!\n"); return; } printf("The node %c's ancestors' (ID, value) are: ", T.nodes[node_loc].data); while(IS_ROOT != id_parent) { (*num_ancestor)++; printf("(%d, %c) ", id_parent, T.nodes[id_parent].data); GetParent_Internal(T, id_parent, &id_parent); } printf("\n"); } /*先序遍历运算: 在先序遍历的过程中对每个结点调用一次visit()操作*/ void PreTraverseTree_Internal(ChildListTree T, int (*visit)(DataType node)) { int *visit_array = NULL, i, num_notvisited; Tree_ListNode *p = NULL; SqStack S; ElemType e; InitStack(&S); visit_array = (int *)malloc(sizeof(int) * T.n); for(i = 0; i <= T.n - 1; i++) visit_array[i] = 0; //初始时所有结点均未被访问过 (*visit)(T.nodes[0].data); //访问根结点 visit_array[0] = 1; Push(&S, 0); num_notvisited = T.n - 1; //尚未访问的结点的个数 while(0 < num_notvisited && !StackEmpty(S)) { GetTop(S, &e); p = T.nodes[e].first; while(NULL != p) { if(0 == visit_array[p->childno]) { (*visit)(T.nodes[p->childno].data); visit_array[p->childno] = 1; num_notvisited--; Push(&S, p->childno); break; } p = p->next; } if(NULL == p) //以栈顶结点为根的子树先序遍历结束 Pop(&S, &e); } free(visit_array); visit_array = NULL; } /*后序遍历运算: 在后序遍历的过程中对每个结点调用一次visit()操作*/ void PostTraverseTree_Internal(ChildListTree T, int (*visit)(DataType node)) { int *visit_array = NULL, i; Tree_ListNode *p = NULL; SqStack S; ElemType e; InitStack(&S); visit_array = (int *)malloc(sizeof(int) * T.n); for(i = 0; i <= T.n - 1; i++) visit_array[i] = 0; //初始时所有结点均未被访问过 //找最左叶子 e = 0; Push(&S, 0); p = T.nodes[0].first; while(NULL != p) { e = p->childno; Push(&S, e); p = T.nodes[e].first; } //开始遍历 while(!StackEmpty(S)) { Pop(&S, &e); (*visit)(T.nodes[e].data); visit_array[e] = 1; GetTop(S, &e); p = T.nodes[e].first; while(NULL != p) { if(0 == visit_array[p->childno]) { Push(&S, p->childno); p = T.nodes[p->childno].first; } else p = p->next; } } } /*层次遍历运算: 在层次遍历的过程中对每个结点调用一次visit()操作*/ void LevelTraverseTree_Internal(ChildListTree T, int (*visit)(DataType node)) { Tree_ListNode *p = NULL; CSqQueue Q; ElemType e; InitQueue(&Q); EnQueue(&Q, 0); while(!QueueEmpty(Q)) { DeQueue(&Q, &e); (*visit)(T.nodes[e].data); p = T.nodes[e].first; while(NULL != p) { EnQueue(&Q, p->childno); p = p->next; } } } /*===================外部接口===================*/ /*初始化运算: 初始化得到一棵空树*/ int InitTree(ChildListTree *T) { (*T).n = 0; return SUCCESS; } /*判空运算: 判断树T是否为空，若为空返回IS_EMPTYTREE，否则返回ISNOT_EMPTYTREE*/ int TreeEmpty(ChildListTree T) { if(0 == T.n) return IS_EMPTYTREE; return ISNOT_EMPTYTREE; } /*创建运算: 创建一棵树，结点编号从0开始*/ int CreateTree(ChildListTree *T) { int i, j, num_children; Tree_ListNode *p = NULL; Tree_ListNode *ptail_array[MAXSIZE]; printf("Please input the number of the nodes of the tree: "); scanf("%d", &(*T).n); if((*T).n <= 0) { (*T).n = 0; return PARAMETER_ERR; } for(i = 0; i <= (*T).n - 1; i++) { printf("Please input the No.%d node's value: ", i); getchar(); //去掉回车字符 scanf("%c", &((*T).nodes[i].data)); (*T).nodes[i].first = NULL; } //孩子链表采用单链表的尾部创建法 for(i = 0; i <= (*T).n - 1; i++) { printf("Please input the number of children of No.%d node: ", i); scanf("%d", &num_children); for(j = 1; j <= num_children; j++) { p = (Tree_ListNode *)malloc(sizeof(Tree_ListNode)); if(p == NULL) return STORAGE_ERROR; printf("Please input No.%d child's number: ", j); scanf("%d", &(p->childno)); p->next = NULL; if(NULL == (*T).nodes[i].first) { (*T).nodes[i].first = p; ptail_array[i] = (*T).nodes[i].first; } else { ptail_array[i]->next = p; ptail_array[i] = p; } } } return SUCCESS; } /*求高度运算: 返回树T的高度*/ int TreeHeight(ChildListTree T) { int i, height, depth_node; if(T.n < 3) //当树的结点个数为0、1、2时 return T.n; height = 2; for(i = 3; i <= T.n; i++) { GetAncestor_Internal(T, i-1, &depth_node); depth_node++; if(height < depth_node) height = depth_node; } return height; } /*访问树根运算: 返回树根的值*/ int GetRoot(ChildListTree T, DataType *root) { if(IS_EMPTYTREE == TreeEmpty(T)) return IS_EMPTYTREE; *root = T.nodes[0].data; return SUCCESS; } /*查找运算: 返回结点node的编号*/ int LocateNode(ChildListTree T, DataType node) { int i; for(i = 0; i <= T.n - 1; i++) { if(node == T.nodes[i].data) return i; } return NOT_EXIST; //表示树中不存在值为node的结点 } /*遍历运算: 对树T的每个结点调用有且仅有一次的visit()操作*/ int TraverseTree(ChildListTree T, int (*visit)(DataType node), int Type) { if(IS_EMPTYTREE == TreeEmpty(T)) { printf("This is a empty tree!\n"); return IS_EMPTYTREE; } if(PRE_TRAVERSE == Type) { printf("The tree's pretraverse list is: "); PreTr