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

《数据结构二叉树遍历及线索化后各种操作(绝对无错)(共9页).doc》由会员分享，可在线阅读，更多相关《数据结构二叉树遍历及线索化后各种操作(绝对无错)(共9页).doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上实验二 二叉树的存储结构及各种运算的实现第一题：#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 (

2、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(

3、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 (hlhr?hl:hr)+1);

4、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);p

5、rintf(n高度:%d,x);printf(n叶子:%d,y); printf(n);第二题：#include #include #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; /*空树*/ fron

6、t=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)

7、 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(

8、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#专心-专注-专业