144-9

链式存储的二叉树，交换左右结点位置

递归

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100

typedef struct node{
    int data;
    struct node *lchild,*rchild;
}TreeNode,*Tree;

void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;    
    }
    else
    {
        T=(TreeNode*)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild);
    }
}

void PreOrder(Tree T)        //先序遍历 
{
    if(T!=NULL)
    {
        printf("%d  ",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void Swap(Tree &T)
{
    if(T==NULL)
        return;
    TreeNode *p=T->lchild;
    T->lchild=T->rchild;
    T->rchild=p;
    Swap(T->lchild);
    Swap(T->rchild);
}

int main()
{
    Tree T;
    CreateTree(T);
    PreOrder(T);
    printf("\n");
    Swap(T);
    PreOrder(T);
    printf("\n");
    return 0;
}