二叉树尾部分

news/2024/7/22 1:38:08/文章来源:https://blog.csdn.net/2302_80378107/article/details/139214607

1.二叉树的销毁

2.二叉树的层序遍历

3.判断二叉树是否为完全二叉树

4.二叉树的性质

1.二叉树的销毁

以后序的方式遍历销毁左右子数,因为前序和中序销毁的话根会被销毁而找不到左右子树的位置,后序的根访问在最后,可以找到左右的子树位置。

void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
}

2.二叉树的层序遍历(BFS广度优先遍历)

注意点:因为实现二叉树的层序遍历需要用到队列的代码,如果是想把之前写的队列代码拷贝过来,则需要把其文件复制到当前的工程目录中,才可以用include去找到对应的代码。

(前序是深度优先遍历DFS)

实现的思想:

把树的结点地址放进队列中,先把树的根结点放进队列,然后再出队列,出队列的同时把根结点的左右子结点放进队列,每次出队列时,都把出的结点的左右子结点放进队列,上一层带下一层,出队列的同时打印其的值,就是一层一层的出来。

void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}QueueDestroy(&q);
}
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode

代码分析:

(注意QDataType的类型是BTNode*,并不是int,val存储的是树结点地址)

首先创建一个队列,把树的根结点地址放进去 ,然后使用循环while,以队列是否为NULL作为条件,使用一个指针front去接收队列出的指针,然后再出队列的数据,需要注意的是QueuePop中free的是队列的空间,并不是树的空间,所以下面能用front去访问其他的结点与值,不为NULL就进队列,然后下一个循环又出,达到层序遍历的目的。

3.判断二叉树是否为完全二叉树

实现思想:

用层序遍历来解决,创建一个队列,把树的结点以地址的形式放进队列中,空的结点也放进去(待会会以这个为判断),每取出队列的数据就判断值是否为NULL,如果为NULL就跳出循环,这时候队列还有数据为出队列,接下来就是进队列去遍历队列,如果有非空的值,就说明这个数不是完全二叉树,否则为完全二叉树。这样判断是因为如果不是完全二叉树,最后一层的结点是不连续的,有空结点插在非空的结点之中,依照层序来看的话,就是队列中空和非空都放在一起,所以以第一个取出值为NULL时,就跳出循环,因为此时非空的结点已经出队列了,有一个非空还在队列中(假设不是完全二叉树),就可以以此来判断了。

void TreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}while (!QueueEmpty(&q)){BTNode* a = QueueFront(&q);QueuePop(&q);if (a){printf("no");return;}}printf("yes");QueueDestroy(&q);
}

4.二叉树的性质

 性质3:N0=N2+1,(一般性感兴趣可以搜索)可以先用特殊的来验证,满二叉树来看,最后一层都是度为0的,其余的都是度为2的,最后一层有2^(h-1)个,出去最后一层共有2^(h-1)-1个结点,则相减就为1.

题目一:

 

 

 题目二:

题目三:

把下面还原成树的形状

前序:1 2 3 4 5 7 6

中序3 2 1 5 7 4 6 

解析:

全代码

test文件:

#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;BinaryTreeNode* left;BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(int x)
{BTNode* a = (BTNode*)malloc(sizeof(BTNode));if (a == NULL){perror("malloc fail:");return 0;}a->data = x;a->left = NULL;a->right = NULL;return a;
}BTNode* CreatNode()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node2->right = node7;node4->left = node5;node4->right = node6;return node1;
}
void PrevOver(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOver(root->left);PrevOver(root->right);
}int TreeNode(BTNode* root)
{return root == NULL ? 0 : TreeNode(root->left) + TreeNode(root->right) + 1;
}int TreeHeight(BTNode* root)
{if (root == NULL){return 0;}int heightleft = TreeHeight(root->left);int heightright = TreeHeight(root->right);return heightleft > heightright ? heightleft +1 : heightright +1;
}
int LeafNode(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return LeafNode(root->left) + LeafNode(root->right);
}
int TreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
BTNode* TreeFind(BTNode* root, int x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* a = TreeFind(root->left, x);if (a){return a;}BTNode* b = TreeFind(root->right, x);if (b){return b;}return NULL;
}
void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
}void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}QueueDestroy(&q);
}
void TreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}while (!QueueEmpty(&q)){BTNode* a = QueueFront(&q);QueuePop(&q);if (a){printf("no");return;}}printf("yes");QueueDestroy(&q);
}
int main()
{BTNode* root = CreatNode();//PrevOver(root);//int ret = TreeNode(root);//int ret1 = TreeHeight(root);//int ret1 = LeafNode(root);//int k = 2;//int ret1=TreeLevelKSize(root, k);//printf("%d", ret1);//int x = 2;//BTNode* a=TreeFind(root, x);//TreeLevelOrder(root);TreeComplete(root);//printf("%d", (*a).data);
}

