二叉树基本函数

一.二叉树基本函数1.宏定义：#includestdio.h#includestdlib.h#includestring.h#definedatatypebtchar#defineMAXNODE1024#defineBOTTOMNODE1024#defineFULLNODE10242.结构体：typedefstructbitnode{datatypebtdata;structbitnode*lchild,*rchild;}Bitnode,*Bitree;3.基本函数：BitreeInitiate_Bitree()/*初始化二叉树函数1.先决条件:无2.函数作用:初始化一棵空的带头结点的二叉树,返回头结点的地址*/{Bitnode*bt;bt=(Bitnode*)malloc(sizeof(Bitnode));bt-lchild=NULL;bt-rchild=NULL;returnbt;}Bitnode*Create_Bitree(datatypebtx,Bitnode*lbt,Bitnode*rbt)/*建立二叉树函数1.先决条件:无2.函数作用:生成一棵以x为根结点数据域信息,以lbt,rbt为左右子树的二叉树,返回新二叉树的地址*/{Bitreep;p=(Bitnode*)malloc(sizeof(Bitnode));p-data=x;p-lchild=lbt;p-rchild=rbt;returnp;}voidPrecreate_Bitree(Bitree*T)/*先序构建二叉树函数1.先决条件:T是子树根结点的地址2.函数作用:以先序遍历序列构造二叉树链表存储的二叉树T*/{charch;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);}}voidPreinorder_Bitree(Bitree*t,charpreod[],inti,intj,charinod[],intk,inth)/*先中序恢复树函数1.先决条件:t是子树根结点的地址2.函数作用:preod[i..j]为先序子序列,inod[k..h]为中子序序列,根据先序序列和中序序列恢复二叉树t*/{intm;*t=(Bitnode*)malloc(sizeof(Bitnode));(*t)-data=preod[i];m=k;while(inod[m]!=preod[i])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)-rchild=NULL;elsePreinorder_Bitree(&(*t)-rchild,preod,i+m-k+1,j,inod,m+1,h);}intRecovery_Bitree(Bitreebt,charpreod[],charinod[],intn)/*先中序恢复树函数1.先决条件:初始化二叉树,bt为头结点,拥有Preinorder_Bitree()函数2.函数作用:根据先序和中序序列恢复二叉树bt,成功返回1*/{if(n=0)bt-lchild=NULL;elsePreinorder_Bitree(&bt-lchild,preod,0,n-1,inod,0,n-1);return1;}voidPostfree_Bitree(Bitreep)/*后序释放函数1.先决条件:p为子树根结点的地址2.函数作用:释放子树p的全部空间*/{if(p==NULL)return;Postfree_Bitree(p-lchild);Postfree_Bitree(p-rchild);free(p);}intEmpty_Bitree(Bitreebt)/*判空函数1.先决条件:初始化二叉树,bt为头结点2.函数作用:若二叉树bt为空,则返回1,否则返回0*/{if(bt-lchild==NULL)return1;elsereturn0;}Bitnode*Root_Bitree(Bitreebt)/*求根函数1.先决条件:初始化二叉树,bt为头结点2.函数作用:求二叉树bt的根结点,返回根结点的地址,若bt为空二叉树,则函数返回NULL*/{returnbt-lchild;}Bitnode*Search_Bitree(Bitreebt,datatypebtx)/*查找函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:在二叉树bt中查找值为x的数据元素,成功返回其地址,找不到返回NULL*/{Bitreep=NULL;if(bt){if(bt-data==x)returnbt;if(bt-lchild)p=Search_Bitree(bt-lchild,x);if(p)returnp;if(bt-rchild)p=Search_Bitree(bt-rchild,x);if(p)returnp;}returnNULL;}intInsertL_Bitree(Bitnode*parent,datatypebtx)/*左插入函数1.先决条件:无2.函数作用:在二叉树中的parent所指结点和其左子树之间插入数据元素为x的结点,成功返回1*/{Bitnode*p;if(parent==NULL){printf(插入出错.\n);/*此句可以根据情况删除*/return0;}p=(Bitnode*)malloc(sizeof(Bitnode));p-data=x;p-lchild=NULL;p-rchild=NULL;if(parent-lchild==NULL)parent-lchild=p;else{p-lchild=parent-lchild;parent-lchild=p;}return1;}intInsertR_Bitree(Bitnode*parent,datatypebtx)/*右插入函数1.先决条件:无2.函数作用:在二叉树中的parent所指结点和其右子树之间插入数据元素为x的结点,成功返回1*/{Bitnode*p;if(parent==NULL){printf(插入出错.\n);/*此句可以根据情况删除*/return0;}p=(Bitnode*)malloc(sizeof(Bitnode));p-data=x;p-lchild=NULL;p-rchild=NULL;if(parent-rchild==NULL)parent-rchild=p;else{p-rchild=parent-rchild;parent-rchild=p;}return1;}intDeleteL_Bitree(Bitnode*parent)/*左删除函数1.先决条件:parent为子树的根结点,拥有Postfree_Bitree()函数2.函数作用:在二叉树中删除parent的左子树,成功返回1*/{Bitnode*p;if(parent==NULL||parent-lchild==NULL){printf(删除出错.\n);/*此句可以根据情况删除*/returnNULL;}p=parent-lchild;parent-lchild=NULL;Postfree_Bitree(p);return1;}intDeleteR_Bitree(Bitnode*parent)/*右删除函数1.先决条件:parent为子树的根结点,拥有Postfree_Bitree()函数2.函数作用:在二叉树中删除parent的右子树,成功返回1*/{Bitnode*p;if(parent==NULL||parent-rchild==NULL){printf(删除出错.\n);/*此句可以根据情况删除*/returnNULL;}p=parent-rchild;parent-rchild=NULL;Postfree_Bitree(p);return1;}Bitnode*Parent_Bitree(Bitreebt,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;returnp;}p=Parent_Bitree(bt-lchild,x);if(p)returnp;p=Parent_Bitree(bt-rchild,x);if(p)returnp;}returnNULL;}voidVisit_Bitree(Bitnode*p)/*访问函数1.先决条件:无2.函数作用:输出一个二叉树结点p的数据*/{if(p)printf(%c,p-data);}intCountleaf_Bitree(Bitreebt)/*统计叶子数函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:统计二叉树bt中叶子结点的个数,返回值为bt的叶子数*/{if(bt==NULL)return0;if(bt-lchild==NULL&&bt-rchild==NULL)return1;returnCountleaf_Bitree(bt-lchild)+Countleaf_Bitree(bt-rchild);}voidPreorder_Bitree(Bitreebt)/*先序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法先序遍历二叉树bt*/{if(bt==NULL)return;Visit_Bitree(bt);Preorder_Bitree(bt-lchild);Preorder_Bitree(bt-rchild);}voidInorder_Bitree(Bitreebt)/*中序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法中序遍历二叉树bt*/{if(bt==NULL)return;Inorder_Bitree(bt-lchild);Visit_Bitree(bt);Inorder_Bitree(bt-rchild);}voidPostorder_Bitree(Bitreebt)/*后序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法后序遍历二叉树bt*/{if(bt==NULL)return;Postorder_Bitree(bt-lchild);Postorder_Bitree(bt-rchild);Visit_Bitree(bt);}intNRPreorder_Bitree(Bitreebt)/*非递归先序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:非递归先序遍历二叉树bt,空树返回0,非空树返回1,栈溢出返回-1*/{Bitnode*p,*s[MAXNODE];/*MAXNODE最少是二叉树的层数h*/inttop=-1;if((p=bt)==NULL){printf(此为空二叉树.\n);/*此句可以根据情况删除*/return0;}while(p!=NULL||top!=-1){while(p!=NULL){Visit_Bitree(p);top++;if(top=MAXNODE){printf(栈溢出.\n);return-1;}s[top]=p;p=p-lchild;}p=s[top];top--;p=p-rchi