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

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

树概念及结构

含义:树是一种非线性的数据结构,它是由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,则它就是满二叉树。

5d747a839591db415606b677e2da244b_dc5945c6e3e346efa94ed7a37e3aa0ce.png


完全二叉树

完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为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就是左(右)子节点下标

下面树顺序结构存储

2.链式存储

链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是:

链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链

堆的概念及结构

堆可以使用数组来实现,因为它是一种完全二叉树。在数组中,父节点和子节点的关系可以通过下标计算得出。

简单理解就是,堆一般是一种完全二叉树,以数组的形式进行存储,

堆有大小堆之分


搜索二叉树

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


  • 对于任意节点,其左子树中的所有节点的值都小于该节点的值。
  • 对于任意节点,其右子树中的所有节点的值都大于该节点的值。
  • 左右子树也都是搜索二叉树。

这里简单的介绍,后面再细讲, 下面我们回归堆

小堆:

小堆要求:任意一个父亲 <= 孩子


大堆

大堆要求: 任意一个父亲 >= 孩子

目录
打赏
0
0
0
0
12
分享
相关文章
|
3月前
|
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。
81 0
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
64 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
51 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
50 10
【C++数据结构——线性表】求集合的并、交和差运算(头歌实践教学平台习题)【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括: 1. **单链表表示集合**:使用单链表存储集合元素,确保元素唯一且无序。 2. **求并集**:遍历两个集合,将所有不同元素加入新链表。 3. **求交集**:遍历集合A,检查元素是否在集合B中存在,若存在则加入结果链表。 4. **求差集**:遍历集合A,检查元素是否不在集合B中,若满足条件则加入结果链表。 通过C++代码实现上述操作,并提供测试用例验证结果。测试输入为两个集合的元素,输出为有序集合A、B,以及它们的并集、交集和差集。 示例测试输入: ``` a c e f a b d e h i ``` 预期输出:
50 7
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
49 5
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
50 5
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
54 2
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
103 5
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
162 16
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等