4-21 二叉树的基本操作 (10分)

T是一个二叉树，函数CreateBiTree(BiTree &T)是创建一颗二叉树（使用数据结构书上的方式），函数PreOrder(BiTree &T)是输出树的先序遍历，函数InOrder(BiTree &T)是输出树的中序遍历，函数PostOrder(BiTree &T)是输出树的后序遍历，函数LevelOrder(BiTree &T)是输出树的层序遍历。数据保证合法。

函数接口定义：

void CreateBiTree(BiTree &T); void PreOrder(BiTree &T); void InOrder(BiTree &T); void PostOrder(BiTree &T); void LevelOrder(BiTree &T);

其中 T 是二叉树。

裁判测试程序样例：

#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode, *BiTree; / typedef BiTNode * QElemType; typedef struct QNode { QElemType data; struct QNode * next; }QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; Status InitQueue_L(LinkQueue &Q) { Q.front = (QueuePtr) malloc (sizeof(QNode)); if (Q.front == NULL) return OVERFLOW; Q.front->next = NULL; Q.rear = Q.front; return OK; } bool QueueEmpty_L(LinkQueue &Q) { return (Q.front == Q.rear); } int QueueLength_L(LinkQueue &Q) { int count = 0; for (QNode *p = Q.front->next; p != NULL; p = p->next) count++; return count; } Status EnQueue_L(LinkQueue &Q, QElemType e) { QNode *s = (QNode *) malloc (sizeof(QNode)); s->data = e; s->next = NULL; Q.rear->next = s; Q.rear = s; return OK; } Status DeQueue_L(LinkQueue &Q) { QNode *q = Q.front->next; Q.front->next = q->next; if (q->next == NULL) Q.rear = Q.front; free(q); return OK; } void PrintQueue_L(LinkQueue &Q) { for (QNode *p = Q.front->next; p != NULL; p = p->next) printf("%c", p->data->data); printf("\n"); } / void CreateBiTree(BiTree &T); void PreOrder(BiTree &T); void InOrder(BiTree &T); void PostOrder(BiTree &T); void LevelOrder(BiTree &T); int main() { BiTree T; CreateBiTree(T); printf("PreOrder:"); PreOrder(T); printf("\n"); printf("InOrder:"); InOrder(T); printf("\n"); printf("PostOrder:"); PostOrder(T); printf("\n"); printf("LevelOrder:"); LevelOrder(T); printf("\n"); return 0; } /* 你的代码将被嵌在这里 */

输入格式：

按照数据结构树上的建图方式，给出建树的字符串

输出格式：

依次输出树的先序遍历，中序遍历，后序遍历和层序遍历

输入样例：

ab#c##d##

输出样例：

PreOrder:abcd InOrder:bcad PostOrder:cbda LevelOrder:abdc

题目判定

#include <stack> #include <queue> using namespace std; void CreateBiTree(BiTree &T) { char data; data = getchar(); if(data == '#') { T = NULL; } else { T=(BiTNode *)malloc(sizeof(struct BiTNode)); T->data = data; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } void PreOrder(BiTree &T) { if(T) { printf("%c",T->data); PreOrder(T->lchild);//遍历左子树 PreOrder(T->rchild);//遍历右子树 } } void InOrder(BiTree &T) { if(T) { InOrder(T->lchild);//遍历左子树 printf("%c",T->data);//输出根节点值 InOrder(T->rchild);//遍历右子树 } } void PostOrder(BiTree &T) { if(T) { PostOrder(T->lchild);//遍历左子树 PostOrder(T->rchild);//遍历右子树 printf("%c",T->data);//输出根节点值 } } void LevelOrder(BiTree &T) { if (!T) { return; } queue<BiTree> TreeQueue; TreeQueue.push(T); BiTree p = T; while (!TreeQueue.empty()) { p = TreeQueue.front(); TreeQueue.pop(); printf("%c", p->data); if (p->lchild) { TreeQueue.push(p->lchild); } if (p->rchild) { TreeQueue.push(p->rchild); } } }

完整代码

#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode, *BiTree; / typedef BiTNode * QElemType; typedef struct QNode { QElemType data; struct QNode * next; }QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; Status InitQueue_L(LinkQueue &Q) { Q.front = (QueuePtr) malloc (sizeof(QNode)); if (Q.front == NULL) return OVERFLOW; Q.front->next = NULL; Q.rear = Q.front; return OK; } bool QueueEmpty_L(LinkQueue &Q) { return (Q.front == Q.rear); } int QueueLength_L(LinkQueue &Q) { int count = 0; for (QNode *p = Q.front->next; p != NULL; p = p->next) count++; return count; } Status EnQueue_L(LinkQueue &Q, QElemType e) { QNode *s = (QNode *) malloc (sizeof(QNode)); s->data = e; s->next = NULL; Q.rear->next = s; Q.rear = s; return OK; } Status DeQueue_L(LinkQueue &Q) { QNode *q = Q.front->next; Q.front->next = q->next; if (q->next == NULL) Q.rear = Q.front; free(q); return OK; } void PrintQueue_L(LinkQueue &Q) { for (QNode *p = Q.front->next; p != NULL; p = p->next) printf("%c", p->data->data); printf("\n"); } / void CreateBiTree(BiTree &T); void PreOrder(BiTree &T); void InOrder(BiTree &T); void PostOrder(BiTree &T); void LevelOrder(BiTree &T); int main() { BiTree T; CreateBiTree(T); printf("PreOrder:"); PreOrder(T); printf("\n"); printf("InOrder:"); InOrder(T); printf("\n"); printf("PostOrder:"); PostOrder(T); printf("\n"); printf("LevelOrder:"); LevelOrder(T); printf("\n"); return 0; } #include <stack> #include <queue> using namespace std; void CreateBiTree(BiTree &T) { char data; data = getchar(); if(data == '#') { T = NULL; } else { T=(BiTNode *)malloc(sizeof(struct BiTNode)); T->data = data; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } void PreOrder(BiTree &T) { if(T) { printf("%c",T->data); PreOrder(T->lchild);//遍历左子树 PreOrder(T->rchild);//遍历右子树 } } void InOrder(BiTree &T) { if(T) { InOrder(T->lchild);//遍历左子树 printf("%c",T->data);//输出根节点值 InOrder(T->rchild);//遍历右子树 } } void PostOrder(BiTree &T) { if(T) { PostOrder(T->lchild);//遍历左子树 PostOrder(T->rchild);//遍历右子树 printf("%c",T->data);//输出根节点值 } } void LevelOrder(BiTree &T) { if (!T) { return; } queue<BiTree> TreeQueue; TreeQueue.push(T); BiTree p = T; while (!TreeQueue.empty()) { p = TreeQueue.front(); TreeQueue.pop(); printf("%c", p->data); if (p->lchild) { TreeQueue.push(p->lchild); } if (p->rchild) { TreeQueue.push(p->rchild); } } }

#结果PTA系统里面没得分！