数据结构——树与二叉树

目录

树与二叉树

1.树的定义

2.树的有关术语

3.二叉树（BinaryTree）

二叉树的性质：

特殊的二叉树

·满二叉树：

·完全二叉树

二叉树的存储结构 

顺序存储结构

链式存储结构

二叉树以及对应接口的实现

1.二叉树架构搭建

2.二叉树的创建

3.二叉树的销毁

4.二叉树的前中后序

5.求树的节点个数

6.求叶子结点个数(无左右孩子，度为0)

7.求树的深度

8.二叉树的层序遍历

顾名思义就是一层一层从左到右遍历

 拓展知识

树与二叉树

1.树的定义

树是n（n>=0）个结点构成的有限集合。

·当n=0时，称为空树

·树中有一个特殊的结点被称作“根（root）”，其余结点可以分为m个不相交的有限集，其中每一个   集合都是一颗树，被称为原来树的子树。（对于空树来说）

2.树的有关术语

（1）结点：树中独立的单元格，包含一个数据元素及若干指向子树的分支。

（2）结点的度：结点的子树个数

（3）树的度：树中最大的结点的度，上图树的度为3.

（4）叶子结点：树中度为0的节点，叶子是这一类结点的总称。上图中的E、F、G、D都是叶子节点。

（5）双亲结点：有子树的结点，是其子树的双亲结点。上图的A就是B、C、D的双亲结点

（6）子结点：上图B、C、D是A的子结点

（7）兄弟结点：上图B、C、D互为兄弟结点

（8）结点的层次：根结点在1层，其他结点的层次等于其父节点的层次+1

  (9)   树的深度：所有结点中最大的层次就是树的深度

（10）森林：m棵不相交的树的集合

3.二叉树（BinaryTree）

二叉树是特殊的树，该树每个结点的度<=2。

二叉树的性质：

