二叉树交换左右子树的三种实现方式

二叉树交换左右子树的三种实现方式

顺序存储结构

交换左右子树实际上就是同层之间交换位置，在顺序存储结构下，先确定树的深度，再划分层，每个层内做交换即可。

链式存储结构

递归实现很简单，非递归可以借助栈或队列辅助实现。

递归代码：

voidReChange(BiTree root){if(root==NULL)return;else{
        BiTree temp=root->lchild;
        root->lchild=root->rchild;
        root->rchild=temp;ReChange(root->lchild);ReChange(root->rchild);}}

非递归代码：

voidChange(BiTree root){
    BiTree Queue[MAXSIZE];int front=-1;int rear=0;
    Queue[rear]=root;while(rear!=front){
        BiTree p=Queue[++front];
        BiTree temp=p->lchild;
        p->lchild=p->rchild;
        p->rchild=temp;if(p->lchild) Queue[++rear]=p->lchild;if(p->rchild) Queue[++rear]=p->rchild;}}

完整代码：

#include<stdio.h>#include<stdlib.h>#include<math.h>#include<iostream>
using namespace std;typedefchar DataType;#define MAXSIZE 100typedefstruct node
{
    DataType data;struct node *lchild;struct node *rchild;}BiTreeNode,*BiTree;//先序建立二叉树voidCreateBiTree(BiTree &root){char c;
    cin>>c;if(c=='#'){
        root=NULL;}else{
        root=(BiTree)malloc(sizeof(BiTreeNode));
        root->data=c;CreateBiTree(root->lchild);CreateBiTree(root->rchild);}}//递归实现先序遍历voidPreOrder(BiTree root){if(root!=NULL){
        cout<<root->data<<" ";PreOrder(root->lchild);PreOrder(root->rchild);}}//递归实现交换左右子树voidReChange(BiTree root){if(root==NULL)return;else{
        BiTree temp=root->lchild;
        root->lchild=root->rchild;
        root->rchild=temp;ReChange(root->lchild);ReChange(root->rchild);}}//非递归实现交换左右子树voidChange(BiTree root){
    BiTree Queue[MAXSIZE];int front=-1;int rear=0;
    Queue[rear]=root;while(rear!=front){
        BiTree p=Queue[++front];
        BiTree temp=p->lchild;
        p->lchild=p->rchild;
        p->rchild=temp;if(p->lchild) Queue[++rear]=p->lchild;if(p->rchild) Queue[++rear]=p->rchild;}}//测试序列：ABDG###E##CF#H###intmain(){
    BiTree root;CreateBiTree(root);PreOrder(root);
    cout<<endl;ReChange(root);PreOrder(root);
    cout<<endl;Change(root);PreOrder(root);
    cout<<endl;system("pause");return0;}