1、實驗二 二叉樹的存儲結(jié)構(gòu)及各種運(yùn)算的實現(xiàn)第一題：#include "stdio.h"#include "malloc.h"#define maxsize 66typedef int datatype;typedef struct node datatype data ; struct node *lchild,*rchild; bitree;bitree *Qmaxsize;bitree *creatree()char ch;int front,rear;bitree *root,*s;root=NULL;front=1;rear=0;ch=getcha

2、r();while (ch!='#')s=NULL;if(ch!='')s=malloc(sizeof(bitree);s->data=ch;s->lchild=NULL;s->rchild=NULL;rear+;Qrear=s;if(rear=1) root=s;elseif (s&&Qfront)if(rear%2=0)Qfront->lchild=s;elseQfront->rchild=s;if(rear%2=1)front+;ch=getchar();return root;preorder(bitree

3、*t) /前if (t)printf(" %c ",t->data);preorder(t->lchild);preorder(t->rchild);inorder(bitree *t) /中if (t)inorder(t->lchild);printf(" %c ",t->data);inorder(t->rchild);postorder(bitree *t) /后if (t)postorder(t->lchild);postorder(t->rchild);printf(" %c "

4、;,t->data);int height(bitree *t) /高度int hl,hr;if(!t) return 0;elsehl=height(t->lchild);hr=height(t->rchild);return (hl>hr?hl:hr)+1);int leaf(bitree *t) /葉子 static int s; if(t) leaf(t->lchild); leaf(t->rchild); if(t->lchild=NULL&&t->rchild=NULL) s=s+1; return s;main()b

5、itree *t;int x,y;printf("輸入數(shù)據(jù)，以#做結(jié)尾:n");t=creatree();printf("preorder:t");preorder(t);printf("ninorder:t");inorder(t);printf("npostorder:t");postorder(t);x=height(t);y=leaf(t);printf("n高度:%d",x);printf("n葉子:%d",y); printf("n");第二題

6、：#include <stdio.h>#include <malloc.h>#define maxsize 40typedef struct node char data; struct node *lchild,*rchild; int ltag,rtag; bitree;bitree *Qmaxsize; /*隊列*/bitree *pre=NULL;bitree *creatree() char ch; int front,rear; /*隊頭、隊尾*/ bitree *root,*s; root=NULL; /*空樹*/ front=1; rear=0; /*空

7、隊*/ ch=getchar(); while(ch!='#') s=NULL; if(ch!='') /*建立新結(jié)點(diǎn)*/ s=(bitree *)malloc(sizeof(bitree); s->data=ch; s->lchild=s->rchild=NULL; s->ltag=s->rtag=0; rear+; Qrear=s; /*入隊*/ if(rear=1) root=s; else if(s && Qfront) /*孩子、雙親均非空*/ if(rear%2=0) Qfront->lchild=

8、s; else Qfront->rchild=s; if(rear%2=1) front+; /*出隊*/ ch=getchar(); return root;/中序遍歷;void inorder(bitree *t) if(t) inorder(t->lchild); printf("%c",t->data); inorder(t->rchild); /中序線索劃;void INTHREAD(bitree *p)if(p!=NULL) INTHREAD(p->lchild); if(p->lchild=NULL) p->ltag=

9、1; if(p->rchild=NULL) p->rtag=1; if(pre!=NULL) if(pre->rtag=1) pre->rchild=p; if(p->ltag=1) p->lchild=pre; pre=p; INTHREAD(p->rchild); /中序線索二叉樹中求中序后繼結(jié)點(diǎn);bitree * inordernext (bitree *p) bitree *q; if(p->rtag=1) return p->rchild; else q=p->rchild; while(q->ltag=0) q=q->lchild; return q; /中序遍歷;void traverseinthread(bitree *p)if(p!=NULL) while (p->ltag=0 ) p=p->lchild; do printf("%c",p->data); p=inordernext(p); while(p!=NULL); void main() bitree *t; t=creatree(); printf("中序遍歷結(jié)果是:n:"); inorder