6-11 二叉树的非递归遍历
本题要求用非递归的方法实现对给定二叉树的 3 种遍历。
函数接口定义：
void InorderTraversal( BinTree BT ); void PreorderTraversal( BinTree BT ); void PostorderTraversal( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; int flag; };
要求 3 个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。
此外，裁判程序中给出了堆栈的全套操作，可以直接调用。
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> typedef enum { false, true } bool; typedef char ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; int flag; }; /*------堆栈的定义-------*/ typedef Position SElementType; typedef struct SNode *PtrToSNode; struct SNode { SElementType Data; PtrToSNode Next; }; typedef PtrToSNode Stack; /* 裁判实现，细节不表 */ Stack CreateStack(); bool IsEmpty( Stack S ); bool Push( Stack S, SElementType X ); SElementType Pop( Stack S ); /* 删除并仅返回S的栈顶元素 */ SElementType Peek( Stack S );/* 仅返回S的栈顶元素 */ /*----堆栈的定义结束-----*/ BinTree CreateBinTree(); /* 裁判实现，细节不表 */ void InorderTraversal( BinTree BT ); void PreorderTraversal( BinTree BT ); void PostorderTraversal( BinTree BT ); int main() { BinTree BT = CreateBinTree(); printf("Inorder:"); InorderTraversal(BT); printf("\n"); printf("Preorder:"); PreorderTraversal(BT); printf("\n"); printf("Postorder:"); PostorderTraversal(BT); printf("\n"); return 0; } /* 你的代码将被嵌在这里 */
输入样例：
如图
输出样例：
Inorder: D B E F A G H C I Preorder: A B D F E C G H I Postorder: D E F B H G I C A
解析
void InorderTraversal( BinTree BT ){//中序遍历 BinTree T=BT; Stack S =CreateStack(); while(T||!IsEmpty(S)){ while(T!=NULL){ Push(S,T); T=T->Left; } T=Pop(S); printf(" %c",T->Data); T=T->Right; } } void PreorderTraversal( BinTree BT ){//先序遍历 BinTree T=BT; Stack S =CreateStack(); while(T||!IsEmpty(S)){ while(T!=NULL){ Push(S,T); printf(" %c",T->Data); T=T->Left; } T=Pop(S); T=T->Right; } } void PostorderTraversal( BinTree BT ){//后序遍历 BinTree T=BT; Stack S =CreateStack(); while(T||!IsEmpty(S)){ while(T!=NULL){ T->flag=0; Push(S,T); T=T->Left; } T=Peek(S); if(T->flag==0){ T->flag++; T=T->Right; } else{ T=Pop(S); printf(" %c",T->Data); T=NULL; } } }
6-12 求二叉树高度
本题要求给定二叉树的高度。
函数接口定义：
int GetHeight( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; };
要求函数返回给定二叉树BT的高度值。
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> typedef char ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; }; BinTree CreatBinTree(); /* 实现细节忽略 */ int GetHeight( BinTree BT ); int main() { BinTree BT = CreatBinTree(); printf("%d\n", GetHeight(BT)); return 0; } /* 你的代码将被嵌在这里 */
输出样例（对于图中给出的树）：
4
解析
int GetHeight(BinTree BT) { int lNum, rNum, Height; if (BT) { lNum = GetHeight(BT->Left); rNum = GetHeight(BT->Right); if (lNum > rNum) Height = lNum; else Height = rNum; return Height + 1; } else { return 0; } }
6-13 邻接矩阵存储图的深度优先遍历
试实现邻接矩阵存储图的深度优先遍历。
函数接口定义：
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );
其中MGraph是邻接矩阵存储的图，定义如下：
typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* 顶点数 */ int Ne; /* 边数 */ WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */ }; typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
函数DFS应从第V个顶点出发递归地深度优先遍历图Graph，遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，要求按序号递增的顺序。题目保证V是图中的合法顶点。
裁判测试程序样例：
#include <stdio.h> typedef enum {false, true} bool; #define MaxVertexNum 10 /* 最大顶点数设为10 */ #define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/ typedef int Vertex; /* 用顶点下标表示顶点,为整型 */ typedef int WeightType; /* 边的权值设为整型 */ typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* 顶点数 */ int Ne; /* 边数 */ WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */ }; typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */ bool Visited[MaxVertexNum]; /* 顶点的访问标记 */ MGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */ void Visit( Vertex V ) { printf(" %d", V); } void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ); int main() { MGraph G; Vertex V; G = CreateGraph(); scanf("%d", &V); printf("DFS from %d:", V); DFS(G, V, Visit); return 0; } /* 你的代码将被嵌在这里 */
输入样例：给定图如下
5
输出样例：
DFS from 5: 5 1 3 0 2 4 6
解析
void DFS(MGraph Graph, Vertex V, void (*Visit)(Vertex)) { Vertex i; Visit(V); Visited[V] = true; for (int i = 0; i < Graph->Nv; i++) { if (Graph->G[V][i] == 1 && !Visited[i]) { DFS(Graph, i, Visit);//进行递归 } } }
6-14 邻接表存储图的广度优先遍历
试实现邻接表存储图的广度优先遍历。
函数接口定义：
void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) );
其中LGraph是邻接表存储的图，定义如下：
/* 邻接点的定义 */ typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{ Vertex AdjV; /* 邻接点下标 */ PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */ }; /* 顶点表头结点的定义 */ typedef struct Vnode{ PtrToAdjVNode FirstEdge; /* 边表头指针 */ } AdjList[MaxVertexNum]; /* AdjList是邻接表类型 */ /* 图结点的定义 */ typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* 顶点数 */ int Ne; /* 边数 */ AdjList G; /* 邻接表 */ }; typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */
函数BFS应从第S个顶点出发对邻接表存储的图Graph进行广度优先搜索，遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，要求按邻接表顺序访问。题目保证S是图中的合法顶点。
裁判测试程序样例：
#include <stdio.h> typedef enum {false, true} bool; #define MaxVertexNum 10 /* 最大顶点数设为10 */ typedef int Vertex; /* 用顶点下标表示顶点,为整型 */ /* 邻接点的定义 */ typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{ Vertex AdjV; /* 邻接点下标 */ PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */ }; /* 顶点表头结点的定义 */ typedef struct Vnode{ PtrToAdjVNode FirstEdge; /* 边表头指针 */ } AdjList[MaxVertexNum]; /* AdjList是邻接表类型 */ /* 图结点的定义 */ typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* 顶点数 */ int Ne; /* 边数 */ AdjList G; /* 邻接表 */ }; typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */ bool Visited[MaxVertexNum]; /* 顶点的访问标记 */ LGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */ void Visit( Vertex V ) { printf(" %d", V); } void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) ); int main() { LGraph G; Vertex S; G = CreateGraph(); scanf("%d", &S); printf("BFS from %d:", S); BFS(G, S, Visit); return 0; }
/* 你的代码将被嵌在这里 */
输入样例：给定图如下
2
输出样例：
BFS from 2: 2 0 3 5 4 1 6
解析
void BFS(LGraph Graph, Vertex S, void (*Visit)(Vertex)) { Visited[S] = true;//标记起始点 Visit(S); int queue[1000], front = 0, rear = 0; queue[rear++] = S;//起始点入队列 PtrToAdjVNode temp;//temp就代表当前点的邻接点的下标 while (front < rear) {//队伍不为空 temp = Graph->G[queue[front++]].FirstEdge; while (temp) { int p = temp->AdjV;//把temp中的下标提取出来 if (!Visited[p]) {//如果p点没有被标记的话 Visited[p] = true; Visit(p); queue[rear++] = p;//储存在队列中 } temp = temp->Next;//指向下一个邻接点 } } }
