假设二叉树中的每个结点值为单个字符，采用二叉链存储，设计一个算法把二叉树b的左右子树进行交换得到新的二叉树t

假设二叉树中的每个结点值为单个字符，采用二叉链存储，设计一个算法把二叉树b的左右子树进行交换得到新的二叉树t

用递归交换结点的左右子树

typedef struct BiTreeNode{
    char data;
    struct BiTreeNode *lchild, *rchild;
}BiTreeNode, *BiTree;

void swap_tree(BiTree root){
    if (root == NULL){
        return;
    }
    BiTree temp = root->lchild;
    root->lchild = root->rchild;
    root->rchild = temp;
    swap_tree(root->lchild);
    swap_tree(root->rchild);
}

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7547196
• 这篇博客你也可以参考下：先序遍历的顺序建立二叉链表&&中序遍历二叉树T的递归算法
• 除此之外, 这篇博客: 假设二叉树中每个结点的值为单个字符， 设计一个算法将一棵以二叉链方式存储的二叉树 b 转换成对应的顺序存储结构 a。——含具体实现工程中的 具体实现： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 我用VC++6.0做的工程，共建了5个源代码文件，代码可访问https://github.com/COCO5666/Date_Structure下载（Chapter07/Ch07_10）

  vc6.0（完整绿色版）（支持XP、Win7、Win8、Win10）

  https://blog.csdn.net/COCO56/article/details/84570964

  

  LiBTree.h

  这里为了避免因重复包含LiBTree.h而造成结构体类型（LBTNode）重复定义的错误发生，使用了#ifndef语句：

  #ifndef LiBTree_H
  
  #define LiBTree_H
  
  //代码段
  
  #endif

  上面这句话的意思是如果没有定义过LiBTree_H那么定义LiBTree_H并执行"代码段"，如果已经定义过则会跳过下面的所有语句，#endif用于结束条件编译，编译时与前面最近的#if、#ifdef或#ifndef作为一对，经常一起使用，来进行判断是否编译两者之间的部分代码段（或称程序段）。

  #ifndef LiBTree_H
  
  #define LiBTree_H
  
  #include <cstdio>
  #include <malloc.h>
  
  #define ElemType char
  #define MaxSize 500
  
  typedef struct node
  {
  	ElemType data;
  	struct node *lchild;
  	struct node *rchild;
  }LBTNode;
  
  void CreateLiBTree(LBTNode *&b, char *str);
  void DispLiBTree(LBTNode *b);
  void DestroyLiBTree(LBTNode *&b);
  
  #endif
  
  

  SqBTree.h

  #include "LiBTree.h"
  
  #include <cstdio>
  #include <iostream>
  
  using namespace std;
  
  #define ElemType char
  #define MaxSize 500
  
  typedef ElemType SBTree[MaxSize];
  typedef ElemType SBTNode;
  
  void CreateSqBTFromLiBT(SBTNode *&SB, LBTNode *LB, int index=1);
  void CreateSqBTree(SBTNode *&b, char *str);
  void DispSqBTree(SBTNode *b, int index=1);
  void DestroySqBTree(SBTNode *b);

  LiBTree.cpp

  #include "LiBTree.h"
  
  void CreateLiBTree(LBTNode *&b, char *str)
  {
  	LBTNode *St[MaxSize], *p;
  	int top=-1,k,j=0;
  	char ch;
  	b = NULL;
  	ch = str[j];
  	while(ch!='\0')
  	{
  		switch(ch)
  		{
  		case '(':top++;St[top]=p;k=1;break;
  		case ')':top--;break;
  		case ',':k=2;break;
  		default:p=(LBTNode *)malloc(sizeof(LBTNode));
  			p->data=ch;
  			p->lchild=p->rchild=NULL;
  			if(b==NULL)
  			{
  				b=p;
  			}
  			else
  			{
  				switch(k)
  				{
  				case 1:St[top]->lchild=p;break;
  				case 2:St[top]->rchild=p;break;
  				}
  			}
  		}
  		j++;
  		ch=str[j];
  	}
  }
  
  void DispLiBTree(LBTNode *b)
  {
  	if(b!=NULL)
  	{
  		printf("%c", b->data);
  		if(b->lchild!=NULL || b->rchild!=NULL)
  		{
  			printf("(");
  			DispLiBTree(b->lchild);
  			if(b->rchild!=NULL)
  			{
  				printf(",");
  			}
  			DispLiBTree(b->rchild);
  			printf(")");
  		}
  	}
  }
  
  void DestroyLiBTree(LBTNode *&b)
  {
  	if(b!=NULL)
  	{
  		DestroyLiBTree(b->lchild);
  		DestroyLiBTree(b->rchild);
  		free(b);
  	}
  }
  

  SqBTree.cpp

  #include "SqBTree.h"
  
  void CreateSqBTFromLiBT(SBTNode *&SB, LBTNode *LB, int index)
  {
  	static bool flag = true;
  	if(flag)
  	{
  		SB = (SBTNode *)malloc(sizeof(SBTree));
  		flag = false;
  		for(int j=0; j<MaxSize; j++)
  		{
  			SB[j]='#';
  		}
  	}
  	if(LB!=NULL)
  	{
  		SB[index-1] = LB->data;
  		CreateSqBTFromLiBT(SB, LB->lchild, 2*index);
  		CreateSqBTFromLiBT(SB, LB->rchild, 2*index+1);
  	}
  	else
  	{
  		SB[index] = '#';
  	}
  }
  
  void CreateSqBTree(SBTNode *&b, char *str)
  {
  	b = (SBTNode *)malloc(sizeof(SBTree));
  	int j=0, index=1;
  	for(;j<MaxSize;j++)
  	{
  		b[j]='#';
  	}
  	j=0;
  	char ch;
  	ch = str[j];
  	while(ch!='\0')
  	{
  		switch(ch)
  		{
  		case '(':index=index*2;break;
  		case ')':index=index/2;break;
  		case ',':index=index+1;break;
  		default:
  			b[index-1]=ch;break;
  		}
  		j++;
  		ch=str[j];
  	}
  }
  
  
  void DispSqBTree(SBTNode *b, int index)
  {
  	if(b[index-1]!='#')
  	{
  		printf("%c", b[index-1]);
  		if(b[2*index-1]!='#' || b[2*index] !='#')
  		{
  			printf("(");
  			DispSqBTree(b, 2*index);
  			if(b[2*index] != '#')
  				printf(",");
  			DispSqBTree(b, 2*index+1);
  			printf(")");
  		}
  	}
  }
  
  void DestroySqBTree(SBTNode *b)
  {
  	if(b!=NULL)
  	{
  	free(b);
  	b = NULL;
  	}
  }

  mian.cpp

  #include "LiBTree.h"
  #include "SqBTree.h"
  
  #include "string.h"
  #include <iostream>
  
  using namespace std;
  
  int main()
  {
  	char str[]="A(B,C)";
  	int i;
  	SBTNode *SB, *SB2;
  	LBTNode *LB;
  
  	CreateLiBTree(LB, str);
  	DispLiBTree(LB);
  	cout  << endl;
  
  	CreateSqBTree(SB, str);
  	for(i=0; i<10; i++)
  		cout << SB[i];
  	cout << endl;
  	DispSqBTree(SB);
  	cout << endl;
  
  	CreateSqBTFromLiBT(SB2, LB);
  	for(i=0; i<10; i++)
  		cout << SB2[i];
  	cout << endl;
  	DispSqBTree(SB2);
  	cout << endl;
  
  	DestroyLiBTree(LB);
  	DestroySqBTree(SB);
  	DestroySqBTree(SB2);
  	return 0;
  }