【数据结构与算法】树和二叉树

【数据结构与算法】树和二叉树

文章目录

  • 【数据结构与算法】树和二叉树
  • 前言
  • 一、树的基本概念
  • 二、二叉树的基本概念
  • 三、二叉树的递归遍历
  • 四、二叉树的编程
  • 五、二叉树的非递归遍历
  • 总结

前言

本篇文章将讲到树的基本概念，二叉树的基本概念，二叉树的递归遍历，二叉树的编程，二叉树的非递归遍历

一、树的基本概念

在这里插入图片描述

树的定义：

由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。

树的结构特点：

  • 非线性结构，有一个直接前驱，但可能有多个直接后继（1:n）
    树的定义具有递归性，树中还有树。
    树可以为空，即节点个数为0。

若干术语：
在这里插入图片描述

  • 根 即根结点(没有前驱)
    叶子 即终端结点(没有后继)
    森林 指m棵不相交的树的集合(例如删除A后的子树个数)
    有序树 结点各子树从左至右有序，不能互换（左为第一）
    无序树 结点各子树可互换位置。
    双亲 即上层的那个结点(直接前驱) parent
    孩子 即下层结点的子树 (直接后继) child
    兄弟 同一双亲下的同层结点（孩子之间互称兄弟）sibling
    堂兄弟 即双亲位于同一层的结点（但并非同一双亲）cousin
    祖先 即从根到该结点所经分支的所有结点
    子孙 即该结点下层子树中的任一结点
    结点 即树的数据元素
    结点的度 结点挂接的子树数（有几个直接后继就是几度）
    结点的层次 从根到该结点的层数（根结点算第一层）
    终端结点 即度为0的结点，即叶子
    分支结点 除树根以外的结点（也称为内部结点）
    树的度 所有结点度中的最大值（Max{各结点的度}）
    树的深度(或高度) 指所有结点中最大的层数（Max{各结点的层次}）
    上图中的结点数＝ 13，树的度＝ 3，树的深度＝ 4

二、二叉树的基本概念

定义：
n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。

逻辑结构：
一对二（1：2）

基本特征:

  • 每个结点最多只有两棵子树（不存在度大于2的结点）；
    左子树和右子树次序不能颠倒（有序树）。

基本形态:
在这里插入图片描述
二叉树性质

  • 性质1: 在二叉树的第i层上至多有 2^(i-1) 个结点（i>0）
    性质2: 深度为k的二叉树至多有 2^k-1 个结点（k>0）
    性质3: 对于任何一棵二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）
    性质4: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

概念解释：

  • 满二叉树
    一棵深度为k 且有2k -1个结点的二叉树。
    特点：每层都“充满”了结点
    在这里插入图片描述

  • 完全二叉树
    除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。
    在这里插入图片描述
    理解：k-1层与满二叉树完全相同，第k层结点尽力靠左

三、二叉树的递归遍历

