二叉树的基本操作(C语言)
发布日期:2021-11-15 21:44:10
浏览次数:1
分类:技术文章
本文共 2482 字,大约阅读时间需要 8 分钟。
前提:
#include#include typedef struct node{ char data; struct node *lson; struct node *rson;}NODE;
一、建造二叉树
1、已知二叉树的一个按先序遍历输入的字符序列,如abc,de,g,f, (其中,表示空结点)。
int i; //在main函数中i要置零char a[100];NODE *creat(){ NODE *t; if(a[i]==',') { i++; return NULL; } t=(NODE *)malloc(sizeof(NODE)); t->data=a[i]; i++; t->lson=creat(); t->rson=creat(); return t;}
2、已知二叉树的先序遍历序列和中序遍历序列
NODE *creat(char s1[],char s2[],int len){ int i; NODE *t; if(len<=0) { return NULL; } t=(NODE *)malloc(sizeof(NODE)); t->data=s1[0]; for(i=0;ilson=creat(s1+1,s2,i); t->rson=creat(s1+i+1,s2+1+i,len-1-i); return t;}
3、已知一棵二叉树的中序遍历和后序遍历
NODE *creat(char s1[],char s2[],int len){ NODE *t; int i; if(len<=0) { return NULL; } t=(NODE *)malloc(sizeof(NODE)); t->data=s2[len-1]; for(i=0;ilson=creat(s1,s2,i); t->rson=creat(s1+i+1,s2+i,len-i-1); return t;}
二、遍历二叉树
1、前序遍历
void xian(NODE *t){ if(t) { printf("%c",t->data); xian(t->lson); xian(t->rson); }}
2、中序遍历
void mid(NODE *t){ if(t) { mid(t->lson); printf("%c",t->data); mid(t->rson); }}
3、后序遍历
void hou(NODE *t){ if(t) { hou(t->lson); hou(t->rson); printf("%c",t->data); }}
4、层序遍历
void show(struct node *t){ //队列思想;out相当于队列的头,in相当于队列的尾后面那一个; struct node *temp[55];//定义了55个结构体指针;用来指结点; temp[0]=t; int in=1,out=0;//因为一开始temp队列中只有一个t;所以in=1 out=0; while(outdata); temp[in++]=temp[out]->lson; //把要输出的那个结点的左右儿子放进队列; temp[in++]=temp[out]->rson; } out++;//既然temp【out】已经输出了,让out++来删除输出的结点; }}
三、求叶子数
int yezi(NODE *t){ int k; if(t==NULL) { return 0; } else if(t->lson==NULL&&t->rson==NULL) { return 1; } else { k=yezi(t->lson)+yezi(t->rson); return k; }}
int count=0;void yezi(NODE *t){ if(t) { if(t->lson==NULL&&t->rson==NULL) { count++; } yezi(t->lson); yezi(t->rson); }}
四、求深度
int deep(NODE *t){ int d=0; if(t) { d=max(deep(t->lson)+1,deep(t->rson)+1); } return d;}
int deep(NODE *t){ if(t==NULL) return 0; else { int l=deep(t->lson)+1; int r=deep(t->rson)+1; int d=l>r?l:r; return d; } }
转载地址:https://blog.csdn.net/qq_43419016/article/details/89341966 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年03月04日 01时14分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
node与mysql开源_node与mysql的相互使用————node+mysql
2019-04-21
mysql连接nginx_nginx四层负载均衡连接mysql
2019-04-21
mysql截取栏目字符_substring从指定字符串开始截取(图)
2019-04-21
python类属性初始化_Python类定义、属性、初始化和析构
2019-04-21
mysql构建url给scrapy_Python Scrapy从mysq填充起始url
2019-04-21
owdcloud mysql_MySQL在Ubuntu远程配置
2019-04-21
python基础装饰器_Python基础 装饰器及练习
2019-04-21
python导出csv不带引号的句子_不带双引号写入CSV文件
2019-04-21
python爬虫代码模板_Python:学习Python爬虫的第一天
2019-04-21
springboot获取原生js请求_springboot跳转原生html
2019-04-21
java buffer nio_Java NIO之Buffer(缓冲区)入门
2019-04-21
android java加密_android 和java平台通用的AES加密解密
2019-04-21
java导出类_java导出excel工具类
2019-04-21
java学习手册下载_Java学习手册
2019-04-21
axios delete有请求体吗_关于axios请求——delete方法
2019-04-21