《二叉树基本函数》由会员分享，可在线阅读，更多相关《二叉树基本函数（17页珍藏版）》请在金锄头文库上搜索。
1、一一. .二叉树基本函数二叉树基本函数1.宏定义：宏定义：#include #include #include #define datatypebt char #define MAXNODE 1024 #define BOTTOMNODE 1024 #define FULLNODE 10242.结构体：结构体：typedef struct bitnode datatypebt data; struct bitnode *lchild,*rchild; Bitnode,*Bitree;3.基本函数：基本函数：Bitree Initiate_Bitree() /*初始化二叉树函数初始化二叉树函数
2、1.先决条件先决条件:无无 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 为根结点数据域信息为根结
3、点数据域信息,以以 lbt,rbt 为左右子树的二叉树为左右子树的二叉树,返回新二叉树的地址返回新二叉树的地址*/ Bitree p; p=(Bitnode *)malloc(sizeof(Bitnode); p-data=x; p-lchild=lbt; p-rchild=rbt; return p; void Precreate_Bitree(Bitree *T) /*先序构建二叉树函数先序构建二叉树函数 1.先决条件先决条件:T 是子树根结点的地址是子树根结点的地址 2.函数作用函数作用:以先序遍历序列构造以先序遍历序列构造二叉树链表存储的二叉树二叉树链表存储的二叉树 T*/ char
4、ch; scanf(“%c“, if(ch=0) *T=NULL; else (*T)=(Bitnode *)malloc(sizeof(Bitnode); (*T)-data=ch; Precreate_Bitree( Precreate_Bitree( void Preinorder_Bitree(Bitree *t,char preod,int i,int j,char inod,int k,int h) /*先中序恢复树函数先中序恢复树函数 1.先决条件先决条件:t 是子树根结点的地址是子树根结点的地址 2.函数作用函数作用:preodi.j为先序子序列为先序子序列, inodk.h为
5、中子序序列为中子序序列,根据先序序列和中序序列恢复二叉树根据先序序列和中序序列恢复二叉树 t*/ int m; *t=(Bitnode *)malloc(sizeof(Bitnode); (*t)-data=preodi; m=k; while(inodm!=preodi) m+; if(m=k) (*t)-lchild=NULL; else Preinorder_Bitree( if(m=h) (*t)-rchild=NULL; else Preinorder_Bitree( int Recovery_Bitree(Bitree bt,char preod,char inod,int n)
6、/*先中序恢复树函数先中序恢复树函数 1.先决条件先决条件:初始化二叉树初始化二叉树,bt 为头结点为头结点,拥有拥有 Preinorder_Bitree()函数函数 2. 函数作用函数作用:根据先序和中序序列恢复二叉树根据先序和中序序列恢复二叉树 bt,成功返回成功返回 1*/ if(nlchild=NULL; else Preinorder_Bitree( return 1; void Postfree_Bitree(Bitree p) /*后序释放函数后序释放函数 1.先决条件先决条件:p 为子树根结点的地址为子树根结点的地址 2.函数作用函数作用:释放子树释放子树 p 的全部空间的全部
7、空间*/ 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(Bitree bt) /*求根函数求根函数
8、 1.先决条件先决条件:初始化二叉树初始化二叉树,bt 为头结点为头结点 2.函数作用函数作用:求二叉树求二叉树 bt 的根结点的根结点,返回根返回根 结点的地址结点的地址,若若 bt 为空二叉树为空二叉树,则函数返回则函数返回 NULL*/ return bt-lchild; Bitnode *Search_Bitree(Bitree bt,datatypebt x) /*查找函数查找函数 1.先决条件先决条件:初始化二叉树初始化二叉树,bt 是子树根或头结点是子树根或头结点 2.函数作用函数作用:在二叉树在二叉树 bt 中查找中查找 值为值为 x 的数据元素的数据元素,成功返回其地址成功返
9、回其地址,找不到返回找不到返回 NULL*/ Bitree p=NULL; if(bt) if(bt-data=x) return bt; if(bt-lchild) p=Search_Bitree(bt-lchild,x); 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.函数作用函数作用:在二叉树中的在二叉树
10、中的 parent 所指结点和其左子树之间插所指结点和其左子树之间插 入数据元素为入数据元素为 x 的结点的结点,成功返回成功返回 1*/ Bitnode *p; if(parent=NULL) printf(“插入出错.n“);/*此句可以根据情况删除*/ return 0; 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=
11、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=(Bitnode *)malloc(sizeof(Bitnode); p-data=x; p-l
12、child=NULL; p-rchild=NULL; if(parent-rchild=NULL) parent-rchild=p; else p-rchild=parent-rchild; parent-rchild=p; return 1; int DeleteL_Bitree(Bitnode *parent)/*左删除函数左删除函数 1.先决条件先决条件:parent 为子树的根结点为子树的根结点,拥有拥有 Postfree_Bitree()函数函数 2.函数作用函数作用:在在 二叉树中删除二叉树中删除 parent 的左子树的左子树,成功返回成功返回 1*/ Bitnode *p; i
13、f(parent=NULL|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 的右子树的右子树,成功
14、返回成功返回 1*/ Bitnode *p; if(parent=NULL|parent-rchild=NULL) printf(“删除出错.n“);/*此句可以根据情况删除*/ 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 中中
15、 结点结点 x 的双亲结点的双亲结点,若结点若结点 x 是二叉树的根结点或二叉树是二叉树的根结点或二叉树 bt 中无结点中无结点 x,则返回则返回 NULL*/ Bitnode *p=NULL; if(bt) if(bt-lchild=x|bt-rchild=x) p=bt; return p; p=Parent_Bitree(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-lchild=NULL return Countleaf_Bitre
