数据结构--树和二叉树

树和二叉树

    • 1.树概念及结构
      • 树的概念
      • 树的相关概念
      • 树的表示
    • 2.二叉树概念及结构
      • 概念
      • 特殊的二叉树
      • 二叉树的性质
    • 3.二叉树顺序结构及实现
    • 4.二叉树链式结构及实现
      • 二叉树的顺序结构
      • 二叉树的前,中,后序遍历
      • 层序遍历

1.树概念及结构

树的概念

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因
为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

在这里插入图片描述

  • 有一个特殊的结点,称为根结点,根节点没有前驱结点
  • 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继。
  • 因此,树是递归定义的。

注意:树形结构中,子树之间不能有交集,否则就不是树形结构

树的相关概念

在这里插入图片描述

节点的度:一个节点含有的子树的个数称为该节点的度; 如上图: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)棵互不相交的树的集合称为森林

树的表示

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

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

在这里插入图片描述

2.二叉树概念及结构

概念

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

  1. 或者为空
  2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
    在这里插入图片描述

从上图可以看出:

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

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

注意:对于任意的二叉树都是由以下几种情况复合而成的:

在这里插入图片描述

特殊的二叉树

  1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是 2^k - 1,则它就是满二叉树。
  2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K
    的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

在这里插入图片描述

二叉树的性质

  1. 若规定根节点的层数为1,则一棵非空二叉树的**第i层上最多有 2^(i-1)**个结点.
  2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h - 1
  3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n0 ,则有 n0= n2+1
  4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log2(n+1)(ps:log2(n+1) 是log以2为底,n+1为对数)
  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
    1. 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点
    2. 若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
    3. 若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子

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

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。

  1. 顺序存储
    顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

在这里插入图片描述

  1. 链式存储
    二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

在这里插入图片描述

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}

4.二叉树链式结构及实现

二叉树的顺序结构

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

二叉树的前,中,后序遍历

要实现前,中,后序遍历,我们需要再来理解二叉树的结构。把任一一棵二叉树分为三部分:根节点,左子树,右子树。
在这里插入图片描述
二叉树的前序(先根)遍历:根,左子树,右子树。
对应上图为:A B D NULL NULL E NULL NULL C NULL NULL。

二叉树的中序(中根)遍历:左子树,根,右子树。
对应上图为:NULL D NULL B NULL E NULL A NULL C NULL。

二叉树的后序(后根)遍历:左子树,右子树,根。
对应上图为:NULL NULL D NULL NULL E B NULL NULL C A。

层序遍历

层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

在这里插入图片描述

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

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

相关文章

我做的小程序,一下流量就爆了【小游戏:你对颜色敏感吗】

大家好&#xff0c;我是鬼哥&#xff0c;一位8年前端从业者&#xff0c;也是一位全栈开发&独立开发者&#xff0c; 最近有点浮躁&#xff0c;可笑的是2024年已经过去一个季度了&#xff0c;我今年的目标貌似都还没正式开始。 本来去年下半年计划今年开始&#xff0c;正式运…

Java集合——Map、Set和List总结

文章目录 一、Collection二、Map、Set、List的不同三、List1、ArrayList2、LinkedList 四、Map1、HashMap2、LinkedHashMap3、TreeMap 五、Set 一、Collection Collection 的常用方法 public boolean add(E e)&#xff1a;把给定的对象添加到当前集合中 。public void clear(…

线程池详解并使用Go语言实现 Pool

写在前面 在线程池中存在几个概念&#xff1a;核心线程数、最大线程数、任务队列。 核心线程数指的是线程池的基本大小&#xff1b;也就是指worker的数量最大线程数指的是&#xff0c;同一时刻线程池中线程的数量最大不能超过该值&#xff1b;实际上就是指task任务的数量。任务…

KK全域电商,全体系打造实操课,多平台打造电商逻辑体系

实操课详细指导分析流程 资深运营老师陪伴式答疑 课程下载&#xff1a;https://download.csdn.net/download/m0_66047725/89013409 更多资源下载&#xff1a;关注我。 课程内容&#xff1a; 1先导课(拍下请看).mp4 2为什么要做小..红营 .mp4 3小红营适合什么类目的产品,…

linux之文件系统、inode和动静态库制作和发布

一、背景 1.没有被打开的文件都在磁盘上 --- 磁盘级文件 2.对磁盘级别的文件&#xff0c;我们的侧重点 单个文件角度 -- 这个文件在哪里&#xff0c;有多大&#xff0c;其他属性是什么&#xff1f; 站在系统角度 -- 一共有多少文件&#xff1f;各自属性在哪里&#xff1f…

UI自动化框架搭建以及面试题详解(上)

UI自动化框架搭建以及面试题 UI自动化面试题框架面试题那你讲下如何搭建现成的框架公司里面的框架是你搭建的么请结合你的项目讲解一下你的框架是如何搭建的 PO模式什么是 PO 模式PO 模式的封装原则有哪些 DDT驱动模式什么的项目适合ddt ddt四种模式ddt处理各种类型数据 自动化…

软考--软件设计师(软件工程总结3)

目录 1.面向对象技术 2。面向对象分析 3.面向对象程序设计&#xff08;选用一种面向对象的程序语言&#xff09; 4.面向对象测试 5.UML ​编辑6.UML的图 ​编辑7.设计模式 1.面向对象技术 面向对象对象继承类消息通信 对象&#xff1a;是基本运行时的实体&#xff0c;包…