1.二叉树在第k层上最多有2^(k-1）个结点

2.深度为k的二叉树最多有2^k-1个结点

3.一颗二叉树如果度为0的结点有N0个，度为2的结点有N2个，则N0=N2+1

特殊的二叉树

·满二叉树：

深度为k且一共有2^k-1个结点，第i层的节点树为2^(i-1)

·完全二叉树

深度为k，前k-1层每层都是满结点，最后退成结点从左向右连续排列

二叉树的存储结构 

顺序存储结构

用数组存储二叉树，按从上到下，从左到右顺序存储。（比较适合满二叉树和完全二叉树）

对于普通的二叉树，存储起来空元素的结点就会导致空间的浪费

链式存储结构

这里最常用的存储类型就是运用两指针

1.两指针分别是左右孩子

2.两指针分别是左孩子和右兄弟

二叉树以及对应接口的实现

1.二叉树架构搭建

typedef char BTDataType;//利于适用于多种类型的数据操作

typedef  struct BinaryTree

{

        BTDataType val;

        struct BinaryTree*left;

        struct BinaryTree*right;//左右孩子指针

}BTNode;

2.二叉树的创建

BTNode* BTbyNode(BTDataType x)

{

        BTNode*newnode=(BTNode*)malloc(sizeof(BTNode));

        if(newnode==NULL)

        {

                perror("malloc fail!!!");

                return NULL;

        }

        newnode->val=x;

        newnode->left=NULL;

        newnode->right=NULL;

        

        return newnode;

}

BTNode* CreateTree()
{
    BTNode* l1 = BTByNode(1);
    BTNode* l2 = BTByNode(2);
    BTNode* l3 = BTByNode(3);
    BTNode* l4 = BTByNode(4);
    BTNode* l5 = BTByNode(5);

    l1->left = l4;
    l1->right = l2;
    l2->left = l3;
    l4->right = l5;

    return l1;
}

3.二叉树的销毁

void TreeDestroy(BTNode*root)

{

        if(root==NULL)

                return ;

        TreeDestroy(root->left);

        TreeDestroy(root->right);

        free(root);

        //root==NULL//这里是局部变量，在函数内部置空没有用，要在调用销毁函数的下面置空root

} 

4.二叉树的前中后序

关于二叉树非常重要的一个思想就是分治思想，将大问题转化成多个小问题去解决。换成二叉树也就是，将根节点问题不断转化给左右子树

void PrevOrder(BTNode*root)//前序----根---左---右

{

        if(root==NULL)

                return ；

        printf("%c  ",root->val);

        PrevOrder(root->left);

        PrevOrder(root->right);

} 

 void InOrder(BTNode*root)//中序----左---根---右

{

        if(root==NULL)

                return ;

        InOrder(root->left);

        printf("%c  ",root->val);

        InOrder(root->right);

}

void PostOrder(BTNode*root)//后序----左---右---根

{

        if(root==NULL)

                return ;

        PostOrder(root->left);

        PostOrder(root->right);

        printf("%c  ",root->val);

} 

5.求树的节点个数

int BinaryTreeSize(BTNode* root)

{

        return root==NULL?0:BinaryTreeSize(root->left)

                                        +BinaryTreeSize(root->right)+1;

} 

6.求叶子结点个数(无左右孩子，度为0)

int BinaryTreeleafSize(BTNode* root)

{

        if(root==NULL)

                return 0;

        if(root->left==NULL&&root->right==NULL)

                return 1；

        return BinaryTreeleafSize（root->left）+BinaryTreeleafSize(root->right);

} 

7.求树的深度

int BinaryTreeHeight(BTNode* root)

{

        if(root==NULL)

                return 0;

        int h1=BinaryTreeHeight(root->left);

        int h2=BinaryTreeHeight(root->right);

        return h1>h2?h1:h2;

} 

8.二叉树的层序遍历

顾名思义就是一层一层从左到右遍历

用一个队列来实现当一个根节点出队列，就将它的左右结点入队列，直到队列中无元素

void TreeLevelOrder(BTNode* root)

{

        Queue q;//创建一个队列对象

        QueueInit(&q);//队列初始化

        if(root)

                QueuePush(&q,root);//将根结点指针入队列

        

        while(!QueueEmpty(&q))//判断队列是否为空，为空说明遍历结束

        {

                BTNode*front=QueueFront(&q);//取队首元素,防止下面出队首元素找不到根结点位置

                QueuePop(&q);//将队首元素出队列

                if(front)

                {

                        printf("%c ",front->val);

                        QueuePush(&q,front->left);

                        QueuePush(&q,front->right);//将左右孩子入队列

                 }

        }

        TreeDestroy(root);

        root==NULL;

} 

 拓展知识

知道一个树的结点数量，怎么算出该树的可能有几种情况

我们定义f(n)表示结点数为n的二叉树的情况数

零个结点也是一种情况，所以f(0)=1;

一个结点时，只有一种情况，则f(1)=1;

两个结点时，有两种情况，根结点一个，剩下结点左右孩子各一种情况，则f(2)=f(1)+f(1)=2;

三个结点时，根节点一个节点，剩下结点分为三种情形：

1.左子树两个结点右子树零个

2.右子树两个结点左子树零个

3.左右子树各一个节点

则f(3)=f(2)*f(0)+f(1)*f(1)+f(0)*f(2)

经过推算得到f(n)=f(n-1)*f(0)+f(n-2)*f(1)+…+f(0)*f(n-1)

上述式子可以化简成（2n)! / ( n! (n+1)! )在数学中被称为卡特兰数

有了上述式子知道结点数就能轻松算出树可能存在的情况数

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

PSO-CNN-BiLSTM多输入分类预测|粒子群优化算法-卷积-双向长短期神经网络分类预测|Matlab

PSO-CNN-BiLSTM多输入分类预测|粒子群优化算法-卷积-双向长短期神经网络分类预测|Matlab

目录 一、程序及算法内容介绍&#xff1a; 基本内容&#xff1a; 亮点与优势&#xff1a; 二、实际运行效果&#xff1a; 三、算法介绍&#xff1a; 四、完整程序下载&#xff1a; 一、程序及算法内容介绍&#xff1a; 基本内容&#xff1a; 本代码基于Matlab平台编译&am…
阅读更多...
【Python机器学习系列】机器学习中的模型微调---随机搜索（案例+源码）

【Python机器学习系列】机器学习中的模型微调---随机搜索（案例+源码）

这是我的第245篇原创文章。 一、引言 如果探索的组合数量较少时&#xff0c;网格搜索是一种不错的方法&#xff0c;但当超参数的搜索范围较大时&#xff0c;通常会优先选择使用 RandomizedSearchCV 。它与 GridSearchCV 用法相似&#xff0c;但它不会尝试所有可能的组合&…
阅读更多...
智能医疗-行业痛点

智能医疗-行业痛点

