非递归队列实现二叉树交换
#include <stdio.h>#include <stdlib.h>
typedef char ElemType;
//二叉链表的存储类型
typedef struct Node
{
ElemType data;
struct Node *lchild,*rchild;
} BitTree;
//先序建立二叉树
BitTree *CreBitTree(void)
{
BitTree *bt;
ElemType x;
scanf("%c",&x);
if(x=='#')//结束标志
bt=NULL;
else
{
bt=(BitTree *)malloc(sizeof(BitTree));
bt->data=x;
bt->lchild=CreBitTree();
bt->rchild=CreBitTree();
}
return bt;
}
//后序递归输出结点信息
void PostOrder(BitTree *bt)
{
if(bt!=NULL)
{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
printf("%c",bt->data);
}
}
//队列
typedef struct QNode
{
BitTree data;
struct QNode *next;
}QNode;
typedef struct
{
QNode *front;
QNode *rear;
}LinkQueue;
//队列初始化
BitTree initQueue(LinkQueue *LQ)
{
LQ->front=LQ->rear=(QNode*)malloc(sizeof(QNode));
LQ->front->next=NULL;
}
//队列入队
BitTree enQueue(LinkQueue*LQ,BitTree *x)
{
QNode *enQuep;
enQuep=(QNode*)malloc(sizeof(QNode));
enQuep=x->data;
enQuep->next=NULL;
LQ->rear->next=enQuep;
LQ->rear=enQuep;
}
//队列出队
int outQueue(LinkQueue *LQ)
{
QNode* outQuep;
BitTree *e;
if(LQ->front==LQ->rear)//队列为空
return 0;
outQuep=LQ->front->next;//首个数据结点给outQuep
e=outQuep;//outQuep给e
LQ->front->next=outQuep->next;//outQuep下一个结点作为首个数据结点
printf("%c",e->data);
if(LQ->rear==outQuep)//如果outQuep与rear指针重合
LQ->rear=LQ->front;//
free(outQuep);
return 1;
}
//非递归交换左右子树 层次遍历 交换
void ExChangeTree(BitTree *bt)
{
LinkQueue *LQ;
initQueue(LQ);
BitTree *temp;//建立用来交换的临时树temp
BitTree *p;
if(bt==NULL)
printf("树为空\n");
enQueue(LQ,bt);//树的根结点插入队尾
while(LQ->front!=LQ->rear)//队列不为空循环
{
outQueue(LQ); //队头结点出队
printf("%c",bt->data);
//判断左孩子，左孩子进队列
if(p->lchild)
{
enQueue(LQ,bt->lchild);
}
if(p->rchild)
{
enQueue(LQ,bt->rchild);
}
temp =bt->lchild;
bt->lchild=bt->rchild;
bt->rchild=temp;//交换
}
}
//主函数部分
int main(void)
{
BitTree *bt;
printf("请以先序遍历输入并以“# ”结束：");
bt=CreBitTree();
printf("输出后序遍历:\n");
PostOrder(bt);
printf("\n");
printf("交换左右子树\n");
ExChangeTree(bt);//有问题
printf("交换后输出后序遍历:\n");
PostOrder(bt);
printf("\n");
printf("程序结束");
}
编译错修改完了但是不知道哪里有错误交换不了
页:
[1]