二叉树的基本操作完整版包二叉树的所有操作凡是你想要的都在里面数据结构版.docx

二叉树的基本操作完整版包二叉树的所有操作凡是你想要的都在里面数据结构版.docx

《二叉树的基本操作完整版包二叉树的所有操作凡是你想要的都在里面数据结构版.docx》由会员分享，可在线阅读，更多相关《二叉树的基本操作完整版包二叉树的所有操作凡是你想要的都在里面数据结构版.docx（35页珍藏版）》请在冰点文库上搜索。

二叉树的基本操作完整版包二叉树的所有操作凡是你想要的都在里面数据结构版

#include"stdio.h"

#include"stdlib.h"

#include"string.h"

#include"math.h"

typedefcharTElemType;//定义结点数据为字符型

typedefintStatus;//定义函数类型为int型

#defineERROR0

#defineOK1

typedefstructBiTNode{//定义结构体

TElemTypedata;//结点数值

structBiTNode*lchild;//左孩子指针

structBiTNode*rchild;//右孩子指针

structBiTNode*next;//下一结点指针

}BiTNode,*BiTree;

StatusNumJudge（charch[20]）{

//限制输入数据必须为大于零的整形

charch1[20];

intnum;

while

（1）{

scanf（"%s",ch）;

num=atoi（ch）;//将字符串转换为整型

itoa（num,ch1,10）;//将整型转换为字符串型

if（strcmp（ch,ch1）==0&&num>0）break;

else{printf（"请输入一个大于零的整数:

"）;}

}

returnnum;

}//NumJudge

StatusInitBiTree（BiTree&T）{

//构造空二叉树T

if（!

（T=（BiTree）malloc（sizeof（BiTNode））））exit（ERROR）;//若申请空间失败则退出

T->next=NULL;

printf（"\n\t空二叉树构建成功!

\n\n"）;

returnOK;

}//InitBiTree

StatusDestroyTree（BiTree&T,BiTreet）{

//销毁二叉树

if（T）{

free（T）;T=NULL;

printf（"\t二叉树销毁成功!

\n"）;

}

if（t）{

DestroyTree（T,t->lchild）;

DestroyTree（T,t->rchild）;

free（t）;

}

returnOK;

}//DestroyTree

StatusClearBiTree（BiTree&T,intsum,int&i）{

//清空二叉树

if（T）{

ClearBiTree（T->lchild,sum,i）;

ClearBiTree（T->rchild,sum,i）;

free（T）;

i++;

}

if（i==sum）{printf（"\t二叉树清空成功!

\n"）;T=NULL;}

returnOK;

}//ClearBiTree

StatusCreateBiTree（BiTree&T,inti,intj,TElemTypech）{

//按先序次序输入二叉树中结点的值（一个字符）,空格字符表示该结点为空

//构造二叉链表示的二叉树T

TElemTypech1;

intk;

charstr[20];

if（i==0）{printf（"\n按先序顺序建立二叉树:

请按提示输入相应的数据（一个字符），若提示结点数值为空，\n请输入空格\n\n"）;

printf（"%5s请输入树根:

",""）;}

if（i!

=0&&i>=j）{printf（"%5s请输入%c的左孩子:

","",ch）;}

if（j!

=0&&j>i）{printf（"%5s请输入%c的右孩子:

","",ch）;}

while

（1）{//限制输入数据必须为字符型,否则重新输入

fflush（stdin）;

for（k=0;k<20;k++）{

str[k]=getchar（）;

if（str[k]=='\n'）break;

}

if（k==0）printf（"%5s请输入一个字符后再按Enter键:

",""）;

if（k==1）break;

if（k>1）printf（"%5s您只能输入一个字符:

",""）;

}

ch1=str[0];//获取输入的准确字符型数据

if（ch1==''）{T=NULL;returnERROR;}//输入空格则为根结点为空

if（ch1!

=''）{

if（!

（T=（BiTree）malloc（sizeof（BiTNode））））exit（ERROR）;

T->data=ch1;//生成根结点

ch=T->data;

i++;

CreateBiTree（T->lchild,i,j,ch）;//构造左子树

j=i;j++;

CreateBiTree（T->rchild,i,j,ch）;//构造右子树

}

i=0;j=0;

returnOK;

}//CreateBitree

StatusTreeDepth（BiTreeT,intl,int&h）{

//若二叉树存在,返回其深度

if（T）{

l=l+1;

if（l>h）h=l;

TreeDepth（T->lchild,l,h）;

TreeDepth（T->rchild,l,h）;

}

returnh;

}//TreeDepth

StatusGetRootElem（BiTreeT）{

//获取根结点值

printf（"该二叉树的根结点值为:

%c\n\n",T->data）;

returnOK;

}//GetRootElem

StatusSaveElem（BiTreeT,BiTree*Q,inti）{

//根据完全二叉树中，若本节点位置序号为i,则其左孩子结点为2i,右孩子为2i+1的方法

//保存二叉树的有效结点至指针数组Q特定的位置

if（T）{

Q[i]=T;

SaveElem（T->lchild,Q,2*i）;

SaveElem（T->rchild,Q,2*i+1）;

}

returnOK;

}//SaveElem

StatusLev_Traverse（BiTreeT,inth）{

//按层次从上到下,每层从左到右的顺序显示树状二叉树

if（T==NULL）{printf（"\n\t\t二叉树目前为空树\n\n"）;returnERROR;}

BiTree*Q;

if（!

（Q=（BiTree*）malloc（int（pow（2,h）+1）*sizeof（BiTNode））））exit（ERROR）;

inti,j,n=1,k=h;

for（i=1;i<=int（pow（2,h）+1）;i++）{

Q[i]=NULL;}

SaveElem（T,Q,n）;//将目前有效结点按照满二叉树的序号存储

printf（"提示:

规定下图中的有效结点的位置序号从1开始按从上到下,从左到右的顺序依次递增\n"）;

for（i=1;i<=（pow（2,h）+1）;i++）{//树形显示二叉树

if（int（pow（2,h））%i==0）{

printf（"\n"）;

printf（"\t\t"）;

for（j=0;j

printf（""）;

}

k--;

}

if（Q[i]）printf（"%c",Q[i]->data）;

if（!

Q[i]）printf（""）;

for（j=0;j

printf（""）;}

}

printf（"\n\n"）;

i=0;j=0;

returnOK;

}//Lev_Traverse

StatusFirstPrint（BiTreeT,inti）{

//按先序次序（递归）访问二叉树

if（i==0）printf（"\n先序（递归）遍历结果如下:

\n"）;

if（T）{

i++;printf（"%-5c",T->data）;//访问T

FirstPrint（T->lchild,i）;//递归遍历左子树

FirstPrint（T->rchild,i）;//递归遍历右子树

}

i=0;

returnOK;

}//FirstPrintBiTree

StatusMiddlePrint（BiTreeT,inti）{

//按中序次序（递归）访问二叉树

if（i==0）printf（"\n中序（递归）遍历结果如下:

\n"）;

if（T）{

i++;

MiddlePrint（T->lchild,i）;//递归遍历左子树

printf（"%-5c",T->data）;//访问T

MiddlePrint（T->rchild,i）;//递归遍历右子树

}

i=0;

returnOK;

}//MiddlePrint

StatusLastPrint（BiTreeT,inti）{

//按后序次序（递归）访问二叉树

if（i==0）printf（"\n后序（递归）遍历结果如下:

\n"）;

if（T）{

i++;

LastPrint（T->lchild,i）;//递归遍历左子树

LastPrint（T->rchild,i）;//递归遍历右子树

printf（"%-5c",T->data）;//访问T

}

i=0;

returnOK;

}//LastPrint

StatusPreOrderTraverse（BiTreeT）{

//按先序（非递归）遍历二叉树T

BiTreep,S,q;

intflag=0;

if（!

（S=（BiTree）malloc（sizeof（BiTNode））））exit（ERROR）;

S->next=NULL;//建立空栈S

p=T;

printf（"\n先序（非递归）遍历结果如下:

\n"）;

while

（1）{

while

（1）{//遍历存储并访问左子树直到根结点左孩子不存在

printf（"%-5c",p->data）;

q=S->next;S->next=p;p->next=q;//当前结点进栈

if（p->lchild）p=p->lchild;

else{break;}

}

while

（1）{//栈顶指针出栈,如果当前栈顶指针的右孩子存在则跳出循环

p=S->next;S->next=p->next;

if（!

S->next&&!

p->rchild）{flag=1;break;}//如果栈空并且当前结点右孩子不存在则遍历结束

if（p->rchild）{p=p->rchild;break;}

}

if（flag==1）break;

}

printf（"\n\n"）;

returnOK;

}//PreOrderTraverse

StatusInOrderTraverse（BiTreeT）{

//中序遍历（非递归）二叉树T

BiTreep,S,q;

if（!

（S=（BiTree）malloc（sizeof（BiTNode））））exit（ERROR）;

S->next=NULL;//建立空栈S

p=T;

printf（"\n中序（非递归）遍历结果如下:

\n"）;

while（p||S->next）{

if（p）{q=S->next;S->next=p;p->next=q;p=p->lchild;}//左孩子进栈

else{

p=S->next;S->next=p->next;

if（p）printf（"%-5c",p->data）;//输出栈中元素

else{returnERROR;}

p=p->rchild;

}

}

printf（"\n\n"）;

returnOK;

}//InOrderTraverse

StatusPostOrderTraverse（BiTreeT）{

//后序遍历（非递归）二叉树T

BiTreep,S,q;

if（!

（S=（BiTree）malloc（sizeof（BiTNode））））exit（ERROR）;

S->next=NULL;//建立空栈S

p=T;

printf（"\n后序（非递归）遍历结果如下:

\n"）;

while

（1）{

while

（1）{//遍历左子树,若当前结点左右孩子都不存在则跳出

q=S->next;S->next=p;p->next=q;//当前结点进栈

if（p->lchild）p=p->lchild;

else{

if（p->rchild）p=p->rchild;

else{break;}

}

}

while（S->next）{

p=S->next;S->next=p->next;//栈顶指针出栈并访问

printf（"%-5c",p->data）;

if（!

S->next）break;//若栈空则跳出

if（p==S->next->rchild）p=S->next;//若当前结点为栈顶指针的右孩子,则继续出栈

else{

if（S->next->rchild）{//栈顶指针右孩存在,指针移至栈顶指针的右孩子后跳出循环

p=S->next->rchild;break;

}

}

}

if（!

S->next）break;//若栈空则跳出循环

}

printf（"\n\n"）;

returnOK;

}//PostOrderTraverse

StatusGetElemSum（BiTreeT）{

//计算二叉树中总结点的个数

BiTreep,*q;

intl=0,h=0;

if（!

（q=（BiTree*）malloc（int（pow（2,TreeDepth（T,l,h））+1）*sizeof（BiTNode））））exit（ERROR）;

inthead=1,tail=2;

q[1]=T;

while（head

p=q[head++];

if（p->lchild）q[tail++]=p->lchild;

if（p->rchild）q[tail++]=p->rchild;

}

returnhead-1;

}//GetElemSum

StatusLevelOrderPrint（BiTreeT）{

//二叉树T存在,层序遍历二叉树

//将二叉树中的结点按从上到下,从左到右的顺序存至指针数组q,然后按次序输出

BiTreep,*q;

if（!

（q=（BiTree*）malloc（GetElemSum（T）*sizeof（BiTNode））））exit（ERROR）;

inthead=1,tail=2;

q[1]=T;

printf（"\n层序（非递归）遍历结果如下:

\n"）;

while（head

p=q[head++];

printf（"%-5c",p->data）;

if（p->lchild）q[tail++]=p->lchild;

if（p->rchild）q[tail++]=p->rchild;

}

printf（"\n\n"）;

returnOK;

}//LevelOrderPrint

StatusGetElemNum（BiTreeT,TElemTypee）{

//查找元素e在二叉树T中的个数及位置

intj,i=0,num=0,*a;

BiTreep,*q;

if（!

（q=（BiTree*）malloc（GetElemSum（T）*sizeof（BiTNode））））exit（ERROR）;

if（!

（a=（int*）malloc（GetElemSum（T）*sizeof（int））））exit（ERROR）;

inthead=1,tail=2;

q[1]=T;

while（head

p=q[head++];

if（p->data==e）{num++;

a[i]=head-1;i++;}

if（p->lchild）q[tail++]=p->lchild;

if（p->rchild）q[tail++]=p->rchild;

}

printf（"\n元素%c在二叉树中的个数为:

%d\n",e,num）;

printf（"元素%c在二叉树中的位置序号为:

",e）;

for（j=0;j

printf（"%-4d",a[j]）;

}