Queue.h文件:
 

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<stdbool.h>typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);// 队尾插入
void QueuePush(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);// 取队头和队尾的数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);int QueueSize(Queue* pq);
bool QueueEmpty(Queu

Queue.c文件:

#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);/*QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;if (pq->phead == NULL)pq->ptail = NULL;*/// 一个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else // 多个节点{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

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

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

相关文章

YOLOv10介绍与推理--图片和视频演示(附源码)

导 读 本文主要对YOLOv10做简单介绍并给出推理图片和视频的步骤演示。 YOLOv10简介 YOLOv10是清华大学的研究人员在Ultralytics Python包的基础上&#xff0c;引入了一种新的实时目标检测方法&#xff0c;解决了YOLO 以前版本在后处理和模型架构方面的不足。通过消除非最大抑…

从零开始打造教育APP:在线教育系统源码与开发流程

很多人疑问&#xff0c;应该如何从零开始打造一个在线教育APP&#xff1f;今天&#xff0c;小编将详细为大家讲解在线教育系统的源码与开发流程。 一、需求分析 对于在线教育APP&#xff0c;需要要明确以下几点&#xff1a; 1.目标用户&#xff1a;明确APP的用户群体&#xf…

类 和 对象(二)

构造方法 接上篇&#xff0c;若每次都想下面的setDate方法给对象初始化&#xff0c;未免比较麻烦&#xff0c;那有什么方法可以让初始化更加简便呢&#xff1f; public void setDate(int year, int month, int day){this.year year;this.month month;this.day day;}答&#…

2024.5.27 作业 xyt

定义自己的命名空间my_sapce&#xff0c;在my_sapce中定义string类型的变量s1&#xff0c;再定义一个函数完成对字符串的逆置 #include <iostream>using namespace std; namespace my_space {string s1"hello world";void my_strreverse(string str); } using…

C++笔试强训day34

目录 1.ISBN号码 2.kotori和迷宫 3.矩阵最长递增路径 1.ISBN号码 链接https://www.nowcoder.com/practice/95712f695f27434b9703394c98b78ee5?tpId290&tqId39864&ru/exam/oj 提取题意&#xff0c;模拟一下即可。 #include <iostream> using namespace std; …

《我的阿勒泰》读后感

暂没时间写&#xff0c;记录在此&#xff0c;防止忘记&#xff0c;后面补上!!! 【经典语录】 01、如果天气好的话&#xff0c;阳光广阔地照耀着世界&#xff0c;暖洋洋又懒洋洋。这样的阳光下&#xff0c;似乎脚下的每一株草都和我一样&#xff0c;也把身子完全舒展开了。 02、…

Qt---录音

1.获取麦克风阵列&#xff1a; QList<QAudioDeviceInfo> infos QAudioDeviceInfo::availableDevices(QAudio::AudioInput);for (int i 0; i < infos.count(); i){qDebug() << infos.at(i).deviceName();} "麦克风阵列 (Realtek(R) Audio)" 2.QAudio…

内存泄漏案例分享3-view的内存泄漏

案例3——view内存泄漏 前文提到&#xff0c;profile#Leaks视图无法展示非Activity、非Fragment的内存泄漏&#xff0c;换言之&#xff0c;除了Activity、Fragment的内存泄漏外&#xff0c;其他类的内存问题我们只能自己检索hprof文件查询了。 下面有一个极佳的view内存泄漏例子…

ubuntu20.04 10分钟搭建无延迟大疆无人机多线程流媒体服务器

1.使用效果 无人机画面 2.服务器视频端口 3.使用教程 3.1.下载ubuntu对应软件包&#xff1a;系统要求ubuntu16以上 3.2修改端口&#xff08;config.xml文件&#xff09; 3.3启动服务 目录下输入&#xff1a;终端启动&#xff1a;./smart_rtmpd 后台启动&#xff1a;nohup ./…

如何选择序列化协议:关键因素与场景分析

如何选择序列化协议&#xff1a;关键因素与场景分析 序列化协议的选择直接影响着系统的性能、可维护性及跨平台兼容性。以下是针对不同场景下&#xff0c;几种常见序列化协议的选择建议&#xff1a; 1. 公司间系统调用&#xff08;性能要求宽松&#xff09; SOAP (基于XML)&a…

LeetCode 279 —— 完全平方数

阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路 此图利用动态规划进行求解&#xff0c;首先&#xff0c;我们求出小于 n n n 的所有完全平方数&#xff0c;存放在数组 squareNums 中。 定义 dp[n] 为和为 n n n 的完全平方数的最小数量&#xff0c;那么有状态…

操作教程|通过DataEase开源BI工具对接金山多维表格

前言 金山多维表格是企业数据处理分析经常会用到的一款数据表格工具&#xff0c;它能够将企业数据以统一的列格式整齐地汇总至其中。DataEase开源数据可视化分析工具可以与金山多维表格对接&#xff0c;方便企业更加快捷地以金山多维表格为数据源&#xff0c;制作出可以实时更…

k8s pv 一直是release状态

如下图所示&#xff0c;pv 一直是release状态 这个时候大家可能就会想到现在我的 PVC 被删除了&#xff0c;PV 也变成了 Released 状态&#xff0c;那么我重建之前的 PVC 他们不就可以重新绑定了&#xff0c;事实并不会&#xff0c;PVC 只能和 Available 状态的 PV 进行绑定。…

ssm137基于SSM框架的微博系统+vue

微博系统网站的设计与实现 摘 要 网络技术和计算机技术发展至今&#xff0c;已经拥有了深厚的理论基础&#xff0c;并在现实中进行了充分运用&#xff0c;尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代&#xff0c;所以对于信息的宣传和管理就…

保安维稳,四信以科技构筑高速公路安全智慧防线

近日&#xff0c;广东梅大高速发生严重塌方事故&#xff0c;造成了严重的人员伤亡和财产损失。这一事件在公众心中敲响了安全的警钟&#xff0c;再次引起了公众对于交通设施运营安全性的重点关注。 国务院安委会办公室和国家防灾减灾救灾委员会办公室等主管机构先后印发紧急通知…

make disclean V=1 分析

文章目录 make distclean步骤1&#xff1a;2090-2114行&#xff0c;执行依赖 clean步骤2&#xff1a;2120-2124行&#xff0c;执行依赖 $(mrproper-dirs)步骤3&#xff1a;2118-2129行&#xff0c;执行依赖 mrproper步骤4&#xff1a;2135-2142行&#xff0c;实现 distclean 编…

flutter 的webview中touchstart和touchend 执行异常问题解决

效果 背景 使用flutter 调用webview内网页&#xff0c;网页内容是监听touchstart和 touchend&#xff0c;触发不同是事件&#xff0c;但是发现每次长按都 手指抬起后 才会执行 touchstart和touchend&#xff0c;满足不了我的需求&#xff0c;我的需求是当手指按下 立即执行touc…

大模型时代的具身智能系列专题(三)

清华高阳团队 高阳为清华叉院助理教授&#xff0c;本科毕业于清华大学计算机系&#xff0c;博士毕业于UC Berkeley。博士导师是Vision领域的大牛Trevor Darrell&#xff0c;读博期间和Sergey Levine合作开始强化学习方面的探索&#xff0c;博后跟随Pieter Abbeel做强化学习&am…

Windows下mingw32编译ffmpeg5.1.4实现rtsp拉流

由于客户要求&#xff0c;要在Windows下使用mingw32编译&#xff0c;去ffmpeg.org下载需要编译的版本&#xff0c;使用msys2方法进行编译&#xff0c;使用QT5.10的编译器&#xff0c;基本上把网上的方法试了个遍&#xff0c;编译全部库总是报错出问题 查看了ffbuild文件夹中con…

【全开源】JAVA情侣扭蛋机情侣游戏系统源码支持微信小程序+微信公众号+H5

一、引言&#xff1a;增添恋爱甜蜜&#xff0c;扭出惊喜时刻 在恋爱生活中&#xff0c;总是需要一些小小的惊喜和乐趣来增添甜蜜。为此&#xff0c;我们精心打造了“情侣扭蛋机情侣游戏系统小程序源码”&#xff0c;为情侣们提供一个充满趣味和创意的互动平台。 二、独特扭蛋…