5.4 交换二叉树中每个结点的左孩子和右孩子_第3关:交换二叉树每个节点的左孩子和右孩子

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

输入格式:

输入二叉树的先序序列。

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

输出格式:

输出有两行：

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

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

输入样例:

ABC##DE#G##F###

输出样例:

CBEGDFA

AFDGEBC

写的时候发现期中算法设计错了，应该换指针而不是换值o(╥﹏╥)o

主要是考虑不周，换值却没有考虑空指针问题，考虑空指针的话就会发现换值会乱成一团了。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 105
 
typedef struct Tree {
	char c;
	struct Tree *lchild, *rchild;
} tree;
 
char s[N], ch;
int n;
 
tree* create() {
 
	tree *p = (tree*)malloc(sizeof(tree));
	scanf("%c", &ch);
 
	if(ch != '#') {
		p->c = ch;
		p->lchild = create();
		p->rchild = create();
	} else return NULL;
 
	return p;
 
}
 
void mid_order(tree *root) {
 
	if(root == NULL) return;
 
	mid_order(root->lchild);
	printf("%c", root->c);
	mid_order(root->rchild);
 
}
 
void swap_l_r(tree *root) {
 
	if(root == NULL) return;
	if(root->lchild == NULL && root->rchild == NULL) return;
	
	tree *tmp;
	tmp = root->lchild;
	root->lchild = root->rchild;
	root->rchild = tmp;
 
	swap_l_r(root->lchild);
	swap_l_r(root->rchild);
}
 
int main() {
 
	tree *root = create();
 
	mid_order(root);
	puts("");
	swap_l_r(root);
	mid_order(root);
 
	return 0;
}