C语言实现二叉树的基本操作---创建、遍历、求深度、求叶子结点 - 推酷
C语言实现二叉树的基本操作---创建、遍历、求深度、求叶子结点
typedef int ElemT
//数据类型
typedef int
//返回值类型
//定义二叉树结构
typedef struct BiTNode{
struct BiTNode *lChild, *rC //左右子树域
}BiTNode, *BiT
//先序创建二叉树
Status CreateBiTree(BiTree *T)
scanf("%d", &ch);
temp = getchar();
if (-1 == ch)
*T = NULL;
*T = (BiTree)malloc(sizeof(BiTNode));
if (!(*T))
(*T)->data =
printf("输入%d的左子节点：", ch);
CreateBiTree(&(*T)->lChild);
printf("输入%d的右子节点：", ch);
CreateBiTree(&(*T)->rChlid);
//先序遍历二叉树
void TraverseBiTree(BiTree T)
if (NULL == T)
printf("%d ", T->data);
TraverseBiTree(T->lChild);
TraverseBiTree(T->rChlid);
//中序遍历二叉树
void InOrderBiTree(BiTree T)
if (NULL == T)
InOrderBiTree(T->lChild);
printf("%d ", T->data);
InOrderBiTree(T->rChlid);
//后序遍历二叉树
void PostOrderBiTree(BiTree T)
if (NULL == T)
PostOrderBiTree(T->lChild);
PostOrderBiTree(T->rChlid);
printf("%d ", T->data);
//二叉树的深度
int TreeDeep(BiTree T)
int deep = 0;
int leftdeep = TreeDeep(T->lChild);
int rightdeep = TreeDeep(T->rChlid);
deep = leftdeep>=rightdeep?leftdeep+1:rightdeep+1;
//求二叉树叶子结点个数
int Leafcount(BiTree T,int &num)
if(T->lChild ==NULL &&T->rChlid==NULL)
Leafcount(T->lChild,num);
Leafcount(T->rChlid,num);
int main(void)
BiTree *p = (BiTree*)malloc(sizeof(BiTree));
int deepth,num=0 ;
printf("请输入第一个结点的值,-1表示没有叶结点:\n");
CreateBiTree(&T);
printf("先序遍历二叉树:\n");
TraverseBiTree(T);
printf("\n");
printf("中序遍历二叉树:\n");
InOrderBiTree(T);
printf("\n");
printf("后序遍历二叉树:\n");
PostOrderBiTree(T);
printf("\n");
deepth=TreeDeep(T);
printf("树的深度为:%d",deepth);
printf("\n");
Leafcount(T,num);
printf("树的叶子结点个数为:%d",num);
printf("\n");
已发表评论数()
已收藏到推刊！
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
排版有问题
没有分页内容
视频无法显示
图片无法显示共有 19863 人关注过本帖
标题：[原创][开源]二叉树基本操作的程序实现.
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9796
专家分：208
结帖率：66.67%
&&问题点数：0&&回复次数：46&&&
[原创][开源]二叉树基本操作的程序实现.
//Bintree.h#include&stdio.h&#include&malloc.h&typedef struct Binnode{//二叉树结点结构体
struct Binnode *
struct Binnode *
};typedef Binnode *B
typedef struct stack{ //二叉树结点栈
Bintree data[100];
int flag[100];
typedef struct queue{ //二叉树结点队列
Bintree data[30];
/*******************************************//*
按照前序遍历建立二叉树
*//*******************************************/
void Creat_Bintree(Bintree *root){
if((ch=getchar())==' ')
*root=NULL;
*root=(Binnode*)malloc(sizeof(Binnode));
(*root)-&data=
Creat_Bintree(&(*root)-&lchild);
Creat_Bintree(&(*root)-&rchild);
/*******************************************//*
按照前序递归遍历二叉树
*//*******************************************/
void Preorder1(Bintree t){
if(t!=NULL)
printf("%c",t-&data);
Preorder1(t-&lchild);
Preorder1(t-&rchild);
/*******************************************//*
按照中序递归遍历二叉树
*//*******************************************/
void Inorder1(Bintree t){
if(t!=NULL)
Inorder1(t-&lchild);
printf("%c",t-&data);
Inorder1(t-&rchild);
/*******************************************//*
按照后序递归遍历二叉树
*//*******************************************/
void Posorder1(Bintree t){
if(t!=NULL)
Posorder1(t-&lchild);
Posorder1(t-&rchild);
printf("%c",t-&data);
}}/*******************************************//*
按照前序非递归遍历二叉树
*//*******************************************/
void Preorder2(Bintree t){
Bintree pre=t;
printf("输出前序遍历序列:");
while(pre||s.top&0)
printf("%c",pre-&data);
s.data[s.top++]=
pre=s.data[--s.top]-&
printf("\n\n");}
/*******************************************//*
按照中序非递归遍历二叉树
*//*******************************************/
void Inorder2(Bintree t){
Bintree pre=t;
printf("输出中序遍历序列:");
while(pre||s.top&0)
s.data[s.top++]=
pre=s.data[--s.top];
printf("%c",pre-&data);
printf("\n\n");}
/*******************************************//*
按照后序非递归遍历二叉树
*//*******************************************/
void Posorder2(Bintree t){
printf("输出后序遍历序列:");
while(t!=NULL||s.top!=-1)
s.flag[s.top]=0;
s.data[s.top]=t;
while(s.top&=0&&s.flag[s.top]==1)
t=s.data[s.top];
printf("%c",t-&data);
if(s.top&=0)
t=s.data[s.top];
s.flag[s.top]=1;
printf("\n\n");}
/*******************************************//*
按照层次遍历二叉树
*//*******************************************/void Levelorder(Bintree t){
q.data[0]=t;
q.front=0;q.rear=1;
printf("层次遍历二叉树结果:");
while(q.front&q.rear)
if(q.data[q.front])
printf("%c",q.data[q.front]-&data);
q.data[q.rear++]=q.data[q.front]-&
q.data[q.rear++]=q.data[q.front]-&
q.front++;
q.front++;
printf("\n\n");}
搜索更多相关主题的帖子:
&&&&&&&&&&
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9796
专家分：208
#include"Bintree.h"/*******************************************//*
递归法将二叉树的左右子树互换
*//*******************************************/void Exchange1(Bintree t){
Exchange1(t-&lchild);
Exchange1(t-&rchild);
t-&lchild=t-&
t-&rchild=
}}/*******************************************//*
非递归法将二叉树的左右子树互换
*//*******************************************/void Exchange2(Bintree t){
while(t||s.top)
s.data[s.top++]=t;
t-&lchild=t-&
t-&rchild=
t=s.data[--s.top]-&
}}int main(){
Creat_Bintree(&t);
Exchange2(t);
Inorder2(t);
return 0;}
倚天照海花无数，流水高山心自知。
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9796
专家分：208
#include"Bintree.h"/*******************************************//*
递归法求叶子结点个数
*//*******************************************/int Leaves_Num1(Bintree t){
if(t-&lchild==NULL&&t-&rchild==NULL)
return Leaves_Num1(t-&lchild)+Leaves_Num1(t-&rchild);
return 0;}
/*******************************************//*
非递归法求叶子结点个数
*//*******************************************/int Leaves_Num2(Bintree t){
int count=0;
while(t||s.top&0)
s.data[s.top++]=t;
if(t-&lchild==NULL&&t-&rchild==NULL)
t=s.data[--s.top]-&
int main(){
int count=0;
Creat_Bintree(&t);
count=Leaves_Num2(t);
printf("该二叉树的叶子结点数为:%d\n",count);
return 0;}
倚天照海花无数，流水高山心自知。
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9796
专家分：208
#include"Bintree.h"
/**********************************************//*
求一棵树的高度
*//**********************************************/
int Depth(Bintree t){
if( NULL == t )
return 0 ;
lh = Depth( t-&lchild ) ;
rh = Depth( t-&rchild ) ;
return ( lh & rh ? lh : rh ) + 1 ;
int main(){
Creat_Bintree( &t ) ;
printf( "树的高度是%d\n" , Depth( t ) ) ;
return 0 ;}
倚天照海花无数，流水高山心自知。
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9796
专家分：208
#include"Bintree.h"/*******************************************************//*
已知一课棵二叉树的中序和后序，建立这棵树
*//*******************************************************/
void In_Pos_order(Bintree *t,char *s,char *r){
char La[30],Lb[30],Ra[30],Rb[30];
int i,len,length=strlen(r);
if(length&0&&r[length-1]!='\0')
*t=(Binnode *)malloc(sizeof(Binnode));
(*t)-&data=r[length-1];
for(i=0;s[i]!=r[length-1];i++)
Ra[i]=s[i];
La[i]=r[i];
Ra[len]='\0'; //左中
La[len]='\0'; //左后
for(i=len+1;i&strlen(s);i++)
Rb[i-len-1]=s[i];
Rb[i-len-1]='\0';
for(i=i&strlen(r)-1;i++)
Lb[i-len]=r[i];
Lb[i-len]='\0';
In_Pos_order(&(*t)-&lchild,Ra,La);
In_Pos_order(&(*t)-&rchild,Rb,Lb);
int main(){
char in[30]="ABCEFGHD",pos[30]="ABFHGEDC";//测试数据
printf("输入中序遍历序列:");
scanf("%s",in);
printf("输入后序遍历序列:");
scanf("%s",in);
In_Pos_order(&t,in,pos);
Preorder2(t);}
倚天照海花无数，流水高山心自知。
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9796
专家分：208
#include"Bintree.h"/*******************************************************//*
判断两棵是否等价
*//*******************************************************/
int Is_equal( Bintree t1 , Bintree t2 ){
if(NULL == t1 && NULL == t2)
if(NULL !=t1 &&NULL != t2 )
if(t1-&data == t2-&data)
if(Is_equal(t1-&lchild,t2-&lchild))
t=Is_equal(t1-&rchild,t2-&rchild);
}}int main(){
Bintree t1,t2;
Creat_Bintree(&t1);
getchar();
Creat_Bintree(&t2);
if(Is_equal(t1,t2))
printf( "Yes!\n") ;
printf( "No!\n" ) ;
return 0 ;}
倚天照海花无数，流水高山心自知。
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9796
专家分：208
#include"Bintree.h"/****************************************************//*
查找某个信息是否在这棵树中
*//****************************************************/
Bintree locale_x(Bintree t,char x){
if(t==NULL) return NULL;
if( t -& data == x )
p = locale_x(t-&lchild,x);
return locale_x(t-&rchild,x);
int main(){
Bintree root,p;
Creat_Bintree(&root);
getchar();
printf("输入要查找的值:");
scanf("%c",&ch);
p=locale_x(root,ch);
if(p)printf( "YES!\n" ) ;
else printf( "NO!\n" ) ;
return 0;}
倚天照海花无数，流水高山心自知。
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9796
专家分：208
#include"Bintree.h"
/****************************************************//*
树的结点个数
*//****************************************************/int
num_of_node(Bintree t){
if(t==NULL)return 0 ;
else return num_of_node(t-&lchild)+num_of_node(t-&rchild)+1;}
int main(){
Bintree root,p;
Creat_Bintree(&root);
printf("%d\n",num_of_node(root));
return 0;}
倚天照海花无数，流水高山心自知。
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9796
专家分：208
#include"Bintree.h"
/*******************************************************//*
已知一课棵二叉树的中序和前序序列，建立这棵树
*//*******************************************************/
void Pre_In_order(Bintree *t,char *s,char *r){
char La[30],Lb[30],Ra[30],Rb[30];
if(s[0]!='\0')
*t=(Binnode *)malloc(sizeof(Binnode));
(*t)-&data=s[0];
for(i=0;r[i]!=s[0];i++)
Ra[i]=r[i];
Ra[len]='\0'; //左中
for(i=0;i&i++)
La[i]=s[i+1];
La[len]='\0'; //左前
for(i=len+1;i&strlen(r);i++)
Rb[i-len-1]=r[i];
Rb[i-len-1]='\0';
for(i=len+1;i&strlen(s);i++)
Lb[i-len-1]=s[i];
Lb[i-len-1]='\0';
Pre_In_order(&(*t)-&lchild,La,Ra);
Pre_In_order(&(*t)-&rchild,Lb,Rb);
int main(){
char pre[30]="ABCDEF",in[30]="CBAEDF";//测试数据
printf("输入前序遍历序列:");
scanf("%s",pre);
printf("输入中序遍历序列:");
scanf("%s",in);
Pre_In_order(&t,pre,in);
Posorder1(t);}
倚天照海花无数，流水高山心自知。
来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9796
专家分：208
#include&stdio.h&#include&malloc.h&typedef struct node{
struct node *lchild,*rchild,*
typedef hufnode */****************************************************//*
*//****************************************************/linkhuf Creat_Node(int n) //创建一单链表{
linkhuf head,pre,p;
head=NULL;
while(n--)
scanf("%d",&x);
p=(linkhuf)malloc(sizeof(hufnode));
p-&data=x;
p-&lchild=NULL;
p-&rchild=NULL;
if(NULL==head)
p-&next=pre-&
pre-&next=p;
}}linkhuf insert(linkhuf root , linkhuf s)//将结点S插入到有序Huffman root中。{
linkhuf p1,p2;
if(NULL == root ) root=s;
while(p2&&p2-&data&s-&data)
s-&next=p2;
if(NULL==p1)
p1-&next=s;
void Preorder1(linkhuf t){
if(t!=NULL)
printf("%-6d",t-&data);
Preorder1(t-&lchild);
Preorder1(t-&rchild);
}}void creathuffman(linkhuf *root)//构造Huffman树。{
linkhuf s, rl,
while(*root && (*root)-&next)
rr=(*root)-&
*root=rr-&
s=(linkhuf)malloc(sizeof(hufnode));
s-&next=NULL;
s-&data=rl-&data+rr-&
s-&lchild=
s-&rchild=
rl-&next=rr-&next=NULL;
*root=insert(*root,s);
int main(){
scanf("%d",&n);
root=Creat_Node(n);
creathuffman(&root);
Preorder1(root);
printf("\n");
return 0;}
倚天照海花无数，流水高山心自知。
版权所有，并保留所有权利。
Powered by , Processed in 0.027939 second(s), 8 queries.
Copyright&, BCCN.NET, All Rights Reserved二叉树的基本操作完整版_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
二叉树的基本操作完整版
上传于||暂无简介
阅读已结束，如果下载本文需要使用
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩7页未读，继续阅读
你可能喜欢