printf（"\n"）;

returnnum;

}//GetElemNum

StatusGetLeafNum（BiTreeT）{

//计算二叉树T中叶子个数

BiTreep,*q;

if（!

（q=（BiTree*）malloc（GetElemSum（T）*sizeof（BiTNode））））exit（ERROR）;

intnum=0,head=1,tail=2;

q[1]=T;

while（head

p=q[head++];

if（!

p->lchild&&!

p->rchild）num++;

if（p->lchild）q[tail++]=p->lchild;

if（p->rchild）q[tail++]=p->rchild;

}

returnnum;

}//GetLeafNum

StatusLBrother（BiTreeT,intsum）{

//求第num个结点的左兄弟

BiTreep,*q;

if（!

（q=（BiTree*）malloc（GetElemSum（T）*sizeof（BiTNode））））exit（ERROR）;

inti,num,head=1,tail=2;

charstr[20];

q[1]=T;

printf（"请输入要查找的位置序号:

"）;

num=NumJudge（str）;

if（num>sum）{printf（"您输入的位置序号大于有效结点个数\n"）;returnERROR;};

while（head

p=q[head++];

if（num==tail-2）break;

if（p->lchild）q[tail++]=p->lchild;

if（p->rchild）q[tail++]=p->rchild;

}

if（num==1）printf（"位置%d的%c没有左兄弟\n",num,q[num]->data）;

