二叉树基本函数

1、一. 二叉树基本函数1.宏定义：#include#include#include#define datatypebt char#define MAXNODE 1024#define BOTTOMNODE 1024#define FULLNODE 10242.结构体：typedef struct bitnodedatatypebt data;struct bitnode *lchild,*rchild;Bitnode,*Bitree;3.基本函数：Bitree Initiate_Bitree()/*初始化二叉树函数1.先决条件:无2.函数作用:初始化一棵空的带头结点的二叉树,返回头结点的地址*/

2、Bitnode *bt;bt=(Bitnode *)malloc(sizeof(Bitnode);bt-lchild=NULL;bt-rchild=NULL;return bt;Bitnode *Create_Bitree(datatypebt x,Bitnode *lbt,Bitnode *rbt)/*建立二叉树函数1.先决条件:无2.函数作用:生成一棵以x为根结点数据域信息,以lbt,rbt为左右子树的二叉树,返回新二叉树的地址*/Bitree p;p=(Bitnode *)malloc(sizeof(Bitnode);p-data=x;p-lchild=lbt;p-rchild=rbt;

3、return p;void Precreate_Bitree(Bitree *T)/*先序构建二叉树函数1.先决条件:T是子树根结点的地址2.函数作用:以先序遍历序列构造二叉树链表存储的二叉树T*/char ch;scanf(%c,&ch);if(ch=0)*T=NULL;else(*T)=(Bitnode *)malloc(sizeof(Bitnode);(*T)-data=ch;Precreate_Bitree(&(*T)-lchild);Precreate_Bitree(&(*T)-rchild);void Preinorder_Bitree(Bitree *t,char preod,i

4、nt i,int j,char inod,int k,int h)/*先中序恢复树函数1.先决条件:t是子树根结点的地址2.函数作用:preodi.j为先序子序列,inodk.h为中子序序列,根据先序序列和中序序列恢复二叉树t*/int m;*t=(Bitnode *)malloc(sizeof(Bitnode);(*t)-data=preodi;m=k;while(inodm!=preodi)m+;if(m=k)(*t)-lchild=NULL;elsePreinorder_Bitree(&(*t)-lchild,preod,i+1,i+m-k,inod,k,m-1);if(m=h)(*t)

5、-rchild=NULL;elsePreinorder_Bitree(&(*t)-rchild,preod,i+m-k+1,j,inod,m+1,h);int Recovery_Bitree(Bitree bt,char preod,char inod,int n)/*先中序恢复树函数1.先决条件:初始化二叉树,bt为头结点,拥有Preinorder_Bitree()函数2.函数作用:根据先序和中序序列恢复二叉树bt,成功返回1*/if(nlchild=NULL;else Preinorder_Bitree(&bt-lchild,preod,0,n-1,inod,0,n-1);return 1

6、;void Postfree_Bitree(Bitree p)/*后序释放函数1.先决条件:p为子树根结点的地址2.函数作用:释放子树p的全部空间*/if(p=NULL)return ;Postfree_Bitree(p-lchild);Postfree_Bitree(p-rchild);free(p);int Empty_Bitree(Bitree bt)/*判空函数1.先决条件:初始化二叉树,bt为头结点2.函数作用:若二叉树bt为空,则返回1,否则返回0*/if(bt-lchild=NULL)return 1;else return 0;Bitnode *Root_Bitree(Bitr

7、ee bt)/*求根函数1.先决条件:初始化二叉树,bt为头结点2.函数作用:求二叉树bt的根结点,返回根结点的地址,若bt为空二叉树,则函数返回NULL*/return bt-lchild;Bitnode *Search_Bitree(Bitree bt,datatypebt x)/*查找函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:在二叉树bt中查找值为x的数据元素,成功返回其地址,找不到返回NULL*/Bitree p=NULL;if(bt)if(bt-data=x)return bt;if(bt-lchild)p=Search_Bitree(bt-lchild,x)

8、;if(p)return p;if(bt-rchild)p=Search_Bitree(bt-rchild,x);if(p)return p;return NULL;int InsertL_Bitree(Bitnode *parent,datatypebt x)/*左插入函数1.先决条件:无2.函数作用:在二叉树中的parent所指结点和其左子树之间插入数据元素为x的结点,成功返回1*/Bitnode *p;if(parent=NULL)printf(插入出错.n);/*此句可以根据情况删除*/return 0;p=(Bitnode *)malloc(sizeof(Bitnode);p-dat

9、a=x;p-lchild=NULL;p-rchild=NULL;if(parent-lchild=NULL)parent-lchild=p;elsep-lchild=parent-lchild;parent-lchild=p;return 1;int InsertR_Bitree(Bitnode *parent,datatypebt x)/*右插入函数1.先决条件:无2.函数作用:在二叉树中的parent所指结点和其右子树之间插入数据元素为x的结点,成功返回1*/Bitnode *p;if(parent=NULL)printf(插入出错.n);/*此句可以根据情况删除*/return 0;p=

10、(Bitnode *)malloc(sizeof(Bitnode);p-data=x;p-lchild=NULL;p-rchild=NULL;if(parent-rchild=NULL)parent-rchild=p;elsep-rchild=parent-rchild;parent-rchild=p;return 1;int DeleteL_Bitree(Bitnode *parent)/*左删除函数1.先决条件:parent为子树的根结点,拥有Postfree_Bitree()函数2.函数作用:在二叉树中删除parent的左子树,成功返回1*/Bitnode *p;if(parent=NU

11、LL|parent-lchild=NULL)printf(删除出错.n);/*此句可以根据情况删除*/return NULL;p=parent-lchild;parent-lchild=NULL;Postfree_Bitree(p);return 1;int DeleteR_Bitree(Bitnode *parent)/*右删除函数1.先决条件:parent为子树的根结点,拥有Postfree_Bitree()函数2.函数作用:在二叉树中删除parent的右子树,成功返回1*/Bitnode *p;if(parent=NULL|parent-rchild=NULL)printf(删除出错.n

12、);/*此句可以根据情况删除*/return NULL;p=parent-rchild;parent-rchild=NULL;Postfree_Bitree(p);return 1;Bitnode *Parent_Bitree(Bitree bt,Bitnode *x)/*求双亲函数1.先决条件:初始化二叉树bt,bt是子树根或头结点;2.函数作用:求二叉树bt中结点x的双亲结点,若结点x是二叉树的根结点或二叉树bt中无结点x,则返回NULL*/Bitnode *p=NULL;if(bt)if(bt-lchild=x|bt-rchild=x)p=bt;return p;p=Parent_Bit

13、ree(bt-lchild,x);if(p)return p;p=Parent_Bitree(bt-rchild,x);if(p)return p;return NULL;void Visit_Bitree(Bitnode *p)/*访问函数1.先决条件:无2.函数作用:输出一个二叉树结点p的数据*/if(p)printf(%c ,p-data);int Countleaf_Bitree(Bitree bt)/*统计叶子数函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:统计二叉树bt中叶子结点的个数,返回值为bt的叶子数*/if(bt=NULL)return 0;if(bt-

14、lchild=NULL&bt-rchild=NULL)return 1;return Countleaf_Bitree(bt-lchild)+Countleaf_Bitree(bt-rchild);void Preorder_Bitree(Bitree bt)/*先序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法先序遍历二叉树bt*/if(bt=NULL)return;Visit_Bitree(bt);Preorder_Bitree(bt-lchild);Preorder_Bitree(bt-rchild);void Inorder_Bitree(Bitre

15、e bt)/*中序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法中序遍历二叉树bt*/if(bt=NULL)return;Inorder_Bitree(bt-lchild);Visit_Bitree(bt);Inorder_Bitree(bt-rchild);void Postorder_Bitree(Bitree bt)/*后序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法后序遍历二叉树bt*/if(bt=NULL)return ;Postorder_Bitree(bt-lchild);Postorder_Bitree(

16、bt-rchild);Visit_Bitree(bt);int NRPreorder_Bitree(Bitree bt)/*非递归先序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:非递归先序遍历二叉树bt,空树返回0,非空树返回1,栈溢出返回-1*/Bitnode *p,*sMAXNODE;/*MAXNODE最少是二叉树的层数h*/int top=-1;if(p=bt)=NULL)printf(此为空二叉树.n);/*此句可以根据情况删除*/return 0;while(p!=NULL|top!=-1)while(p!=NULL)Visit_Bitree(p);top+

17、;if(top=MAXNODE)printf(栈溢出.n);return -1;stop=p;p=p-lchild;p=stop;top-;p=p-rchild;return 1;int NRInorder_Bitree(Bitree bt)/*非递归中序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:非递归中序遍历二叉树bt,空树返回0,非空树返回1,栈溢出返回-1*/Bitnode *p,*sMAXNODE;/*MAXNODE最少是二叉树的层数h*/int top=-1;if(p=bt)=NULL)printf(此为空二叉树.n);/*此句可以根据情况删除*/retu

18、rn 0;while(p!=NULL|top!=-1)while(p!=NULL)top+;if(top=MAXNODE)printf(栈溢出.n);return -1;stop=p;p=p-lchild;p=stop;Visit_Bitree(p);top-;p=p-rchild;return 1;int NRPostorder_Bitree(Bitree bt)/*非递归后序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:非递归后序遍历二叉树bt,p为当前结点指针,q为前驱结点指针,空树返回0,非空树返回1,栈溢出返回-1*/Bitnode *sMAXNODE;/*M

19、AXNODE最少是二叉树的层数h*/int top;Bitnode *p,*q;q=NULL;p=bt;if(!p)return 0;top=-1;while(p!=NULL|top!=-1)while(p!=NULL)top+;if(top=MAXNODE)printf(栈溢出.n);return -1;stop=p;p=p-lchild;if(top-1)p=stop;if(p-rchild=NULL|p-rchild=q)Visit_Bitree(p);q=p;top-;p=NULL;elsep=p-rchild;return 1;int Levelorder_Bitree(Bitree

20、 bt)/*层次遍历二叉树函数1.先决条件:bt是子树根结点2.函数作用:层次遍历二叉树bt,队满溢出返回-1,空树返回0,非空树返回1*/Bitnode *sqBOTTOMNODE;/*MAXNODE最少是2(h-1),其中h为层数*/int front=-1,rear=0,num=0;if(bt=NULL)return 0;if(numlchild)if(num=MAXNODE)printf(队满.n);/*可视情况删除此句*/return -1;elserear=(rear+1)%MAXNODE;sqrear=sqfront-lchild;num+;if(sqfront-rchild)i

21、f(num=MAXNODE)printf(队满.n);/*可视情况删除此句*/return -1;elserear=(rear+1)%MAXNODE;sqrear=sqfront-rchild;num+;return 1;int Posttreedepth_Bitree(Bitree bt)/*后序二叉树高度函数1.先决条件:bt为子树根结点2.函数作用:通过后序遍历求二叉树bt的高度,返回二叉树的高度*/int hl,hr,max;if(bt!=NULL)hl=Posttreedepth_Bitree(bt-lchild);hr=Posttreedepth_Bitree(bt-rchild)

22、;max=hlhr?hl:hr;return max+1;elsereturn 0;void Pretreedepth_Bitree(Bitree bt,int h,int *depth)/*前序二叉树高度函数1.先决条件:bt是子树根结点,h为bt结点所在层次,初值为1,depth为当前求得的最大层次,调用前初值为0;2.函数作用:通过先序遍历求二叉树bt高度*/if(bt!=NULL)if(h*depth)*depth=h;Pretreedepth_Bitree(bt-lchild,h+1,depth);Pretreedepth_Bitree(bt-rchild,h+1,depth);vo

23、id Pretreelevel_Bitree(Bitree bt,int h)/*前序二叉树打印层号函数1.先决条件:bt是子树根结点,h为bt结点所在层次,初值为1;2.函数作用:通过先序遍历打印二叉树bt中结点和层号*/if(bt!=NULL)printf(%d %cn,h,bt-data);Pretreelevel_Bitree(bt-lchild,h+1);Pretreelevel_Bitree(bt-rchild,h+1);void Pretreenode_Bitree(Bitree bt,int *num)/*前序二叉树结点函数1.先决条件:bt是子树根结点,num为累计的结点数,

24、调用前初值为0;2.函数作用:通过先序遍历求二叉树的结点数目num*/if(bt!=NULL)*num=*num+1;Pretreenode_Bitree(bt-lchild,num);Pretreenode_Bitree(bt-rchild,num);int Print1_Bitree(Bitree bt)/*按树状打印二叉树函数1.先决条件:bt是子树根结点,拥有Posttreedepth_Bitree()函数2.函数作用:按树状打印二叉树bt*/int i,j,k,n,flag=1,kongge,chuduigeshu=1;Bitnode *sqFULLNODE,*temp;/*FULL

25、NODE最少为满二叉树结点数+1*/int rear,front,num;if(bt=NULL)return 0;front=rear=FULLNODE-1;num=0;if(num=FULLNODE)printf(队满.n);/*可视情况删除此句*/return -1;elserear=(rear+1)%FULLNODE;sqrear=bt;num+;n=Posttreedepth_Bitree(bt);for(i=1,kongge=1;in;i+)kongge=kongge*2;for(i=1;i=n;i+)j=1;while(j=chuduigeshu)if(flag=1)for(k=1

26、;kdata);/*因二叉树数据类型不同而不同*/if(num=FULLNODE-1)printf(队满.n);/*可视情况删除此句*/return -1;elserear=(rear+1)%FULLNODE;sqrear=temp-lchild;rear=(rear+1)%FULLNODE;sqrear=temp-rchild;num=num+2;elseprintf( );/*因树结点的数据长度不同而不同*/if(num=FULLNODE-1)printf(队满.n);/*可视情况删除此句*/return -1;elserear=(rear+1)%FULLNODE;sqrear=NULL;

27、rear=(rear+1)%FULLNODE;sqrear=NULL;num=num+2;j+;elsefor(k=1;krchild,nlayer+1);for(int i=0;idata);/*因树结点的数据类型不同而不同*/Print2_Bitree(bt-lchild,nlayer+1);4.主函数int main()Bitree bt;bitnode *node,*node2;int choice,length,yezhi,high,num;char s11024,s21024;datatypebt ch,ch2;doprintf(*n);printf(1.初始化二叉树 2.建立二叉

28、树 3.先序构建二叉树 4.先中序恢复树n);printf(5.后续释放树 6.判空二叉树 7.求二叉树根 8.查找二叉结点n);printf(9.左插二叉结点 10.右插二叉结点 11.删左二叉结点 12.删右二叉结点n);printf(13.查找双亲结点 14.访问二叉结点 15.统计叶结点数 16.先序遍历二叉树n);printf(17.中序遍历二叉树 18.后序遍历二叉树 19.非递归先序遍历 20.非递归中序遍历n);printf(21.非递归后序遍历 22.层次遍历二叉树 23.后序求高度 24.前序求高度n);printf(25.树状输出树 26.倒树状输出树 27.打印结点和层

29、号 28.求结点数n);printf(29.退出n);printf(*n);printf(请输入选择(129):);scanf(%d,&choice);getchar();switch(choice)case 1:if(bt=Initiate_Bitree() printf(初始化成功!n); else printf(初始化失败!n);break;case 2:printf(请输入新二叉树结点的数据:); scanf(%c,&ch); printf(至于指针域暂时设为NULL.n); node=Create_Bitree(ch,NULL,NULL); printf(新生成的二叉树结点数据和地址

30、分别为:%c,%xn,node-data,node); break;case 3:printf(请输入要构建的二叉树的先序序列,以0表示空:); Precreate_Bitree(&bt-lchild); printf(构建成功!n); break;case 4:printf(请输入要恢复的二叉树的先序序列:); gets(s1); printf(请输入要恢复的二叉树的中序序列:); gets(s2); length=strlen(s1); if(Recovery_Bitree(bt,s1,s2,length) printf(已恢复二叉树.n); break;case 5:printf(此函数

31、在删左二叉结点和删右二叉结点里实现.n); break;case 6:if(Empty_Bitree(bt)printf(二叉树为空.n); else printf(二叉树不为空.n); break;case 7:if(node=Root_Bitree(bt) printf(根结点的数据为:%cn,node-data); else printf(根结点为空.n); break;case 8:printf(请输入要查找的二叉树的数据:); scanf(%c,&ch); if(node=Search_Bitree(bt,ch) printf(该结点在:%x,%cn,node,node-data);

32、 else printf(无该二叉树!n); break;case 9:printf(请输入要插入的数据:); scanf(%c,&ch); getchar(); printf(请输入要插入的位置的数据:); scanf(%c,&ch2); getchar(); if(node=Search_Bitree(bt,ch2) if(InsertL_Bitree(node,ch)printf(插入成功.n);else; else printf(插入位置出错.n); break;case 10:printf(请输入要插入的数据:); scanf(%c,&ch);getchar(); printf(请输

33、入要插入的位置的数据:); scanf(%c,&ch2);getchar(); if(node=Search_Bitree(bt,ch2)if(InsertR_Bitree(node,ch)printf(插入成功.n);else; else printf(插入位置出错.n); break;case 11:printf(请输入要删除的位置的数据:); scanf(%c,&ch2); if(node=Search_Bitree(bt,ch2)if(DeleteL_Bitree(node)printf(删除成功.n);else; else printf(插入位置出错.n); break;case 12:printf(请输入要删除的位置的数据:); scanf(%c,&ch2); if(node=Search_Bitree(bt,ch2)if(DeleteR_Bitree(node)printf(删除成功.n);else; else printf(插入位置出错.n)