数据结构第五课 -----线性表之树

2023-12-14 11:52

本文主要是介绍数据结构第五课 -----线性表之树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者前言

🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂
​🎂 作者介绍: 🎂🎂
🎂 🎉🎉🎉🎉🎉🎉🎉 🎂
🎂作者id:老秦包你会, 🎂
简单介绍:🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂
喜欢学习C语言和python等编程语言,是一位爱分享的博主,有兴趣的小可爱可以来互讨 🎂🎂🎂🎂🎂🎂🎂🎂
🎂个人主页::小小页面🎂
🎂gitee页面:秦大大🎂
🎂🎂🎂🎂🎂🎂🎂🎂
🎂 一个爱分享的小博主 欢迎小可爱们前来借鉴🎂


二叉树

  • **作者前言**
  • 小知识的插入
  • 树概念及结构
  • 树的相关
  • 树的结构体类型
    • 指针数组法
    • 左孩子右兄弟
  • 二叉树
  • 特殊的二叉树
    • 满二叉树
    • 完全二叉树
    • 二叉树的存储结构
    • 堆的概念及结构

小知识的插入

  • 前面我们所学习的链表、顺序表、栈、队列都是逻辑结构描述的,其中顺序表是逻辑和物理结构是连续的

树概念及结构

含义:树是一种非线性的数据结构,它是由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)棵互不相交的树的集合称为森林;

简单的说就是一颗树可以拆成多个子树,子树之间不能相交,每个节点有且仅有一个父节点,有N个节点就会有N-1条边,每个节点有多少个度,就会有多少个子树

树的结构体类型

指针数组法

struct TreeNode
{int val;struct TreeNode* chailArr[N]; //指针数组,每个节点的度最大是6//这样会造成很多空间浪费
};

左孩子右兄弟

//左孩子右兄弟
struct TreeNode
{int val;struct TreeNode* leftchild;struct TreeNode* rigthbrother;
};

在这里插入图片描述

二叉树

二叉树是一种特殊的树结构,其中每个节点最多有两个子节点,分别称为左子节点右子节点。二叉树可以为空,也可以只有一个根节点
二叉树具有一些特殊的性质,例如:

  1. 每个节点最多有两个子节点,分别为左子节点和右子节点。
  2. 左子树和右子树也是二叉树,它们的结构与父节点类似。
  3. 二叉树可以是空的,即没有任何节点。
  4. 二叉树可以是斜的,即所有节点都只有左子节点或只有右子节点。

在这里插入图片描述

可以简单的理解,二叉树的度不超过2

对于任意的二叉树都是由以下几种情况复合而成的
在这里插入图片描述

特殊的二叉树

满二叉树

满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是 2^k -1,则它就是满二叉树。
在这里插入图片描述

完全二叉树

完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K
的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
简单的理解就是 完全二叉树有k层,前k-1层是全满的,第k层的节点数的范围是[1, 2^(k-1)], 并且从左到右必须连续
在这里插入图片描述

二叉树的存储结构

在这里插入图片描述

  1. 顺序存储(适合于满二叉树(或者完全二叉树))
    可以看出左子节点都是奇数, 右子节点都是偶然
    这样存储有一个规律
    父节点下标为parent
    左子节点: leftchild = parent2 +1
    右子节点:rigthchild = parent
    2 +2

还要一条万能公式
parent = (child -1) /2; child就是左(右)子节点下标
下面树顺序结构存储
在这里插入图片描述
在这里插入图片描述

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

堆的概念及结构

堆可以使用数组来实现,因为它是一种完全二叉树。在数组中,父节点和子节点的关系可以通过下标计算得出。
简单理解就是,堆一般是一种完全二叉树,以数组的形式进行存储,
堆有大小堆之分

搜索二叉树
搜索二叉树(Binary Search Tree,BST)是一种特殊的二叉树结构,具有以下性质:

  • 对于任意节点,其左子树中的所有节点的值都小于该节点的值。
  • 对于任意节点,其右子树中的所有节点的值都大于该节点的值。
  • 左右子树也都是搜索二叉树。
    这里简单的介绍,后面再细讲, 下面我们回归堆
    小堆:
    小堆要求:任意一个父亲 <= 孩子
    在这里插入图片描述
    大堆
    大堆要求: 任意一个父亲 >= 孩子
    在这里插入图片描述

这篇关于数据结构第五课 -----线性表之树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/492419

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据,每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明: 1. 列表 (List) 列表是一种可变的有序集合,可以存放任意类型的数据。列表中的元素可以通过索

浙大数据结构:04-树7 二叉搜索树的操作集

这道题答案都在PPT上,所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现,小就进左子树,大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客,我们学习了排序算法中的插入排序和选择排序,接下来我们将继续探索交换排序与归并排序,这两个排序都是重头戏,让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换,让较大的元素逐渐向右移动,从而将最大的元素移动到最右边。 动画演示: 1.1.2 具体步

数据结构:线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表,允许插入的一端叫做队尾(rear),允许删除的一端叫做队首(front)。 队列具有FIFO的性质 队列的存储表示也有两种方式:基于数组的,基于列表的。基于数组的叫做顺序队列,基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示:只提供了接口和显式的默认构造函数和析构函数,在派生类中调用。 #i