下面空的括号里每空一句
#include <alloc.h> #include <stdio.h> #define M 10 typedef struct node { char data; int lt,rt; struct node *lc,*rc; }JD;
JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do { while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr; } if(pr->rc==NULL) { pr->rt=1; pr->rc=p; } pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; } return(t); }
void zxblxss(JD *t) { /* 在中序线索树中找后继的方式遍历中序二叉树*/ JD *p; p=t->lc; do { while(p->lt==0) p=p->lc; printf("%c ",p->data); while(( )&&(p->rc!=t)) { ( ); printf("%c ",p->data); } ( ); }while(p!=t); }
void zxblxss_2(JD *t) { /* 从头结点的rc域找到中序序列中的最后一个结点， 再从最后一个结点起找前驱，遍历中序二叉树*/ JD *p; p=t->rc; do { printf("%c ",p->data); while(( )&&(p->lc!=t)) { p=p->lc; printf("%c ",p->data); } ( ); while(p->rt==0) ( );
}while(p!=t); }
JD *crt_bt_pre(JD *bt) { char ch; printf("ch="); scanf("%c",&ch); getchar(); if(ch==' ') bt=NULL; else { bt=(JD *)malloc(sizeof(JD)); bt->data=ch; bt->lt=bt->rt=0; bt->lc=crt_bt_pre(bt->lc); bt->rc=crt_bt_pre(bt->rc); } return(bt); }
void main() { JD *head=NULL; head=crt_bt_pre(head); head=zxxsh(head); printf("\n"); zxblxss(head); printf("\n"); zxblxss_2(head); }
[此贴子已经被作者于2004-12-09 15:42:29编辑过]
