数据结构——遍历二叉树和线索二叉树,树和森林

news/2024/6/16 2:56:41/文章来源:https://blog.csdn.net/2301_79431343/article/details/136809214

目录

1.遍历的算法实现

1.先序遍历 

代码示例:

 

 2.中序遍历

代码示例:

 3.后序遍历

代码示例:

4.遍历算法的分析 

 

2.遍历二叉树的非递归算法

1.中序遍历非递归算法 

代码示例:

 3.二叉树的层次遍历

代码示例:

 

4.二叉树遍历算法的应用

1.二叉树的建立 

代码示例:

 2.复制二叉树

 代码示例:

3.计算二叉树深度 

代码示例:

 4.计算二叉树结点总数

代码示例:

 

5.计算二叉树叶子结点数 

代码示例:

 5.线索二叉树

1.线索二叉树的结构 

代码示例:

 2.先序线索二叉树

3.中序线索二叉树 

4.后序线索二叉树 

5.练习 

6.树和森林 

1.树的存储结构 

1.双亲表示法 

2.孩子链表 

3.孩子兄弟表示法 

2.树和二叉树的转换 

3.将二叉树转换为树 

7.树和森林的遍历


1.遍历的算法实现

1.先序遍历 

fafc6908807e44518c364a8a19b1f5ba.png

69678e22193e4c1db8a898f8b0a55ebb.png

ebb34f71d35b4728b2997519b25a9971.png

代码示例:

 

int preordertraverse(bitree t)
{if(t == NULL) return 0;else{printf("%d\t",t -> data);preordertraverse(t -> lchild);preordertraverse(t -> rchild);}
}void pre(bitree t)
{if(t != NULL){printf("%d\t",t -> data);pre(t -> lchild);pre(t -> rchild);}
}

 2.中序遍历

93194a14ab1b469d82012b46096a898b.png

fcdb27438bcc4d3682ccbf39badf158b.png

代码示例:

int inordertraverse(bitree t)
{if(t == NULL) return 0;else{inordertraverse(t -> lchild);printf("&d\t",t -> data);inordertraverse(t -> rchild);}
}

 3.后序遍历

497cf6dc808f4b0aa4e83fde78dcd919.png

1791c479cb8b48ffbd5404ef7edb54a8.png

代码示例:

int postordertraverse(bitree t)
{if(t == NULL) return 0;else{postordertraverse(t -> lchild);postordertraverse(t -> rchild);printf("%d\t",t -> data);}
}

4.遍历算法的分析 

 

cd156213da22440f9ad2a14bff4549c9.png

aac0282e8e254113aa0a5b787169c280.png

6719152c9107452f9fad855fd0e01f36.png

2.遍历二叉树的非递归算法

1.中序遍历非递归算法 

f66574e1debc43e095dc658d5e661ccc.png

4d5d51bd77974bbc87c416def237782e.png

925bef5487364737af8fab585029ab30.png

2c51c71272fb487aa2544fc18353d553.png

ce80c4bfd4d74af596dcb972108f85ed.png

eeee6682dc6b493cb3379d1e0963b6df.png

代码示例:

