以二叉链表作为二叉树的存储结构，交换二叉树中每个结点的左孩子和右孩子。
输入格式:
输入二叉树的先序序列。
提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。
输出格式:
输出有两行：
第一行是原二叉树的中序遍历序列；
第二行是交换后的二叉树的中序遍历序列。
输入样例:
ABC##DE#G##F###
输出样例:
CBEGDFA
AFDGEBC
需要三个函数：根据前序输入生成树，交换，中序输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
//根据有#的前序遍历生成树
tree fcreate()
{
tree t;
char s;
//按每个字符输入
scanf("%c",&s);
if(s=='#')return nullptr;
else {
t=(tree)malloc(sizeof(struct treenode));
t->data = s;
t->lchild = fcreate();
t->rchild = fcreate();
return t;
}
}
void Inordertranverse(tree t)
{
if(!t)return;
Inordertranverse(t->lchild);
cout<<t->data;
Inordertranverse(t->rchild);
}
//交换每个结点左右子树
void Exchange(tree &bt)
{
tree temp;
if(bt){
temp = bt -> lchild;
bt -> lchild = bt -> rchild;
bt -> rchild = temp;
Exchange(bt -> lchild);
Exchange(bt -> rchild);
}
}
int main()
{
tree t;
t=fcreate();
Inordertranverse(t);
Exchange(t);
Inordertranverse(t);
}
|