【PTA】交换二叉树中每个结点的左孩子和右孩子 (20 分)

以二叉链表作为二叉树的存储结构，交换二叉树中每个结点的左孩子和右孩子。

输入格式:
输入二叉树的先序序列。

提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。

输出格式:
输出有两行：

第一行是原二叉树的中序遍历序列；

第二行是交换后的二叉树的中序遍历序列。

输入样例:
ABC##DE#G##F###

输出样例:
CBEGDFA

AFDGEBC

组装一个string，用一个全局变量完成交换操作。

#include
using namespace std;
string a;
int a1=0;
typedef struct BiTNode
{char data;BiTNode *lchild,*rchild;
}*BiTree,BiTNode;void precreate(BiTree &T)
{char ch;cin>>ch;a=a+ch;if(ch=='#'){T=NULL;return;}T=new BiTNode;T->data=ch;precreate(T->lchild);precreate(T->rchild);
}void midTravel(BiTree T)
{if(T){midTravel(T->lchild);cout<<T->data;midTravel(T->rchild);}else return;
}void changeTree(BiTree &T,char ch)
{//中右左a1++;if(ch=='#') {T=NULL;return;}T=new BiTNode;T->data=ch;	changeTree(T->rchild,a[a1]);changeTree(T->lchild,a[a1]);return;
}int main()
{BiTree T,T1;precreate(T);midTravel(T);cout<<endl;changeTree(T1,a[a1]);midTravel(T1);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！