信息来源渠道少 病患只能从特定时间巡房的医护处了解病情&#xff0c;信息来源渠道少&#xff0c;了解信息内容有限。 床头卡老旧&#xff0c;信息更新不及时 每位医护人员负责的床铺数量多&#xff0c;床头卡更新频率快&#xff0c;替换纸质床头卡需打印、手写、张贴等一系列…
阅读更多...
发展规划--IM系统

发展规划--IM系统

1、时代背景 5G应用&#xff0c;多终端应用&#xff0c;物联网应用&#xff0c;小程序&#xff0c;工业互联&#xff0c;大数据应用等等大前端时代的到来&#xff0c;程序员不能只关注crud&#xff0c;因为以后的服务并发量只会越来越多。 高并发架构师、大数据架构师或者说j…
阅读更多...
ABC346 A-G 题解

ABC346 A-G 题解

ABC346 A-G题解 A题目AC Code&#xff1a;时间复杂度 B题目时间复杂度AC Code&#xff1a; C题目时间复杂度AC Code&#xff1a; D题目时间复杂度AC Code&#xff1a; E题目时间复杂度AC Code&#xff1a; F题目时间复杂度AC Code&#xff1a; G题目时间复杂度AC Code&#xff…
阅读更多...
关于四篇GNN论文的阅读笔记PPT：包括GATNE，AM-GCN，HGSL和coGSL

关于四篇GNN论文的阅读笔记PPT：包括GATNE，AM-GCN，HGSL和coGSL

关于四篇GNN论文的阅读笔记PPT&#xff1a;包括GATNE&#xff0c;AM-GCN&#xff0c;HGSL和coGSL 前言GATNEAM-GCNHGSLcoGSL 前言 这里的PPT主要是在跟Graph Transformer一起的&#xff1a; 【图-注意力笔记&#xff0c;篇章1】Graph Transformer&#xff1a;包括Graph Trans…
阅读更多...
LeetCode每日一题——移除链表元素

LeetCode每日一题——移除链表元素

移除链表元素OJ链接&#xff1a;203. 移除链表元素 - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 思路&#xff1a; 这与之前的移除元素的题目很相似&#xff0c;那么我们同样可以用类似的做法&#xff08;双指针&#xff09;进行解题。但是这是一个链表删除&a…
阅读更多...
Less-1（sqlmap手工注入攻击）--sqli

Less-1（sqlmap手工注入攻击）--sqli

第一步&#xff1a;判断他是什么sql注入&#xff1f; 1 报错 1 and 12 -- 错误结果(--表示注释符) 1 and 11 -- 正确结果 第二步&#xff1a;判断返回字段数 ?id1 order by 3-- 正确显示结果 ?id1 order by 4--当列数为4时开始报错&#xff0c;所以只有三列 注&#xf…
阅读更多...
基于ssm的大学生心理健康的设计与实现

基于ssm的大学生心理健康的设计与实现

1 用户功能分析 1、注册、登录系统 2、心理预约指导&#xff1a;用户登录系统可以查看心理专家&#xff0c;可以预约时间进行指导。 3、在线交流&#xff1a;可以与其他用户进行交流互动 4、个人信息&#xff1a;可以修改个人信息&#xff0c;维护自己的信息 5、心理测试&…
阅读更多...
目标检测中的mAP计算原理和源码实现

目标检测中的mAP计算原理和源码实现

简介 在目标检测任务中&#xff0c;mAP&#xff08;mean Average Precision&#xff0c;平均精度均值&#xff09;是一个非常重要的评价指标&#xff0c;用于衡量模型在多个类别上的平均性能。它综合考虑了模型在不同召回率下的精确率&#xff0c;能够全面反映模型在检测任务中…
阅读更多...
VMware 调整产品方案，该跟随还是撤退？全面评估不同用户应对策略

VMware 调整产品方案，该跟随还是撤退？全面评估不同用户应对策略

本文针对 VMware 调整后的产品组合进行深入分析&#xff0c;并根据不同用户使用情况给出详细的应对策略&#xff0c;干货满满&#xff0c;建议收藏阅读&#xff01;重点内容包括&#xff1a; VMware 产品变化梳理不同用户如何选择应对策略&#xff1a;评估角度与应对思路梳理延…
阅读更多...
ChatGPT 对 ELT的理解

ChatGPT 对 ELT的理解

