二叉树的基本操作(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;i
lson=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;i
lson=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(out
data); 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:螺旋矩阵(C语言)
下一篇:动态规划---求最长公共子序列和最长公共子串(C语言)

发表评论

最新留言

不错!
[***.144.177.141]2024年03月04日 01时14分43秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

node与mysql开源_node与mysql的相互使用————node+mysql 2019-04-21
python合并列表重新排序_python – 将两个已排序的列表合并为一个更大的排序列表... 2019-04-21
vbs用mysql语句查询数据库_vbs脚本实现window环境下的mysql数据库的备份及删除早期备份... 2019-04-21
mysql连接nginx_nginx四层负载均衡连接mysql 2019-04-21
mysql截取栏目字符_substring从指定字符串开始截取(图) 2019-04-21
python 函数参数前面两个星号_Python中参数前面一个星号两个星号(*参数,**参数)起什么作用呢?... 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
java 自助更改密码 api_搭建ldap自助修改密码系统--Self Service Password 2019-04-21
php继承exten,stylus中文文档 » 继承(@extend) » 张鑫旭-鑫空间-鑫生活 2019-04-21