【数据结构】树和二叉树

简介: 【数据结构】树和二叉树

前言

回顾一下前面几期,我们学习了数据结构中的顺序表单链表双向链表队列,它们有个共同的特点:都是线性的数据结构。而接下来,我们要学习一种非线性的数据结构---->二叉树

一、树概念及结构

1.1 树的概念

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

一颗树具有以下几个特点:

  • 每颗树有一个唯一的特殊节点,称作根结点,根节点没有前驱结点,上面的A就是根结点。
  • 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱结点,可以有0个或多个后继结点。
  • 由此可见,树可以看作"根节点"+n个子树组成,而每个子树又可以看作"根节点"+n个子树组成。即树是递归定义的。

1.2 树的相关概念

术语 解释
节点的度 一个节点含有的子树的个数称为节点的度。例如:A有6颗子树,A节点的度为6。
叶子节点/终端节点 度为0的节点称为叶子节点。例如:B、C、H、I…为叶子节点
分支节点/非终端节点 度不为0的节点称为分支节点。例如:D、E、F、G…为分支节点
父节点/双亲结点 如果一个节点含有子节点,则这个节点称为其子节点的父节点。例如:A是B的父节点
子节点/孩子节点 一个节点含有的子树的根节点称为该节点的子节点。例如:B是A的孩子节点
兄弟节点 具有相同父节点的节点互称为兄弟节点。例如:B、C是兄弟节点;H、I不是兄弟节点,它们的父节点不同
树的度 一棵树中,最大的节点的度称为树的度; 如上图:树的度为6
节点的层次 从根开始定义起,根为第1层,根的子节点为第2层,以此类推(特别说明:也有地方将根作为第0层)
树的高度/深度 树中节点的最大层次; 如上图:树的高度为4(根为第1层)
堂兄弟节点 双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点
节点的祖先 从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先、H的祖先有D、A
子孙 以某节点为根的子树中任一节点都称为该节点的子孙;如上图:所有节点都是A的子孙、J的子孙有P、Q
森林 由m(m>0)棵互不相交的树的集合称为森林;

1.3 数的表示

树是一种非线性结构,相对于线性表,树要存储表示起来就比较复杂了。不仅要保存当前结点的值,也要保存结点和结点之间的关系(亲缘关系)。实际中树有很多种表示方式,例如:双亲表示法(结点的指针指向双亲),孩子表示法(结点的指针指向孩子)、孩子双亲表示法(二者混合)以及孩子兄弟表示法(下面介绍)等。我们这里就简单的了解其中最常用的孩子兄弟表示法。以下是孩子兄弟表示法的结构体和图例:

//孩子兄弟表示法
typedef int TDataType;
struct Node
{
    struct Node* Child; // 第一个孩子结点
    struct Node* Brother; // 指向其下一个兄弟结点
    TDataType data; // 结点中的数据域
};

其中Child指针域指向第一个孩子结点,Brother指针域指向其下一个兄弟结点。通过这种方式,我们不仅可以有效解决孩子表示法中孩子指针的个数无法合理控制的问题,还能很好地表示出每个结点之间的关系。

  1. 已知B结点,需要找到F结点:只需通过B结点的Child指针找到D,然后再通过D的Brother指针找到E,最后通过E的Brother指针找到F即可。
  2. 已知A结点,需要知道G结点的信息:通过A结点的Child指针找到C,然后再通过B的Brother指针找到C,最后通过C的Child指针找到G即可。

1.4 树在实际中的应用


二、二叉树概念及结构

2.1 二叉树的概念

我们规定二叉树就是一颗度不大于2的树。我们上面说到树是由根结点和多颗子树构成的,二叉树就是由根结点和别名为左子树、右子树的两颗树组成。下面就是一颗二叉树:

从上图我们可以看出:

  1. 二叉树不存在度大于2的结点
  2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

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

2.2 特殊的二叉树

  1. 满二叉树

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

  1. 完全二叉树

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

2.3 二叉树的性质

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

2、若规定根结点的层数为1,则一颗深度为h(h>=1)的二叉树最多有2^h-1个结点(满二叉树)。

3、对于任何一颗二叉树,如果度为0的结点有n0个,度为2的结点有n2个,则有n0=n2+1。

4、若规定根结点的层数为1,则具有n个结点的满二叉树的深度h=log2(n+1)。

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

  1. 若i>0,则i位置节点的双亲序号为(i-1)/2(表示向下取整)
  2. 若i=0,则i为根节点编号,无双亲节点
  3. 若2i+1<n,则左孩子序号为2i+1,否则无左孩子
  4. 若2i+2<n,则右孩子序号为2i+2,否则无右孩子

2.4 二叉树的存储结构

二叉树的存储结构一般分为两种:顺序存储和链式存储。

1.顺序存储

顺序结构存储就是使用数组来存储,利用下标表示结点之间的关系(性质5)。一般使用数组只适合表示完全二叉树,因为不是完全二叉树则会造成空间浪费。而现实中使用中只有堆(一种完全二叉树)才会使用数组来存储,关于堆我们放到后面的篇章专门讲解。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。如下:

2.链式存储

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用指针来指示每个结点的逻辑关系。链式结构又分为二叉链和三叉链。二叉链就是除了数据域,链表中还有两个指针域,分别用来指向该结点的左孩子和右孩子的存储地址,目前我们用到的基本都是二叉链。而所谓三叉链就是在二叉链的基础上再增加一个指针域指向该结点的父亲结点的存储地址,一些更复杂的数据结构如红黑树将会用到三叉链。 图示如下:

本次的内容到这里就结束啦。希望大家阅读完可以有所收获,同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言,小羊一定认真修改,写出更好的文章~~

目录
打赏
0
0
0
0
0
分享
相关文章
|
3月前
|
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。
79 0
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
62 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
49 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
47 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
53 2
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
100 5
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
131 4
|
3月前
|
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
219 8
|
3月前
|
数据结构之文件系统模拟(树数据结构)
本文介绍了文件系统模拟及其核心概念,包括树状数据结构、节点结构、文件系统类和相关操作。通过构建虚拟环境,模拟文件的创建、删除、移动、搜索等操作,展示了文件系统的基本功能和性能。代码示例演示了这些操作的具体实现,包括文件和目录的创建、移动和删除。文章还讨论了该算法的优势和局限性,如灵活性高但节点移除效率低等问题。
93 0

热门文章

最新文章