使用Android完成案例教学

目录 题目&#xff1a;完成在Android平台下2个玩家分别利用2个手机连接在同一局域网下通过滑动摇杆分别使红飞机和黄飞机移动的开发。&#xff08;全代码解析&#xff09; 题目&#xff1a;完成在Android平台下2个玩家分别利用2个手机连接在同一局域网下通过滑动摇杆分别使红飞…

Open CASCADE学习|旋转变换

物体在三维空间中的旋转变换操作通常可以通过三种不同的方式来表示&#xff1a;矩阵&#xff08;Matrix&#xff09;、欧拉角&#xff08;Euler Angles&#xff09;和四元数&#xff08;Quaternion&#xff09;。下面详细解释这三种表示方法。 矩阵&#xff08;Matrix&#xf…

【51单片机入门记录】RTC(实时时钟)-DS1302应用

目录 一、DS1302相关写函数 &#xff08;1&#xff09;Write&#xff3f;Ds1302 &#xff08;2&#xff09;Write&#xff3f;Ds1302&#xff3f;Byte 二、DS130相关数据操作流程及相关代码 &#xff08;1&#xff09;DS1302初始化数据操作流程及相关代码 (shijian[i]/10&…

【学习分享】小白写算法之插入排序篇

【学习分享】小白写算法之插入排序篇 前言一、什么是插入排序算法二、插入排序算法如何实现三、C语言实现算法四、复杂度计算五、算法稳定性六、小结 前言 要学好每个算法&#xff0c;我觉得需要先总结出规律&#xff0c;然后自己去推演一遍&#xff0c;加深记忆&#xff0c;否…

阿里云8核32G云服务器租用优惠价格表,包括腾讯云和京东云

8核32G云服务器租用优惠价格表&#xff0c;云服务器吧yunfuwuqiba.com整理阿里云8核32G服务器、腾讯云8核32G和京东云8C32G云主机配置报价&#xff0c;腾讯云和京东云是轻量应用服务器&#xff0c;阿里云是云服务器ECS&#xff1a; 阿里云8核32G服务器 阿里云8核32G服务器价格…

【记录】LangChain|llama 2速通版

官方教程非常长&#xff0c;我看了很认可&#xff0c;但是看完了之后呢就需要一些整理得当的笔记让我自己能更快地找到需求。所以有了这篇文章。【写给自己看的&#xff0c;里面半句废话的解释都没有&#xff0c;如果看不懂的话直接看官方教程再看我的】 我是不打算一开始就用…

Jenkins (四) - 搭建 Docker SonarQube

Jenkins (四) - 搭建 Docker SonarQube 拉取 SonarQube $ docker pull sonarqube拉取 postgres $ $ docker pull postgres运行 postgres $ docker run -itd \ -e TZAsia/Shanghai -e POSTGRES_USERtester \ -e POSTGRES_PASSWORD123456 \ -p 5432:5432 \ -v /home/tester/d…

京东云服务器4核8G主机租用价格418元一年,1899元3年

京东云轻量云主机4核8G服务器租用价格418元一年&#xff0c;1899元3年&#xff0c;配置为&#xff1a;轻量云主机4C8G-180G SSD系统盘-5M带宽-500G月流量&#xff0c;京东云主机优惠活动 yunfuwuqiba.com/go/jd 可以查看京东云服务器详细配置和精准报价单&#xff0c;活动打开如…

【mac操作】brew指令集

brew指令集记录 1. brew search 【软件名称】2. rm -rf $(brew --cache)3. brew install 【软件名】4. brew uninstall 【软件名】5. 未完待续&#xff0c;&#xff0c;&#xff0c;&#xff0c; 官网路径&#xff1a; Homebrew官网 最上面就来一个homebrew安装指令吧&#xf…

win10上一个详细的Django开发入门例子

1.Django概述 Django是一个开放源代码的Web应用框架&#xff0c;由Python写成。采用了MTV的框架模式&#xff0c;即模型M&#xff0c;视图V和模版T。 Django 框架的核心组件有&#xff1a; 用于创建模型的对象关系映射&#xff1b; 为最终用户设计较好的管理界面&#xff1b…

阿里云倚天云服务器详解_CPU采用倚天710处理器

阿里云倚天云服务器CPU采用倚天710处理器&#xff0c;租用倚天服务器c8y、g8y和r8y可以享受优惠价格&#xff0c;阿里云服务器网aliyunfuwuqi.com整理倚天云服务器详细介绍、倚天710处理器性能测评、CIPU架构优势、倚天服务器使用场景及生态支持&#xff1a; 阿里云倚天云服务…

c# wpf LiveCharts MVVM绑定 简单试验

1.概要 c# wpf LiveCharts MVVM绑定 简单试验 2.代码 <Window x:Class"WpfApp3.Window3"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://s…

gitea简单介绍

Gitea是一个轻量级的开源自托管Git服务&#xff0c;提供了类似GitHub的功能和界面。它是一个简单、易于安装和使用的Git代码托管解决方案&#xff0c;适用于个人、小型团队和企业。 Gitea的主要特点如下&#xff1a; 自托管&#xff1a;Gitea允许在自己的服务器上搭建和管理…