本文主要内容来自 ChatGPT 4.0 到底什么是 ETL&#xff1f;在数据库内部&#xff0c;把数据从 ODS 层加工成 DWD&#xff0c;再加工成 DWS&#xff0c;这个过程和 ETL 的关系是什么&#xff1f;带着这些问题&#xff0c;我问了一下 ChatGPT&#xff0c;总结如下。 数据在两个数…
阅读更多...
下载最新VMware，社区版本（免费）

下载最新VMware，社区版本（免费）

VMware - Delivering a Digital Foundation For BusinessesRun any app on any cloud on any device with a digital foundation built on VMware solutions for modern apps, multi-cloud, digital workspace, security & networking.https://www.vmware.com/ 官网地址
阅读更多...
【SpringBoot】了解简单原理 Bean管理 配置优先级

【SpringBoot】了解简单原理 Bean管理 配置优先级

文章目录 一、配置优先级1.1 命令行设置端口号1.2 打包后修改端口号1.3 优先级 小结 二、Bean的管理2.1 获取Bean2.2 Bean作用域2.3 第三方Bean 三、剖析Springboot的底层原理3.1 起步依赖3.2 自动配置3.2.1 第三方类装配3.2.2 原理分析 总结Web后端开发总结&#xff1a;源码跟…
阅读更多...
笔记本电脑与服务器首选：PW1605可编程电流限制开关，稳定可靠新标准

笔记本电脑与服务器首选：PW1605可编程电流限制开关，稳定可靠新标准

一般描述 PW1605 是一款电流限制开关&#xff0c;具有可编程输入过压保护和输出电压箝位功能。集成保护 N 沟道 FET 具有极低的 RDS&#xff08;ON&#xff09; 功能&#xff0c;PW1605有助于降低正常工作期间的功率损耗。可编程软启动时间控制启动期间输出电压的压摆率。独立的…
阅读更多...
python实现常见统计量与统计分布

python实现常见统计量与统计分布

一. 基本概念 1. 总体 一个统计问题研究对象的全体称为总体&#xff0c;构成总体的每个成员称为个体。 2. 样本 一般由于总体的数量是非常巨大的&#xff0c;不可能对全部总体进行研究&#xff0c;通常会对总体进行抽样进行研究。 从总体中按一定规则抽出的一部分个体称为…
阅读更多...
UE4_官方动画内容示例1.2_动画蓝图——使用蓝图告知Actor播放动画

UE4_官方动画内容示例1.2_动画蓝图——使用蓝图告知Actor播放动画

展示了两个示例&#xff1a;在其中一个示例中&#xff0c;使用蓝图告知Actor播放动画&#xff0c;在另外一个示例中&#xff0c;展示了告知Actor播放动画的动画蓝图&#xff08;例如&#xff0c;此示例展示了如何将变量从蓝图传递给动画蓝图&#xff0c;并演示了如何将现有姿势…
阅读更多...
.NET高级面试指南专题二十三【 B+ 树作为索引有什么优势】

.NET高级面试指南专题二十三【 B+ 树作为索引有什么优势】

B 树作为索引有许多优势&#xff0c;这些优势使其成为许多数据库管理系统中首选的索引结构之一。以下是 B 树作为索引的一些主要优势&#xff1a; 高效的查询性能&#xff1a;B 树是一种平衡树结构&#xff0c;具有良好的平衡性和高度平衡的性质&#xff0c;这使得在 B 树上进行…
阅读更多...
leetcode刷题日记-滑铁卢了家人们（解数独）

leetcode刷题日记-滑铁卢了家人们（解数独）

问题描述 解题思路 看到这个题&#xff0c;给我的感觉是什么玩意啊&#xff01;仔细读题之后&#xff0c;真的没想到解题思路。然后看了题解&#xff0c;用到了回溯算法&#xff0c;感觉这个回溯和N皇后的问题差不太多。然后就照着思路尝试理解了一遍&#xff0c;感觉这种题目…
阅读更多...
电脑怎么解除安全模式?

电脑怎么解除安全模式?

安全模式是windows系统中的一种特殊模式，在安全模式可以让系统仅载入最低需求的驱动程序来启动电脑，用户可以在此模式下检测或故障排除。可是一些用户却不知道怎么解除安全模式。下面，极客狗就为大家带来电脑怎么解除安全模式的方法吧。 解除安全模式的方法: 1、 首先，在安…
阅读更多...
最新文章

Copyright @ 2022~2023