int inordertraverse2(bitree t)
{bitree p,q;initstack(s);p = t;while(p || !stackempty(s)){if(p != NULL){push(s,p);p = p -> lchild;}else{pop(s,q);//使栈顶元素弹出,并且将栈顶元素的地址赋给qprintf("%c",q -> data),p = q -> rchild;}return 1;}
}

 3.二叉树的层次遍历

926c70c3a82c45f287f1aa9bf91bb8b8.png

85c59ea0882e4095b556c703457179fd.png

e1958a411f8847bf878045f5501fb0be.png

903887185d624e42bd25d3395af990d2.png

6b818d3801424dbbb24a3c2229a0e8f7.png

9ddacc42cab64108a29d1860992671cf.png

代码示例:

 

typedef struct{btnode data[100];int front,rear;
}sqqueue;void levelorder(btnode *b)
{btnode *p;sqqueue *qu;initqueue(qu);enqueue(qu,b);while(!queueempty(qu)){dequeue(qu,p);printf("%c",p -> data);if(p -> lchild != NULL) enqueue(qu,p -> lchild);if(p -> rchild != NULL) enqueue(qu,p -> rchild);}
}

4.二叉树遍历算法的应用

1.二叉树的建立 

c016951a15fb4e51af02adb503d08879.png

21c494ccb63f41d7a0e51333d704c617.png

c5bb5ed9b3be498684f50c4f0095b594.png

代码示例:

int createbitree(bitree &t)
{cin >> ch;if(ch == '#') t = NULL;else{t = new bitnode;t -> data = ch;createbitree(t -> lchild);createbitree(t -> rchild);}return 1;
}

 2.复制二叉树

982d6a90b716481db0c78f177ca2f980.png

 代码示例:

int copy(bitree t,bitree &newt)
{if(t == NULL){newt = NULL;return 0;}else{newt = new bitnode;newt -> data = t -> data;copy(t -> lchild,newt -> lchild);copy(t -> rchild,newt -> lchild);}
}

3.计算二叉树深度 

321263016a1b4578b12c027275382418.png

代码示例:

int depth(bitree t)
{if(t == NULL) return 0;else{int m,n;m = depth(t -> lchild);n = depth(t -> rchild);if(m > n) return m + 1;else return n + 1;}
}

 4.计算二叉树结点总数

9fbbb895865c4f479315f90bfa0b84f9.png

代码示例:

 

int nodecount(bitree t)
{if(t == NULL) return 0;else{return nodecount(t -> lchild) + nodecount(t -> rchild) + 1;}
}

5.计算二叉树叶子结点数 

9771b582b89c49a183ad73c4f6b442e1.png

代码示例:

int leafcount(bitree t)
{if(t == NULL) return 0;if(t -> lchild == NULL && t -> rchild == NULL) return 1;else return leafcount(t -> lchild) + leafcount(t -> rchild);
}

 5.线索二叉树

bb0b2824402a4af6a570516840c4fb2b.png

445fa532c4ef4929a2144251db22f348.png

5cc54f1232a342ca8749b2d6d56501ba.png

25cc24506a464950ae2bbec033675087.png

044ca47bb6c2402d9a4df5f5ce260522.png

3808e823b78f4fae9b637683781f25f5.png

1.线索二叉树的结构 

7cba2174004f450880e59f5ff4829843.png

代码示例:

typedef struct bithrnode{int data;int ltag,rtag;struct bithrnode *lchild,*rchild;
}bithrnode,*bithrtree;

 2.先序线索二叉树

81347271a2e94f518bb2d3538c9d2796.png

3.中序线索二叉树 

2f8ca093e9a44be9bf982a81c776a4d7.png

4.后序线索二叉树 

ccbbe06e2ce14b9eb18e87c277628e2a.png

5.练习 

16ee657a95824cfdb6d21249757c1a7b.png

92ea03e792fc45c9b6f78ba28929187d.png

6.树和森林 

6854da0bfc3441ee8753a6609678ecd2.png

1.树的存储结构 

1.双亲表示法 

348e9ac43b844399863533c911d4ebc6.png

b60513672ae84806acf6bde7e1a16747.png

2.孩子链表 

4f17ad62bc94453891760de6c22e19bf.png

81c125f9fb6d4945bde84ba612cbab25.png

a77b1a5fb75440ecb3b3ce3ebdf269c9.png

eafe682694484826bd9777def5b42694.png

3.孩子兄弟表示法 

b71056328b15455bb40f6404f970a329.png

215d350a102346feb4f4835499f050bc.png

2.树和二叉树的转换 

55a4538f587a49a387d730168df7ad2b.png

0811ab99f5274557aed325465c375f5c.png

85b64e3de32f4b35b9475ad125e9e6c0.png

811bb68ea7fc447986031a3083fa4394.png

3.将二叉树转换为树 

e0a63cdf1ae048c3b6bde8311b03940c.png

81d81da1eb72443b8a1f6f6321b49904.png

 

03020388d9f745379af6fea7b934385a.png

1949a8f057b24c4fb4219ceafafce7de.png

b1467793aed44d3abc57dd9bf2362fe8.png

ac746065e9ec47eaa38d0dffb4fd8fe1.png

7.树和森林的遍历

355879a716184f6ab59dc8ec81fa9bfa.png

 4f74efd2dcb94e21927f75a0bd84a6ae.png

81631c5013af4b81a7e8b363e3b8cdea.png

c430052d7aeb480ea06949237a26bddd.png

d0f9049bf17e44ffb80c847d0aee8550.png

8.总的代码

typedef struct binode{int data;struct binode *lchild,*rchild;
}binode,*bitree;int preordertraverse(bitree t)
{if(t == NULL) return 0;else{printf("%d\t",t -> data);preordertraverse(t -> lchild);preordertraverse(t -> rchild);}
}void pre(bitree t)
{if(t != NULL){printf("%d\t",t -> data);pre(t -> lchild);pre(t -> rchild);}
}int inordertraverse(bitree t)
{if(t == NULL) return 0;else{inordertraverse(t -> lchild);printf("&d\t",t -> data);inordertraverse(t -> rchild);}
}int postordertraverse(bitree t)
{if(t == NULL) return 0;else{postordertraverse(t -> lchild);postordertraverse(t -> rchild);printf("%d\t",t -> data);}
}int inordertraverse2(bitree t)
{bitree p,q;initstack(s);p = t;while(p || !stackempty(s)){if(p != NULL){push(s,p);p = p -> lchild;}else{pop(s,q);//使栈顶元素弹出,并且将栈顶元素的地址赋给qprintf("%c",q -> data),p = q -> rchild;}return 1;}
}typedef struct{btnode data[100];int front,rear;
}sqqueue;void levelorder(btnode *b)
{btnode *p;sqqueue *qu;initqueue(qu);enqueue(qu,b);while(!queueempty(qu)){dequeue(qu,p);printf("%c",p -> data);if(p -> lchild != NULL) enqueue(qu,p -> lchild);if(p -> rchild != NULL) enqueue(qu,p -> rchild);}
}int createbitree(bitree &t)
{cin >> ch;if(ch == '#') t = NULL;else{t = new bitnode;t -> data = ch;createbitree(t -> lchild);createbitree(t -> rchild);}return 1;
}int copy(bitree t,bitree &newt)
{if(t == NULL){newt = NULL;return 0;}else{newt = new bitnode;newt -> data = t -> data;copy(t -> lchild,newt -> lchild);copy(t -> rchild,newt -> lchild);}
}int depth(bitree t)
{if(t == NULL) return 0;else{int m,n;m = depth(t -> lchild);n = depth(t -> rchild);if(m > n) return m + 1;else return n + 1;}
}int nodecount(bitree t)
{if(t == NULL) return 0;else{return nodecount(t -> lchild) + nodecount(t -> rchild) + 1;}
}int leafcount(bitree t)
{if(t == NULL) return 0;if(t -> lchild == NULL && t -> rchild == NULL) return 1;else return leafcount(t -> lchild) + leafcount(t -> rchild);
}typedef struct bithrnode{int data;int ltag,rtag;struct bithrnode *lchild,*rchild;
}bithrnode,*bithrtree;

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1034864.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

c#仿ppt案例

画曲线 namespace ppt2024 {public partial class Form1 : Form{public Form1(){InitializeComponent();}//存放所有点的位置信息List<Point> lstPosition new List<Point>();//控制开始画的时机bool isDrawing false;//鼠标点击开始画private void Form1_MouseD…

网络原理 - HTTP / HTTPS(2)——http请求

目录 一、认识 “方法”&#xff08;method&#xff09; 1、GET方法 2、POST方法 &#xff08;1&#xff09;登录 &#xff08;2&#xff09;上传 &#xff08;3&#xff09;GET和POST使用习惯 3、GET方法和POST方法的区别 正确滴 关于一些网上的说法&#xff0c;错误滴…

电商技术揭秘四:电商平台的物流管理系统

文章目录 引言一、物流管理系统的功能与架构1.1 物流管理系统在电商平台中的作用概述保障订单的及时配送优化库存管理控制运营成本提升客户服务水平支持数据驱动的决策应对市场变化 1.2 订单处理功能分析自动化处理流程订单分配与履行错误检测与处理机制实时订单状态更新订单数…

新能源汽车充电桩常见类型及充电桩站场的智能监管方案

随着新能源汽车市场的迅猛发展&#xff0c;充电桩作为支持其运行的基础设施&#xff0c;也呈现出多样化的类型。这些充电桩不仅在外形和功能上存在差异&#xff0c;更在充电速度、充电方式以及使用场景等方面展现出独特的优势。 一、充电桩类型及区别 1、慢充桩&#xff08;交…

5.vector容器的使用

文章目录 vector容器1.构造函数代码工程运行结果 2.赋值代码工程运行结果 3.容量和大小代码工程运行结果 4.插入和删除代码工程运行结果 5.数据存取工程代码运行结果 6.互换容器代码工程运行结果 7.预留空间代码工程运行结果 vector容器 1.构造函数 /*1.默认构造-无参构造*/ …

苹果开发者账号注册后生成开发证书和发布证书的流程解析

转载&#xff1a;注册苹果开发者账号的方法 在2020年以前&#xff0c;注册苹果开发者账号后&#xff0c;就可以生成证书。 但2020年后&#xff0c;因为注册苹果开发者账号需要使用Apple Developer app注册开发者账号&#xff0c;所以需要缴费才能创建ios证书了。 所以新政策出…

Redis的5大常见数据类型的用法

上一篇文章我们讲了Redis的10大应用场景&#xff0c;这一篇文章就针对Redis的常用数据结构进行一个说明&#xff0c;通过示例的形式演示每一种数据结构如何使用。 当涉及Redis的数据操作时&#xff0c;不同数据类型对应的不同数据结构&#xff0c;如下就对5大常用的数据类型进行…

车载电子电器架构 —— 局部网络管理汇总

车载电子电器架构 —— 局部网络管理汇总 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明…

MQ消息队列详解以及MQ重复消费问题

MQ消息队列详解以及MQ重复消费问题 1、解耦2、异步调用3、流量削峰4、MQ重复消费问题&#xff0c;以及怎么解决&#xff1f;4.1、重复消费产生4.2、解决方法&#xff1a; https://blog.csdn.net/qq_44240587/article/details/104630567 核心的就是&#xff1a;解耦、异步、削锋…

【Go】十七、进程、线程、协程

文章目录 1、进程、线程2、协程3、主死从随4、启动多个协程5、使用WaitGroup控制协程退出6、多协程操作同一个数据7、互斥锁8、读写锁9、deferrecover优化多协程 1、进程、线程 进程作为资源分配的单位&#xff0c;在内存中会为每个进程分配不同的内存区域 一个进程下面有多个…

Android 自定义View 测量控件宽高、自定义viewgroup测量

1、View生命周期以及View层级 1.1、View生命周期 View的主要生命周期如下所示&#xff0c; 包括创建、测量&#xff08;onMeasure&#xff09;、布局&#xff08;onLayout&#xff09;、绘制&#xff08;onDraw&#xff09;以及销毁等流程。 自定义View主要涉及到onMeasure、…

Node.js知识点总结:从入门到入土

Node.js知识点总结&#xff1a;从入门到入土 node.js概念说明与相关知识储备了解基本概念&#xff1a;JavaScript基础能力&#xff1a;安装和设置Node.js环境&#xff1a;核心能力模块&#xff1a;重点能力-异步编程&#xff1a;使用npm管理依赖&#xff1a;构建Web应用&#x…

.238.除自身以外数组的乘法

题目描述 解题思路&#xff1a; ————————时间换空间&#xff08;for循环暴力求解&#xff09;———————— 1.两个for循环不断乘积 2.稍作优化——先判断是否有0存在&#xff0c;若是在乘积的余下数组中有0直接判断为0 &#xff08;但是只是最优时间复杂度减少…

EVM Layer2 主流解决方案

深度解析主流 EVM Layer 2 解决方案&#xff1a;zk Rollups 和 Optimistic Rollups 随着以太坊网络的不断演进和 DeFi 生态系统的迅速增长&#xff0c;以太坊 Layer 2 解决方案日益受到关注。 其中&#xff0c;zk Rollups 和 Optimistic Rollups 作为两种备受瞩目的主流 EVM&…

Mistral 7B v0.2 基础模型开源,大模型微调实践来了

Mistral AI在3月24日突然发布并开源了 Mistral 7B v0.2模型&#xff0c;有如下几个特点&#xff1a; 和上一代Mistral v0.1版本相比&#xff0c;上下文窗口长度从8k提升到32k&#xff0c;上下文窗口&#xff08;context window&#xff09;是指语言模型在进行预测或生成文本时&…

C++的并发世界(三)——线程对象生命周期

0.案例代码 先看下面一个例子&#xff1a; #include <iostream> #include <thread>void ThreadMain() {std::cout << "begin sub thread:" << std::this_thread::get_id()<<std::endl;for (int i 0; i < 10; i){std::cout <&…

Mac 下安装maven教程

note&#xff1a;网上已经有很多该类型教程了&#xff0c;这边自身保留一份&#xff0c;方便后面使用&#xff1b; 一、安装地址&#xff1a;官网 二、安装步骤 $ tar -xvf apache-maven-3.3.9-bin.tar.gz //mac支持手动点击解压 $ sudo mv -f apache-maven-3.3.9 /usr…

SRS OBS利用RTMP协议实现音视频推拉流;WebRTC 屏幕直播分享工具

一、SRS OBS利用RTMP协议实现音视频推拉流 参考&#xff1a;https://ossrs.net/lts/zh-cn/docs/v5/doc/getting-started 1&#xff09;docker直接运行SRS服务&#xff1a; docker run --rm -it -p 1935:1935 -p 1985:1985 -p 8080:8080 registry.cn-hangzhou.aliyuncs.co…

STM32 直接修改寄存器来输出内部时钟的方法

1. 在特殊情况下使能 MCO 功能的方法 在对某些不容易复现的问题进行代码调时&#xff0c;需要观察内部时钟的情况&#xff0c;但往往代码之前并没有使能 MCO 功能&#xff0c;在这种情况下就可以使用寄存器直接配置来输出内部时钟到GPIO 脚位上进行观察和测试。 下面的例子就…

Mysql实战--为什么表数据删掉一半,表文件大小不变

经常会有同学来问我&#xff0c;我的数据库占用空间太大&#xff0c;我把一个最大的表删掉了一半的数据&#xff0c;怎么表文件的大小还是没变&#xff1f; 那么今天&#xff0c;我就和你聊聊数据库表的空间回收&#xff0c;看看如何解决这个问题。 这里&#xff0c;我们还是针…