刚学数据结构，题目不会，给个代码（算法）参考

Question

1．编写一个C语言程序，对二叉树实现以下操作：
（1）按先根、中根和后根次序遍历二叉树；
（2）按二叉树的层次输出各结点（每一行输出一层）；
（3）利用遍历算法，将二叉树中所有结点的左、右子树交换。
2．假设有一个带头结点的循环链式队列，并且只设一个指向队尾结点的指针（注意没有头指针），试编写相应的队列初始化、入队列和出队列的算法。

Answer 1

1
#include "stdio.h"

#define MAXSIZE 32

typedef char datatype;

typedef struct _Node{
datatype data;
_Node *lchild, *rchild;
}Node, *PNode, *PBitTree;

void visit(PNode node){
printf("%c\t", node->data);
}

(1)
void PreOrder(PBitTree root){
if(!root) return;
visit(root);
PreOrder(root->lchild);
PreOrder(root->rchild);
}

void InOrder(PBitTree root){
if(!root) return;
InOrder(root->lchild);
visit(root);
InOrder(root->rchild);
}

void PostOrder(PBitTree root){
if(!root) return;
PostOrder(root->lchild);
PostOrder(root->rchild);
visit(root);
}

(2)
void Display(PBitTree root){
PNode nodeQueue[MAXSIZE]; /*结点队列*/
int levelQueue[MAXSIZE]; /*用于保存结点层次信息的队列*/
int front=0, rear=0, curlevel = 0, bline = 0; /*bline用于判断是否需要换行*/
PNode p = root;
if(p) { /*根结点入队*/
nodeQueue[rear] = p;
levelQueue[rear] = 0;
rear = (rear + 1) % MAXSIZE;
}
while(front != rear) { /*如果队列不空*/
p = nodeQueue[front]; /*获取队首元素*/
bline = levelQueue[front] != curlevel ? 1 : 0; /*判断是否需要换行*/
curlevel = levelQueue[front];
front = (front + 1) % MAXSIZE; /*出队*/
if(bline) printf("\n"); /*如果需要换行，则输出换行符*/
visit(p);
if(p->lchild) { /*如果左孩子不空，将左孩子入队*/
nodeQueue[rear] = p->lchild;
levelQueue[rear] = curlevel + 1;
rear = (rear + 1) % MAXSIZE;
if(p->rchild) { /*如果右孩子不空，将右孩子入队*/
nodeQueue[rear] = p->rchild;
levelQueue[rear] = curlevel + 1;
rear = (rear + 1) % MAXSIZE;
}
}
}

(3)
void Exchange(PBitTree root) {
if(!root) return;
PNode tmp;
Exchange(root->lchild);
Exchange(root->rchild);
tmp = root->lchild;
root->lchild = root->rchild;
root->rchild = tmp;
}

2
typedef char datatype;

typedef struct _listNode{
datatype data;
_listNode *next;
}RQueueNode, *PRQueueNode, *PRQueue;

PRQueue rear;

void InitRQueue( ) { /*初始化队列*/
rear = (PRQueue) malloc(sizeof(RQueueNode)); /*生成附加头结点*/
rear->next = rear; /*设置为循环的空队*/
}

void EnRQueue(datatype x) { /*入队*/
PRQueueNode *newNode;
newNode = (PRQueue) malloc(sizeof(RQueueNode)); //生成新结点
newNode->data = x;
newNode->next = rear->next; /*将新结点链接到队尾*/
rear->next = newNode;
rear = newNode; /*将新结点作为新的队尾*/
}

datatype DeRQueue( ) { /*出队*/
PRQueueNode *front; /*队首指针*/
datatype tmp; /*用于返回队首元素数据*/
assert(rear->next != rear); /*断言队列不空*/
front = rear->next->next;
rear->next->next = front->next;
if(rear == front) rear = rear->next; /*如果出队的是队列中的最后一个结点*/
tmp = front->data;
free(front);
return tmp;
}