遍历方法：
牢记一种约定，对每个结点的查看都是“先左后右” 。
限定先左后右，树的遍历有三种实现方案：
DLR LDR LRD
先 (根)序遍历 中 (根)序遍历 后(根)序遍历
DLR — 先序遍历，即先根再左再右
LDR — 中序遍历，即先左再根再右
LRD — 后序遍历，即先左再右再根
注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。
从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>struct BinaryNode
{//数据域char ch;//指针域struct BinaryNode* lChild;struct BinaryNode* rChild;};void recursion(struct BinaryNode* root)
{if (root == NULL){return;}//先序遍历printf("%c ", root->ch);recursion(root->lChild);recursion(root->rChild);}void test01()
{struct BinaryNode nodeA = { 'A', NULL, NULL };struct BinaryNode nodeB = { 'B', NULL, NULL };struct BinaryNode nodeC = { 'C', NULL, NULL };struct BinaryNode nodeD = { 'D', NULL, NULL };struct BinaryNode nodeE = { 'E', NULL, NULL };struct BinaryNode nodeF = { 'F', NULL, NULL };struct BinaryNode nodeG = { 'G', NULL, NULL };struct BinaryNode nodeH = { 'H', NULL, NULL };//建立关系nodeA.lChild = &nodeB;nodeA.rChild = &nodeF;nodeB.rChild = &nodeC;nodeC.lChild = &nodeD;nodeC.rChild = &nodeE;nodeF.rChild = &nodeG;nodeG.lChild = &nodeH;//递归遍历recursion(&nodeA);
}int main()
{test01();system("pause");return EXIT_SUCCESS;
}

在这里插入图片描述

四、二叉树的编程

  • 计算二叉树叶子数量
  • 获取树的高度
  • 拷贝二叉树
  • 递归遍历
  • 释放二叉树
#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>struct BinaryNode
{//数据域char ch;//指针域struct BinaryNode* lChild;struct BinaryNode* rChild;
};//计算二叉树叶子数量
void calculateLeafNum(struct BinaryNode* root, int* p)
{if (root == NULL){return;}//如果节点 左子树 与右子树 同时为空  称为叶子if (root->lChild == NULL && root->rChild == NULL){(*p)++;}calculateLeafNum(root->lChild, p);calculateLeafNum(root->rChild, p);}//获取树的高度
int getTreeHeight(struct BinaryNode* root)
{if (root == NULL){return 0;}//获取左子树高度int lHeight = getTreeHeight(root->lChild);//获取右子树高度int rHeight = getTreeHeight(root->rChild);//从左子树和右子树中取大的值+1int height = lHeight > rHeight ? lHeight + 1 : rHeight + 1;return height;
}//拷贝二叉树
struct BinaryNode* copyTree(struct BinaryNode* root)
{if (root == NULL){return NULL;}//先拷贝左子树struct BinaryNode* lChild = copyTree(root->lChild);//再拷贝右子树struct BinaryNode* rChild = copyTree(root->rChild);struct BinaryNode* newNode = malloc(sizeof(struct BinaryNode));newNode->ch = root->ch;newNode->lChild = lChild;newNode->rChild = rChild;return newNode;
}void recursion(struct BinaryNode* root)
{if (root == NULL){return;}printf("%c ", root->ch);recursion(root->lChild);recursion(root->rChild);}void freeTree(struct BinaryNode* root)
{if (root == NULL){return;}//先释放左子树freeTree(root->lChild);//再释放右子树freeTree(root->rChild);//释放根printf("%c被释放了\n", root->ch);free(root);
}void test01()
{struct BinaryNode nodeA = { 'A', NULL, NULL };struct BinaryNode nodeB = { 'B', NULL, NULL };struct BinaryNode nodeC = { 'C', NULL, NULL };struct BinaryNode nodeD = { 'D', NULL, NULL };struct BinaryNode nodeE = { 'E', NULL, NULL };struct BinaryNode nodeF = { 'F', NULL, NULL };struct BinaryNode nodeG = { 'G', NULL, NULL };struct BinaryNode nodeH = { 'H', NULL, NULL };//建立关系nodeA.lChild = &nodeB;nodeA.rChild = &nodeF;nodeB.rChild = &nodeC;nodeC.lChild = &nodeD;nodeC.rChild = &nodeE;nodeF.rChild = &nodeG;nodeG.lChild = &nodeH;//1、求二叉树 叶子数量int num = 0;calculateLeafNum(&nodeA, &num);printf("树的叶子数量为：%d\n", num);//2、 求树的高度/深度int height = getTreeHeight(&nodeA);printf("树的高度为：%d\n", height);//3、 拷贝二叉树struct BinaryNode* newTree = copyTree(&nodeA);//递归遍历recursion(newTree);printf("\n");//4、 释放二叉树freeTree(newTree);}int main() {test01();system("pause");return EXIT_SUCCESS;
}

五、二叉树的非递归遍历

利用栈容器可以实现二叉树的非递归遍历
首先将每个节点都设置一个标志，默认标志为假，根据节点的的状态进行如下流程。
在这里插入图片描述
执行上述流程，可以得到先序遍历的结果，如果想得到其他二叉树遍历结果，修改2.4步骤即可。

seqStack.h

#pragma  once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>#define  MAX 1024//struct SStack
//{
//	void * data[MAX];  //栈的数组
//
//	int m_Size; //栈大小
//};typedef void * SeqStack;//初始化栈
SeqStack init_SeqStack();//入栈
void push_SeqStack(SeqStack stack, void * data);//出栈
void pop_SeqStack(SeqStack stack);//返回栈顶
void * top_SeqStack(SeqStack stack);//返回栈大小
int size_SeqStack(SeqStack stack);//判断栈是否为空
int isEmpty_SeqStack(SeqStack stack);//销毁栈
void destroy_SeqStack(SeqStack stack);

seqStack.c

#include "seqStack.h"struct SStack
{void * data[MAX];  //栈的数组int m_Size; //栈大小
};//初始化栈
SeqStack init_SeqStack()
{struct SStack * myStack = malloc(sizeof(struct SStack));if (myStack == NULL){return NULL;}//初始化数组memset(myStack->data, 0, sizeof(void *)* MAX);//初始化栈大小myStack->m_Size = 0;return myStack;
}
//入栈
void push_SeqStack(SeqStack stack, void * data)
{//入栈本质  --- 数组尾插if (stack == NULL){return;}if (data == NULL){return;}struct SStack * mystack = stack;if (mystack->m_Size == MAX){return;}mystack->data[mystack->m_Size] = data;mystack->m_Size++;
}
//出栈
void pop_SeqStack(SeqStack stack)
{//出栈本质  --- 数组尾删if (stack == NULL){return;}struct SStack * mystack = stack;if (mystack->m_Size == 0){return;}mystack->data[mystack->m_Size - 1] = NULL;mystack->m_Size--;}
//返回栈顶
void * top_SeqStack(SeqStack stack)
{if (stack == NULL){return NULL;}struct SStack * mystack = stack;if (mystack->m_Size == 0){return NULL;}return mystack->data[mystack->m_Size - 1];
}
//返回栈大小
int size_SeqStack(SeqStack stack)
{if (stack == NULL){return -1;}struct SStack * mystack = stack;return mystack->m_Size;}
//判断栈是否为空
int isEmpty_SeqStack(SeqStack stack)
{if (stack == NULL){return -1;//返回-1代表真  空栈}struct SStack * mystack = stack;if (mystack->m_Size == 0){return 1;}return 0; //返回0 代表 不是空栈}
//销毁栈
void destroy_SeqStack(SeqStack stack)
{if (stack == NULL){return;}free(stack);stack = NULL;
}

这里是引用

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include "seqStack.h"struct BinaryNode
{//数据域char ch;//指针域struct BinaryNode* lChild;struct BinaryNode* rChild;//标志int flag;
};/*
1、将根节点 入栈
2、只要栈中元素个数大于 0  执行循环获取栈顶元素出栈如果标志位真  直接输出  并且执行下一次循环如果为假 将标志改为真将右子树  左子树 根 入栈执行下一次循环
*/void nonRecursion(struct BinaryNode* root)
{//初始化栈SeqStack myStack = init_SeqStack();push_SeqStack(myStack, root);while (size_SeqStack(myStack) > 0){//获取栈顶元素struct BinaryNode* pTop = top_SeqStack(myStack);//出栈pop_SeqStack(myStack);//如果标志位真  直接输出  并且执行下一次循环if (pTop->flag == 1){printf("%c ", pTop->ch);continue;}//如果为假 将标志改为真pTop->flag = 1;//将右子树  左子树 根 入栈if (pTop->rChild != NULL){push_SeqStack(myStack, pTop->rChild);}if (pTop->lChild != NULL){push_SeqStack(myStack, pTop->lChild);}push_SeqStack(myStack, pTop);}//销毁栈destroy_SeqStack(myStack);}void test01()
{struct BinaryNode nodeA = { 'A', NULL, NULL,0 };struct BinaryNode nodeB = { 'B', NULL, NULL,0 };struct BinaryNode nodeC = { 'C', NULL, NULL,0 };struct BinaryNode nodeD = { 'D', NULL, NULL,0 };struct BinaryNode nodeE = { 'E', NULL, NULL,0 };struct BinaryNode nodeF = { 'F', NULL, NULL,0 };struct BinaryNode nodeG = { 'G', NULL, NULL,0 };struct BinaryNode nodeH = { 'H', NULL, NULL,0 };//建立关系nodeA.lChild = &nodeB;nodeA.rChild = &nodeF;nodeB.rChild = &nodeC;nodeC.lChild = &nodeD;nodeC.rChild = &nodeE;nodeF.rChild = &nodeG;nodeG.lChild = &nodeH;//非递归遍历nonRecursion(&nodeA);}int main() {test01();system("pause");return EXIT_SUCCESS;
}

总结

到这里这篇文章的内容就结束了，谢谢大家的观看，如果有好的建议可以留言喔!

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

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

相关文章

大语言模型---Llama7B和Llama8B的区别；模型参数量；权重文件的不同；嵌入层权重的不同；输入序列长度的不同；应用场景

大语言模型---Llama7B和Llama8B的区别；模型参数量；权重文件的不同；嵌入层权重的不同；输入序列长度的不同；应用场景

文章目录 1.概要2. 模型参数量3. 权重文件的不同4. 嵌入层权重的不同5. 输入序列长度的不同6. 应用场景 1.概要 LLaMA&#xff08;Large Language Model Meta AI&#xff09;是由Meta开发的一系列语言模型&#xff0c;其中不同版本的参数量&#xff08;如7B、8B等&#xff09;…
阅读更多...
Android Binder技术概览

Android Binder技术概览

Android中的Binder是一种基于远程过程调用&#xff08;Remote Procedure Call, RPC&#xff09;的轻量级通信机制&#xff0c;核心用于 Android 系统中的进程间通信&#xff08;Inter-Process Communication, IPC&#xff09;。Binder 是 Android 系统中不可或缺的一部分&#…
阅读更多...
NoteExpress导入知网论文无法智能更新题录的处理方法

NoteExpress导入知网论文无法智能更新题录的处理方法

知网论文下载下来一般为“标题_作者.caj”&#xff0c;只要在导入文件时对字段默认值进行设置就行了。 其他地方下载的论文也是一样&#xff0c;根据文件名称设置字段默认值。
阅读更多...
搜索二维矩阵

搜索二维矩阵

搜索二维矩阵 给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#xff0c;如果 target 在矩阵中&#xff0c;返回 true &#xff1b;否则&#xff0c…
阅读更多...
Mysql中的 TEXT 和 BLOB 解析

Mysql中的 TEXT 和 BLOB 解析

&#x1f680; 博主介绍&#xff1a;大家好&#xff0c;我是无休居士&#xff01;一枚任职于一线Top3互联网大厂的Java开发工程师&#xff01; &#x1f680; &#x1f31f; 在这里&#xff0c;你将找到通往Java技术大门的钥匙。作为一个爱敲代码技术人&#xff0c;我不仅热衷…
阅读更多...
2024强网拟态决赛-eBeepf

2024强网拟态决赛-eBeepf

漏洞分析与利用 分析后面看情况吧&#xff0c;有时间再写吧&#xff0c;先贴个利用脚本&#xff1a; #ifndef _GNU_SOURCE #define _GNU_SOURCE #endif#include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <fcntl.h> #include <…
阅读更多...
Duolingo「多邻国」v6.9.0 解锁Max高级版

Duolingo「多邻国」v6.9.0 解锁Max高级版

前言 Duolingo是一个特别有名的学语言的应用软件&#xff0c;你可以用它来学西班牙语、法语、德语、意大利语、俄语等等好多种语言。当然&#xff0c;用它来学英语也是个不错的选择。 安装环境 [名称]&#xff1a;Duolingo「多邻国」 [大小]&#xff1a;79MB [版本]&#x…
阅读更多...
鸿蒙开发-音视频

鸿蒙开发-音视频

Media Kit 特点 一般场合的音视频处理&#xff0c;可以直接使用系统集成的Video组件&#xff0c;不过外观和功能自定义程度低Media kit&#xff1a;轻量媒体引擎&#xff0c;系统资源占用低支持音视频播放/录制&#xff0c;pipeline灵活拼装&#xff0c;插件化扩展source/demu…
阅读更多...
基于SSM的婚庆管理系统+LW示例参考

基于SSM的婚庆管理系统+LW示例参考

1.项目介绍 系统角色&#xff1a;管理员、商家&#xff08;婚庆公司&#xff09;、用户功能模块&#xff1a;管理员&#xff08;用户管理、商家管理、摄影风格管理、礼服款式管理、案例管理、婚车品牌管理、婚纱拍摄管理、策划服务管理、婚宴酒店管理、婚车套餐管理、在线咨询…
阅读更多...
manin动画编程（安装+入门）

manin动画编程（安装+入门）

文章目录 1.基本介绍2.效果展示3.安装步骤3.1安装manba软件3.2配置环境变量3.3查看是否成功3.4什么是mamba3.5创建虚拟环境3.6尝试进入虚拟环境 4.vscode操作4.1默认配置文件 5.安装ffmpeg6.安装manim软件6.vscode制作7.我的学习收获 1.基本介绍 这个manim就是一款软件&#x…
阅读更多...
CH595 驱动数码管

CH595 驱动数码管

先上原理图 我手里的是型号SR410361K的 4段数码管是共阳的&#xff08;低电平驱动&#xff09;&#xff0c;先发送数据&#xff0c;然后发送片选 共阴 共阳的图如下&#xff1a; 如何测量呢&#xff1f; 首先将数字万用表档位调节到蜂鸣器/二极管档&#xff0c;红表笔和黑表笔…
阅读更多...
Vue生命周期详解

Vue生命周期详解

目录 1.beforeCreate2.created3.beforeMount4.mounted5.beforeUpdate6.updated7.beforeUnmount&#xff08;beforeDestroy&#xff09;8.unmounted&#xff08;destroyed&#xff09; 1.beforeCreate 分析 beforeCreate执行时Vue实例还没有被创建&#xff0c;data和methods也…
阅读更多...
MySQL底层概述—1.InnoDB内存结构

MySQL底层概述—1.InnoDB内存结构

大纲 1.InnoDB引擎架构 2.Buffer Pool 3.Page管理机制之Page页分类 4.Page管理机制之Page页管理 5.Change Buffer 6.Log Buffer 1.InnoDB引擎架构 (1)InnoDB引擎架构图 (2)InnoDB内存结构 (1)InnoDB引擎架构图 下面是InnoDB引擎架构图&#xff0c;主要分为内存结构和磁…
阅读更多...
【力扣算法题】双指针-战场上的矛与盾的组合（移动零）（快乐数）

【力扣算法题】双指针-战场上的矛与盾的组合（移动零）（快乐数）

前言 &#x1f31f;&#x1f31f;本期讲解关于力扣算法两道双指针题目解析~~~ &#x1f308;感兴趣的小伙伴看一看小编主页&#xff1a;GGBondlctrl-CSDN博客 &#x1f525; 你的点赞就是小编不断更新的最大动力 &#x1f386;那么…
阅读更多...
第三十九篇 ShuffleNet V1、V2模型解析

第三十九篇 ShuffleNet V1、V2模型解析

摘要 ShuffleNet V1 ShuffleNet V1是由旷视科技&#xff08;Megvii&#xff0c;又称Face&#xff09;在2017年底提出的一种轻量级卷积神经网络架构。该网络专为移动设备和边缘计算环境设计&#xff0c;旨在以较低的计算资源实现高效的图像分类和其他计算机视觉任务。 特点与…
阅读更多...
Springboot系列之：创建Springboot项目，Springboot整合MyBatis-plus

Springboot系列之：创建Springboot项目，Springboot整合MyBatis-plus

Springboot系列之&#xff1a;创建Springboot项目&#xff0c;Springboot整合MyBatis-plus 一、快速创建Spring boot项目二、项目完整目录三、pom.xml四、application.yaml五、实体类六、mapper七、IService接口八、Service实现类九、配置类十、枚举十一、增删改查测试类十二、…
阅读更多...
C++：用红黑树封装map与set-1

C++：用红黑树封装map与set-1

文章目录 前言一、STL源码分析二、红黑树的构建三、map与set整体框架的搭建与解析四、如何取出进行比较&#xff1f;1. met与set的数据是不同的2. 取出数据进行比较1&#xff09;问题发现2&#xff09;仿函数解决 五、封装插入六、迭代器的实现1. operator* 与operator->2. …
阅读更多...
Perforce《2024游戏技术现状报告》Part3：生成式AI、版本控制、CI/CD等游戏技术的未来趋势与应用

Perforce《2024游戏技术现状报告》Part3：生成式AI、版本控制、CI/CD等游戏技术的未来趋势与应用

游戏开发者一直处于创新前沿。他们的实践、工具和技术受到各行各业的广泛关注&#xff0c;正在改变着组织进行数字创作的方式。 近期&#xff0c;Perforce发布了《2024游戏技术现状报告》&#xff0c;通过收集来自游戏、媒体与娱乐、汽车和制造业等高增长行业的从业者、管理人…
阅读更多...
4-SpringCloud整合服务间的调用即负载均衡

4-SpringCloud整合服务间的调用即负载均衡

springcloud目录&#xff1a; 1.Spring Cloud简介 2.SpringCloud整合eureka注册中心 3.SpringCloud整合服务注册 4.SpringCloud整合服务间的调用即负载均衡 5.SpringCloud整合Feign调用 6.SpringCloud整合config配置中心 7.SpringCloud整合zuul路由网关 我们复制一个yqx-user服…
阅读更多...
Elasticsearch客户端在和集群连接时，如何选择特定的节点执行请求的？

Elasticsearch客户端在和集群连接时，如何选择特定的节点执行请求的？

大家好&#xff0c;我是锋哥。今天分享关于【Elasticsearch客户端在和集群连接时&#xff0c;如何选择特定的节点执行请求的&#xff1f;】面试题。希望对大家有帮助&#xff1b; Elasticsearch客户端在和集群连接时&#xff0c;如何选择特定的节点执行请求的&#xff1f; 100…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023