数据结构二叉树遍历及线索化后各种操作(绝对无错)(共9页).doc

精选优质文档-倾情为你奉上实验二 二叉树的存储结构及各种运算的实现第一题：#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=getchar();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 *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 ",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()bitree *t;int x,y;printf("输入数据，以#做结尾: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");第二题：#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; /*空队*/ ch=getchar(); while(ch!='#') s=NULL; if(ch!='') /*建立新结点*/ 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=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=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); /中序线索二叉树中求中序后继结点;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("中序遍历结果是:n:"); inorder(t); printf("n"); INTHREAD(t); printf("线索化中序遍历的结果是：n"); printf("n"); traverseinthread(t);printf("n")；输入数据为：abfcdge#专心-专注-专业