else{

for（i=1;i

if（q[i]->lchild==q[num]||q[i]->rchild==q[num]）break;

}

if（q[i]->lchild==q[num]）printf（"位置%d的%c没有左兄弟\n",num,q[num]->data）;

if（q[i]->rchild==q[num]）printf（"位置%d的%c的左兄弟为:

%c\n",num,q[num]->data,q[i]->lchild->data）;

}

returnOK;

}//LBrother

StatusRBrother（BiTreeT,intsum）{

//求第num个结点的右兄弟

BiTreep,*q;

if（!

（q=（BiTree*）malloc（GetElemSum（T）*sizeof（BiTNode））））exit（ERROR）;

inti,num,head=1,tail=2;

charstr[20];

q[1]=T;

printf（"请输入要查找的位置序号:

"）;

num=NumJudge（str）;

if（num>sum）{printf（"您输入的位置序号大于有效结点个数\n"）;returnERROR;};

while（head

p=q[head++];

if（num==tail-2）break;

if（p->lchild）q[tail++]=p->lchild;

if（p->rchild）q[tail++]=p->rchild;

}

if（num==1）printf（"位置%d的%c没有右兄弟\n",num,q[num]->data）;

else{

for（i=1;i

if（q[i]->lchild==q[num]||q[i]->rchild==q[num]）break;

}

if（!

q[i]->rchild||q[i]->rchild==q[num]）printf（"位置%d的%c没有右兄弟\n",num,q[num]->data）;

if（q[i]->rchild&&q[i]->lchild==q[num]）printf（"位置%d的%c的右兄弟为:

%c\n",num,q[num]->data,q[i]->rchild->data）;

}

returnOK;

}//RBrother

StatusLchild（BiTreeT,intsum）{

//求第num个结点的左孩子

BiTreep,*q;

if（!

（q=（BiTree*）malloc（GetElemSum（T）*sizeof（BiTNode））））exit（ERROR）;

intnum,head=1,tail=2;

charstr[20];

q[1]=T;

printf（"请输入要查找的位置序号:

"）;

num=NumJudge（str）;

if（num>sum）{printf（"您输入的位置序号大于有效结点个数\n"）;returnERROR;}

while（head

p=q[head++];

if（num==tail-2）break;

if（p->lchild）q[tail++]=p->lchild;

if（p->rchild）q[tail++]=p->rchild;

}

if（q[num]->lchild）printf（"位置%d的%c的左孩子为:

%c\n",num,q[num]->data,q[num]->lchild->data）;