【数据结构】非线性结构---二叉树

news/2024/6/16 11:32:24/文章来源:https://blog.csdn.net/qq_72952716/article/details/137055646

1、树

1.1 树的相关概念

节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6

叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点

非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等节点为分支节点

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点

兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点

树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度或深度:树中节点的最大层次; 如上图:树的高度为4

堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点

节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙

森林:由m(m>0)棵互不相交的树的集合称为森林;

1.2 树的表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间 的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。其中最常用的是孩子兄弟表示法。

 typedef int DataType;struct Node{struct Node* _firstChild1;  // 第一个孩子结点  struct Node* _pNextBrother; // 指向其下一个兄弟结点  DataType _data;  // 结点中的数据域            };

2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合,该集合:

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

 2.2特殊的二叉树

 1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是 说,如果一个二叉树的层数为K,且结点总数是,则它就是满二叉树。

满二叉树:每一层都是满的,结点个数为2^h-1

2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K 的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

完全二叉树:前n-1层都是满的,最后一层可以不满,但是从左到右是连续的,结点范围[2^(h-1), 2^h-1]

2.3 二叉树的性质

1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有 个结点2^(i-1).

2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h-1.

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0 , 度为2的分支结点个数为n0=n2+1.

4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h= ,则有= . (ps: +1 是log以2 为底,n+1为对数)

5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对 于序号为i的结点有: 

        1. 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点

        2. 若2i+1=n否则无左孩子

        3. 若2i+2=n否则无右孩子

3.二叉树的顺序结构及实现

3.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。

3.2 堆的概念及结构

一个集合所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,堆中某个节点的值总是小于或等于其父节点的值是大堆,堆中某个节点的值总是大于或等于其父节点的值是小堆。

3.3 堆的实现

#include "Heap.h"void HPInit(HP* php)
{assert(php);php->a = (Datatype*)malloc(sizeof(Datatype) * 4);if (php->a == NULL){perror("malloc fail");return;}php->size = 0;php->capacity = 4;
}void HPInitArray(HP* php, int* a, int n)
{assert(php);php->a = (Datatype*)malloc(sizeof(Datatype) * n);if (php->a == NULL){perror("malloc fail");return;}php->size = n;php->capacity = n;for (int i = (n - 1 - 1) / 2; i >= 0; i++){AdjustDown(php->a, php->size, i);}
}void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}void Swap(Datatype* p1, Datatype* p2)
{Datatype tmp = p1;*p1 = *p2;*p2 = tmp;
}//除了child,前面的数据都构成堆
void AdjustUp(Datatype* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent])// 大堆{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//左右子树都构成大堆或小堆
void AdjustDown(Datatype* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child])//大堆{++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void HPPush(HP* php, Datatype x) 
{assert(php);if (php->size == php->capacity){Datatype* tmp = (Datatype*)realloc(php->a, sizeof(Datatype)*php->capacity*2);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}void HPPop(HP* php)
{assert(php);assert(!PHEmpty(php));//和最后一个数据交换Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size - 1, 0);}Datatype HPTop(HP* php)
{assert(php);return php->a[0];
}bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}int HPSize(HP* php)
{assert(php);return php->size;
}//堆排序--升序--建大堆
void HPSort(int* a, int n) 
{建堆--向上调整--O(NlogN)//for (int i = 1; i < n; i++)//{//	AdjustUp(a, i);//}//建堆--向下调整--O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//实现排序--O(NlogN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

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

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

相关文章

51单片机学习笔记14 LCD1602显示屏使用

51单片机学习笔记14 LCD1602显示屏使用 一、LCD1602介绍1. 简介2. 引脚定义3. DDRAM4. 字模5. 指令&#xff08;1&#xff09;清屏指令 0x01&#xff08;2&#xff09;光标归位指令 0x02&#xff08;3&#xff09;进入模式设置指令 0x06&#xff08;4&#xff09;显示开关控制指…

JavaScript中什么叫深拷贝?

在 JavaScript 中&#xff0c;深拷贝指的是创建一个新的对象&#xff0c;这个新的对象与原始对象完全独立&#xff0c;没有任何共享的属性或者数据&#xff0c;它们不共享同一块内存地址。深拷贝会复制原始对象的所有属性和嵌套对象的所有属性&#xff0c;包括嵌套对象中的属性…

Ts递归查找多个根节点树结构某一条数据

// 递归查找树结构数据 function getIsNode(nodes: any, code: string) {let found false;function search(nodes: any) {nodes.forEach((node: any) > {if (node.code code) { //code相等&#xff0c;视为找到&#xff0c;将found设置为truefound true;}// 否则查找子节…

数据结构进阶篇 之【选择排序】详细讲解(选择排序,堆排序)

民以食为天&#xff0c;我以乐为先 嘴上来的嘘寒问暖&#xff0c;不如直接打笔巨款 一、选择排序 1.直接选择排序 SelectSort 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 直接选择排序的特性总结 2.堆排序 HeapSort 跳转链接&#xff1a;数据结构 之 堆的应用 二、完…

OpenHarmony实战开发-如何通过Stage模型实现一个简单的游戏卡片

介绍 本示例展示了如何通过Stage模型实现一个简单的游戏卡片。 通过卡片支持的点击事件进行交互&#xff0c;让用户通过点击的先后顺序把一个乱序的成语排列成正确的成语。使用了C和TS的混合编程方式&#xff0c;将获取随机数的能力下沉到C实现&#xff0c;并通过NAPI的能力将…

牛客NC153 信封嵌套问题【中等 动态规划,最长递增子序列 Java,Go,PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/9bf77b5b018d4d24951c9a7edb40408f 相同的题目&#xff1a; https://www.lintcode.com/problem/602 思路 本质是求最长子序列问题envelopes 先按 w 升序排序&#xff0c;再按 h 降序 排序&#xff0c;只需考虑h…

基于深度学习的机场航拍小目标检测系统(网页版+YOLOv8/v7/v6/v5代码+训练数据集)

摘要&#xff1a;在本博客中介绍了基于YOLOv8/v7/v6/v5的机场航拍小目标检测系统。该系统的核心技术是采用YOLOv8&#xff0c;并整合了YOLOv7、YOLOv6、YOLOv5算法&#xff0c;从而进行性能指标的综合对比。我们详细介绍了国内外在机场航拍小目标检测领域的研究现状、数据集处理…

Nginx三大常用功能“反向代理,负载均衡,动静分离”

注意&#xff1a;以下案例在Windows系统计算机作为宿主机&#xff0c;Linux CentOS 作为虚拟机的环境中实现 一&#xff0c;Nginx配置实例-反向代理 1.反向代理 案例一 实现效果&#xff1a;使用nginx反向代理&#xff0c;访问 www.123.com 直接跳转到127.0.0.1:8080 准备工…

vue3源码解析——ref和reactive定义响应式的区别

ref 和 reactive 是 Vue 3.0 中用于定义响应式数据的两个新 API。它们有以下区别&#xff1a; ref 定义单个响应式数据 数据类型可以是任意类型。它通常用于定义原始数据类型为响应式数据。返回一个响应式对象&#xff0c;该对象包含一个 .value 属性&#xff0c;可用于获取和设…

Golang Gin框架

1、这篇文章我们简要讨论一些Gin框架 主要是给大家一个基本概念 1、Gin主要是分为路由和中间件部分。 Gin底层使用的是net/http的逻辑&#xff0c;net/http主要是说&#xff0c;当来一个网络请求时&#xff0c;go func开启另一个协程去处理后续(类似epoll)。 然后主协程持续…

网络安全 | 什么是DDoS攻击?

关注WX&#xff1a;CodingTechWork DDoS-介绍 DoS&#xff1a;Denial of Service&#xff0c;拒绝服务。DDoS是通过大规模的网络流量使得正常流量不能访问受害者目标&#xff0c;是一种压垮性的网络攻击&#xff0c;而不是一种入侵手段。NTP网络时间协议&#xff0c;设备需要…

DSP实时计算平台设计方案:912-基于6U CPCIe的双路光纤图像DSP实时计算平台

基于6U CPCIe的双路光纤图像DSP实时计算平台 一、设备概述 设备基于6U CPCIe架构&#xff0c;通过背板交换实现4片信号处理板卡的互联传输&#xff0c;每个信号处理板卡支持双TMS320C6678&#xff0c;支持2路光纤的图像处理&#xff0c;实现FPGA的预处理和备份工…

Java基础知识总结(第八篇):集合:Collection(List、Set)、Map、Collections 工具类

声明: 1. 本文根据韩顺平老师教学视频自行整理&#xff0c;以便记忆 2. 若有错误不当之处, 请指出 系列文章目录 Java基础知识总结&#xff08;第一篇&#xff09;&#xff1a;基础语法 Java基础知识总结&#xff08;第二篇&#xff09;&#x…

159 Linux C++ 通讯架构实战14,epoll 函数代码实战

ngx_epoll_init函数的调用 //&#xff08;3.2&#xff09;ngx_epoll_init函数的调用&#xff08;要在子进程中执行&#xff09; //四章&#xff0c;四节 project1.cpp&#xff1a;nginx中创建worker子进程&#xff1b; //nginx中创建worker子进程 //官方nginx ,一个…

HarmonyOS 应用开发之页面和自定义组件生命周期

在开始之前&#xff0c;我们先明确自定义组件和页面的关系&#xff1a; 自定义组件&#xff1a;Component装饰的UI单元&#xff0c;可以组合多个系统组件实现UI的复用&#xff0c;可以调用组件的生命周期。 页面&#xff1a;即应用的UI页面。可以由一个或者多个自定义组件组成…

Topaz Video AI for Mac v5.0.0激活版 视频画质增强软件

Topaz Video AI for Mac是一款功能强大的视频处理软件&#xff0c;专为Mac用户设计&#xff0c;旨在通过人工智能技术为视频编辑和增强提供卓越的功能。这款软件利用先进的算法和深度学习技术&#xff0c;能够自动识别和分析视频中的各个元素&#xff0c;并进行智能修复和增强&…

区块链web3智能合约开发学习-开发工具Remix(1)

学习区块链中常用语言solidity时&#xff0c;我们会用到特别的开发工具&#xff0c;对于学习前期&#xff0c;建议是将代码写到Remix IDE中进行编译部署和测试&#xff0c;这就是我们编写和交互智能合约的地方&#xff0c; 在线remix编译器&#xff1a; https://remix.ethereu…

腾讯云(CVM)托管进行权限维持

前言 刚好看到一个师傅分享了一个阿里云ECS实战攻防&#xff0c;然后想到了同样利用腾讯云CVM的托管亦可实现在实战攻防中的权限维持。 简介 腾讯云自动化助手&#xff08;TencentCloud Automation Tools&#xff0c;TAT&#xff09;是一个原生运维部署工具&#xff0c;它可…

单片机中的RAM vs ROM

其实&#xff0c;单片机就是个小计算机。大计算机少不了的数据存储系统&#xff0c;单片机一样有&#xff0c;而且往往和CPU集成在一起&#xff0c;显得更加小巧灵活。 直到90年代初&#xff0c;国内容易得到的单片机是8031&#xff1a;不带存储器的芯片&#xff0c;要想工作&a…

基于SpringBoot的“校园志愿者管理系统”的设计与实现(源码+数据库+文档+PPT)

基于SpringBoot的“校园志愿者管理系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统总体结构图 系统首页界面图 志愿者注册…