遞歸思路比較簡單
算法暴力,不斷疊代
一句話說清算法思想:隻要沒有後代,往下交換就完事了
//交換左右子樹的程式代碼
#include<stdio.h>
#include<malloc.h>
//二叉連結清單的結構類型定義
const int maxsize=1024;
typedef char datatype;
typedef struct node
{
datatype data;
struct node *lchild,*rchild;
}bitree;
bitree*creattree();
void preorder(bitree*);
bitree*swap(bitree*);
int main()
{
bitree*pb;
pb=creattree();
preorder(pb);
printf("\n");
swap(pb);
preorder(pb);
printf("\n");
}
//二叉樹的建立
bitree*creattree()
{
char ch;
bitree*Q[maxsize];
int front,rear;
bitree*root,*s;
root=NULL;
front=1;rear=0;
printf("按層次輸入二叉樹,虛結點輸入'@',以'#'結束輸入:\n");
while((ch=getchar())!='#')
{
s=NULL;
if(ch!='@')
{
s=(bitree*)malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)root=s;
else
{
if(s&&Q[front])
if(rear%2==0)Q[front]->lchild=s;
else Q[front]->rchild=s;
if(rear%2==1)front++;
}
}
return root;
}
//先序周遊按層次輸出二叉樹
void preorder(bitree*p)
{
if(p!=NULL)
{
printf("%c",p->data);
if(p->lchild!=NULL||p->rchild!=NULL)
{
printf("(");
preorder(p->lchild);
if(p->rchild!=NULL)printf(",");
preorder(p->rchild);
printf(")");
}
}
}
//添加交換左右子樹算法
bitree*swap(bitree*p)
{
bitree *temp;
temp=p->lchild;
p->lchild=p->rchild;
p->rchild=temp;
if(p->lchild)swap(p->lchild);
if(p->rchild)swap(p->rchild);
return p;
}
複制