1)用二叉链表作为存储结构;
2)分别按先序,中序和后序遍历二叉树;
3)编写交换二叉树中所有结点左右孩子的非递归算法。
请各位高手指示下第三问的算法吧!!小菜不懂
只要懂遍历,这个应该没问题的
void Child_change(BiTree T)
{
Queue *Q;
BiTree s=T,p=q=NULL;
InitQueue(&Q);
if (T)
{
EnQueue(&Q,s);
while (Q->rear->next!=Q->rear)
{
s=DeQueue(&Q);
p=s->lchild;
q=s->rchild;
s->lchild=q;
s->rchild=p;
if (s->lchild)
EnQueue(&Q,s->lchild);
if (s->rchild)
EnQueue(&Q,s->rchild);
}
}
else
printf("The tree is empty!");
}
还有其它遍历也可以
[此贴子已经被作者于2006-11-18 18:00:21编辑过]
你好,我把它编为如下,但是在main中的createbintree();那里总是跳不出来啊,要怎么办啊?
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#define null 0
#define max 100
typedef struct node{char data;
struct node *lchild,
*rchild;}BTNode;
typedef struct{char data[max];
int f,r;}Queue;
Queue *createemptyq()
{Queue *q;
q=(Queue *)malloc(sizeof(Queue));
q->f=0;
q->r=0;
return q;
}
int queueempty(Queue *q)
{return(q->f==q->r);
}
int queuefull(Queue *q)
{return((q->r+1)%max==q->f);
}
void enqueue(Queue *q,BTNode *x)
{if(queuefull(&q))
printf("overflow\n");
else{q->r=(q->r+1)%max;
q->data[q->r]=x;}
}
void delqueue(Queue *q)
{if(queueempty(&q))
printf("underflow\n");
else q->f=(q->f+1)%max;
}
char queuefront(Queue *q)
{return(q->data[q->f+1]);
}
BTNode *createbintree()
{BTNode *t;
char x;
scanf("%c",&x);
if(x=='#') t=null;
else{
t=(BTNode *)malloc(sizeof(BTNode));
t->data=x;
t->lchild=createbintree();
t->rchild=createbintree();}
return(t);
}
void preorder(BTNode *t)
{if(t!=null)
{printf("%c\n",t->data);
preorder(t->lchild);
preorder(t->rchild);}
}
void postorder(BTNode *t)
{if(t!=null)
{postorder(t->lchild);
postorder(t->rchild);
printf("%c\n",t->data);}
}
void midorder(BTNode *t)
{Queue *q;
BTNode *p;
if(t=null) return;
q=createemptyq();
p=t;
do{
while(p){enqueue(&q,p);
p=p->lchild;}
if(!queuefront(&q))
{p=queuefront(&q);
delqueue(&q);
printf("%c",p->data);
p=p->rchild;}
}while(!queueempty(&q)||q);
}
void child_change(BTNode *t)
{Queue *Q;
BTNode *s,*p,*q;
s=t;
p=q=null;
Q=createemptyq();
if(t)
{enqueue(&Q,s->data);
while(Q->f+1!=Q->r)
{delqueue(&Q);
p=s->lchild;
q=s->rchild;
s->lchild=q;
s->rchild=p;
if(s->lchild)
enqueue(&Q,s->lchild);
if(s->rchild)
enqueue(&Q,s->rchild);
}
}
else
printf("the tree is emptry!");
}
main()
{int n;
BTNode *r;
clrscr();
printf("create bintree\n");
r=createbintree();
printf("root order search\n");
preorder(r);
printf("\nmiddle order search\n");
midorder(r);
printf("\nlast order search\n");
postorder(r);
child_change(r);
printf("\nresult of the change:\n");
printf("\nmiddle order search\n");
midorder(r);
}