TZOJ 5425：数据结构实验—交换二叉树结点的左右孩子（二叉链表存储）

描述

给定一棵二叉树，以二叉链表存储，要求交换二叉树中每个结点的左右孩子。
部分代码已经给出，请补充完整，提交时请勿包含已经给出的代码。

int main()
{
Bitnode *t;
int n;
scanf("%d",&n);
while(n–)
{
t=CreatBitree_level();
leveltraversing(t);
printf("\n");
t=child_swap(t);
leveltraversing(t);
printf("\n");
}
return 0;
}

输入

输入数据分为多组，第一行是测试数据的组数n，下面的n行分别代表一棵二叉树。每棵二叉树结点的值均为正整数，数据为0代表当前结点为空，数据为-1代表二叉树数据输入结束，-1不作处理。二叉树的构造按照层次顺序（即第1层1个整数，第2层2个，第3层4个，第4层有8个…，如果某个结点不存在以0代替）。

输出

每组输出数据有两行，第一行是交换前按照层次遍历二叉树的序列，第二行是交换后按照层次遍历二叉树的序列。

样例输入

2
1 2 0 3 4 -1
1 0 2 0 0 0 3 -1

样例输出

1 2 3 4
1 2 4 3
1 2 3
1 2 3

代码

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int date;struct node *left,*right;}Bitnode;
Bitnode *CreatBitree_level()
{
    Bitnode *root,*t,*q[1001];int a,rear=0,front1=1;while(scanf("%d",&a)){
    if(a==-1)break;if(a==0)t=NULL;else{
    t=(Bitnode*)malloc(sizeof(Bitnode));//分配内存t->date=a;t->left=NULL;t->right=NULL;}rear++;q[rear]=t; //入队if(rear==1)  //如果rear为1，表明此时t为根结点root=t;else{
    if(q[front1]!=NULL) {
    if(rear%2==0) //能被二整除为左节点，不能被二整除为右节点q[front1]->left=t;else q[front1]->right=t;}if(rear%2==1) //只有当一个节点左右都挂满的时候才给下一个节点挂叶子front1++;}}return root;
}
void leveltraversing(Bitnode *root) //层次遍历：一层一层往下遍历
{
    Bitnode *t,*q[1001];int rear=0,front1=1;q[++rear]=root;while(rear>=front1) //循环到队列为空为止{
    t=q[front1];front1++;printf(" %d",t->date);if(t->left!=NULL)   //左节点不为空就入队q[++rear]=t->left;if(t->right!=NULL)   //右节点不为空就入队q[++rear]=t->right;}
}
Bitnode* child_swap(Bitnode* root)
{
    if(root==NULL) //如果根节点为空就返回return 0;if(root->left!=NULL)root->left=child_swap(root->left); //左节点不为空就对左节点的叶子进行交换if(root->right!=NULL)root->right=child_swap(root->right);Bitnode *t; //左右节点交换t=root->left;root->left=root->right;root->right=t;return root;
}
int main()
{
    Bitnode *t; int n;scanf("%d",&n);while(n--){
    t=CreatBitree_level();leveltraversing(t);printf("\n");  t=child_swap(t);leveltraversing(t);printf("\n"); }return 0;
}