关于二叉树的一些操作(C源码)VIP免费

下载本文档

阅读 112
下载 8
格式 doc
大小 110 KB
约6页
2024-10-21 发布于山西
收藏
评论
点赞(0)
海报
举报

1/6页

2/6页

3/6页

在线预览已结束，请下载后查看完整版，加入VIP享文档下载特权

文本预览下载提示常见问题

/*调试环境VS2008、VC++6.0*//*关于二叉树的一些操作，包括二叉树的建立，输出，遍历*//*判断是否为完全二叉树，求二叉树的层数，求叶子结点数*/#include#include#include#defineMAX(x,y)(x)>(y)?(x):(y)typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreateBiTree(BiTreeT){//按先序次序输入二叉树中结点的值(int类型)//构造二叉链表表示的二叉树T，结点值为int型，表示空（子）树intnum;scanf("%d",&num);if(0==num)//空T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));if(!T)exit(0);T->data=num;//生成根结点printf("请输入结点%d的左子结点:",T->data);T->lchild=CreateBiTree(T->lchild);//构造左子树printf("请输入结点%d的右子结点:",T->data);T->rchild=CreateBiTree(T->rchild);//构造右子树}returnT;}voidPrintBiTree(BiTreeT){//先序遍历输出二叉树，其中NULL表示空结点//输出其嵌套括号表示格，即形如A(T1,T2)，其中A为根结点，T1，T2分别为A的左子树和右子树if(T!=NULL){printf("%d",T->data);//若结点非空，输出结点的值if(T->lchild!=NULL||T->rchild!=NULL){printf("(");PrintBiTree(T->lchild);//判断左子树，非空则输出根结点的值printf(",");if(T->rchild!=NULL)PrintBiTree(T->rchild);//判断右子树，非空则输出根结点的值elseprintf("NULL");printf(")");}}elseprintf("NULL");}intFullBiTree(BiTreeT){//判断二叉树是否为完全二叉树，完全二叉树需满足两个条件//一是某结点缺失左或右孩子，则其后续结点均无孩子结点//二是某结点无左孩子，则一定无右孩子//需按层次遍历二叉树，故设一队列，用queue表示该队列//用bj表示是否所以结点均有左孩子和右孩子，若是bj=1,否则bj=0BiTreequeue[50],p;intfirst=0,rear=0,cm=1,bj=1;if(T!=NULL){queue[++rear]=T;//根结点入队while(first!=rear){p=queue[++first];//p按入队先后顺序依次指向队列中的结点if(p->lchild==NULL){bj=0;//p的左孩子为空，bj=0if(p->rchild!=NULL){//p的左孩子为空，右孩子却不为空，不可能是完全二叉树了`cm=0;break;}}else{cm=bj;if(!cm)break;queue[++rear]=p->lchild;//p的左孩子不为空，入队if(p->rchild==NULL)//p的左孩子非空，右孩子空，则其左孩子必须无后续结点bj=0;//否则不可能为完全二叉树elsequeue[++rear]=p->rchild;//p的右孩子非空，入队}}returncm;}return1;}voidpreorder(BiTreeT){//先序遍历二叉树并输出if(T!=NULL){printf("%d",T->data);preorder(T->lchild);preorder(T->rchild);}}voidinorder(BiTreeT){//中序遍历二叉树并输出if(T!=NULL){preorder(T->lchild);printf("%d",T->data);preorder(T->rchild);}}voidpostorder(BiTreeT){//后序遍历二叉树并输出if(T!=NULL){preorder(T->lchild);preorder(T->rchild);printf("%d",T->data);}}voidlayorder(BiTreeT){//按层次遍历二叉树，利用队列先进先出性质即可inthead=0,tail=0;BiTreequeue[50],p;p=T;if(p!=NULL)queue[tail++]=p;while(head!=tail){if(p->lchild!=NULL)queue[tail++]=p->lchild;if(p->rchild!=NULL)queue[tail++]=p->rchild;printf("%d",p->data);p=queue[++head];}}intleaf_num(BiTreeT){//计算叶子结点数，并输出叶子结点//f(T)=0,如果T=NULL//f(T)=1,如果T->lchild=T->rchild=NULL//f(T)=f(T->lchild)+f(T->rchild),其他情况intnum1,num2;if(T==NULL)return0;elseif(T->lchild==NULL&&T->rchild==NULL){printf("结点%d",T->data);return1;}else{num1=leaf_num(T->lchild);num2=leaf_num(T->rchild);return(num1+num2);}}intlayer_num(BiTreeT){//f(T)=0,如果T=NULL//f(T)=1,如果T->lchild=T->rchild=NULL//f(T)=max{f(T->lchild)+1,f(T->rchild)+1},其他情况intnum1,num2;if(T==NULL)return0;elseif(T->lchild==NULL&&T->rchild==NULL)return1;else{num1=layer_num(T->lchild)+1;num2=layer_num(T->rchild)+1;returnMAX(num1,num2);}}intmain(void){intk;BiTreeT=NULL;printf("\n建立二叉树\n请输入树的根结点：");T=CreateBiTree(T);printf("\n输出二叉树：\n");PrintBiTree(T);if(FullBiTree(T))printf("\n\n这是一棵完全二叉树");elseprintf("\n\n这不是一棵完全二叉树");printf("\n\n先序遍历二叉树：");preorder(T);printf("\n\n中序遍历二叉树：");inorder(T);printf("\n\n后序遍历二叉树：");postorder(T);printf("\n\n按层次遍历二叉树：");layorder(T);printf("\n\n二叉树的叶子结点为：");k=leaf_num(T);printf("，共%d个",k);printf("\n\n二叉树的层数为：%d层\n\n",layer_num(T));return0;}以图1所示的二叉树为例，程序的运行结果如图2、图3所示图1图2图3

1、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
3、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。

碎片内容

关于二叉树的一些操作(C源码)

/*调试环境VS2008、VC++6

0*//*关于二叉树的一些操作，包括二叉树的建立，输出，遍历*//*判断是否为完全二叉树，求二叉树的层数，求叶子结点数*/#include#include#include#defineMAX(x,y)(x)>(y)

(x):(y)typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreateBiTree(BiTreeT){//按先序次序输入二叉树中结点的值(int类型)//构造二叉链表表示的二叉树T，结点值为int型，表示空（子）树intnum;scanf("%d",&num);if(0==num)//空T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));if(

T)exit(0);T->data=num;//生成根结点printf("请输入结点%d的左子结点:",T->data);T->lchild=CreateBiTree(T->lchild);//构造左子树printf("请输入结点%d的右子结点:",T->data);T->rchild=CreateBiTree(T->rchild);//构造右子树}returnT;}voidPrintBiTree(BiTreeT){//先序遍历输出二叉树，其中NULL表示空结点//输出其嵌套括号表示格，即形如A(T1,T2)，其中A为根结点，T1，T2分别为A的左子树和右子树if(T

=NULL){printf("%d",T->data);//若结点非空，输出结点的值if(T->lchild

=NULL||T->rchild

=NULL){printf("(");PrintBiTree(T->lchild);//判断左子树，非空则输出根结点的值

您可能关注的文档

文章天下 + 关注: 实名认证
内容提供者

各种文档应有尽有

收藏店铺进入空间

关于二叉树的一些操作(C源码)VIP免费

关于二叉树的一些操作(C源码)

您可能关注的文档

相关文档

热门下载

相关标签