数据结构:树

简介: 数据结构:树

一. 树的基本概念


1.1 树的定义


树是N(N>=0)个节点的有限集合。N=0时为空树,N>0时应满足:


有且仅有一个特定的称为根的节点


N>1时,其余节点可分为m(m>0)个互不相交的有限集合。其中,每一个有限集合自身又是一棵树


1.2 树的相关概念


1. 根节点:非空树处于最上层的唯一节点,其余节点都是它的子孙后代


2. 节点的度:节点具有的孩子节点个数


3. 叶子节点:度为0的节点


4. 父子节点:直接相连的一对节点,处于上层的是父节点,处于下层的是子节点


5. 兄弟节点:由同一个父节点生出的不同节点互称兄弟节点


9d520266c93492907655bfe1226a8324_899b354e63e747728eb122e723d2d63f.png


6.节点层次:由根开始记为1层,其子节点为2层,孙子节点为3层……


7.节点深度:节点所在的层次数


8.树的深度/高度:树的最大层次数


9.节点高度:以节点为根的子树的深度/高度


10. 有序树:以兄弟节点为根的子树交换位置得到的新树视作与原来的树不同的树


11. 无序树:以兄弟节点为根的子树交换位置得到的新树视作与原来的树相同的树


76661fbb2156ae20d88f71e4c480de02_cd71dcbb172e472a8be09f7c959438a7.png


1.3 二叉树


1.定义:二叉树是一种每个节点度都不大于2的树。其中,每个节点的子节点有左右之分且左右

子节点所在的子树不可以交换位置,即二叉树是一棵有序树。


c09ef4b9d308164930949f5f7057ace2_d3622741ebde476392935594431432c6.png


2. 特殊的二叉树


(1)满二叉树:所有叶子节点全部在最底层,且所有非叶子节点度都是2的树。


4ccac992ef73d7b1ed2ff9d5c3170f2e_4a55fe39280e4ddf918e81b62aa68cb4.png


记满二叉树T的高度为h,节点总数为n,则,第k层的节点总数是。


从1开始,对T从上到下,从左到右进行编号。如果编号i的节点有父节点,则其父节点的编号为i/2,如果有左字节点,则其左字节的的编号为2*i,如果有右子节点,则其右子节点的编号为2*i+1。


(2)完全二叉树:记二叉树高度为h。从1开始,对二叉树从上到下,从左到右进行编号。对高度

同为h的满二叉树做同样的编号处理。如果二叉树中所有节点的编号都能与满二叉树中同样位置的节点编号一致,则该二叉树是一棵完全二叉树。


d134c57e7c21b828db86bfba797ec12a_49502e04a26a4f9d836d91467f4877d5.png


  • 完全二叉树的叶子节点只可能存在于最下面的两层中,且最下层的叶子节点全部是靠左紧密排列的。
  • 完全二叉树中父子节点之间的编号规律与满二叉树的规律完全相同,且编号大于[n/2]的节点必是叶子节点。
  • 如果n为奇数,则每个非叶子节点都有两个子节点;如果n为偶数,则第n/2个节点必为非叶子节点,且它只有左子节点而无右子节点,其余非叶子节点都有两个子节点。


(3)二叉搜索树(BST):二叉搜索树要么是空树,要么同时满足以下条件:

1. 左子树所有节点的关键字均小于根节点的关键字

2. 右子树所有节点的关键字均大于根节点的关键字

3. 左右子树也均为二叉搜索树


8c7efae281058f13d6e110ff81333f1d_5ba2b91940fb4c6592590db03f80d12f.png


(4)平衡二叉树(AVL):如果二叉树中每个节点的左右子树高度差都不大于1,则这棵二叉树就

是平衡二叉树 。


485019459212e8a2d3fa3b41f9f7a60d_35c7b3a3bf254981bf6f6af049b33560.png


平衡二叉树经典的应用场景就是与二叉搜索树结合,形成平衡二叉搜索树。在构建二叉搜索树

的同时借助调整策略使每个节点的左右子树高度差都不大于1,保证二叉搜素树中每个节点的

左右子树都规模相当,整个树看起来更加“匀称”。


二、树的基本操作


2.1 树的存储结构


2.1.1 顺序存储结构


image.png


2.2.2 链式存储结构


ddba718b6980b331a9fbf1aada0ae469_f834fd30ebcb4b1c9566e3ae11f915df.png


2.2 树的增删查改


2.2.1 查找/搜索/遍历是树的核心操作


image.png


遍历:按照某种规则“访问”树中的每个节点,保证每个节点都会被“访问”到且每个节点只

会被“访问”一次

“访问”:程序与节点产生交互或者在节点进行某些操作

“进入”:程序来到了某个节点,并未与该节点产生任何交互

不同规则下,对同一个节点的“进入”次数可能有一次也可能有多次,但对同一个节点的“访

问”只会发生一次


2.2.2 二叉树的深度优先搜索(DFS)


二叉树的深度优先搜索,在“进入”节点时有以下约定俗成的要求:


(1)必须以根节点为搜索起始节点并“进入”


(2)优先“进入”当前节点的左子节点,其次“进入”当前节点的右子节点


(3)如果当前节点为空节点或者左右子节点都被“进入”过,则再次“进入”父节点


da5559ed30877121aad65f81505237b3_22b0650d77174385905cb8d86bd30c84.png


根节点第一次“进入”时,其余节点均未被“进入”;第二次“进入”时,左子树节点全部完成三次“进入”;第三次“进入”时,右子树节点全部完成三次“进入”。


“进入”序列:1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 1, 3, 3, 6, 6, 6, 3, 1


  • 将打印操作视为一次“访问”,第一次“进入”后“访问”:1, 2, 4, 5, 3, 6;先“访问”根,再“访问”左子树,最后“访问”右子树,即先序遍历
  • 将打印操作视为一次“访问”,第二次“进入”后“访问”:4, 2, 5, 1, 3, 6;先“访问”左子树,再“访问”根,最后“访问”右子树,即中序遍历
  • 将打印操作视为一次“访问”,第三次“进入”后“访问”:4, 5, 2, 6, 3, 1;先“访问”左子树,再“访问”右子树,最后“访问”根,即后序遍历


2.2.3 二叉树的广度优先搜索(BFS)


从根节点开始,按层次从上到下,同层次内从左到右“访问”每一个节点,也叫做层次遍历,每个节点只会“进入”一次。


42a221db86e423ba2d95f285a872d7da_2265ecf28cfe4695a17a2c5528544a80.png


要实现二叉树的广度优先搜索,需要借助一个特殊的数据结构——队列


ae6ccbacc33420a3b75abf24715706a8_61c64356ee1b4c70afa8a162a75affb4.png


实现二叉树层次遍历的流程:

1. 初始化空队,将根节点入队

2. 当队列非空且队头元素非空时不断重复以下操作:

(1)队头节点出队并设置为当前节点

(2)对当前节点进行“访问”

(3)如果当前节点左子节点存在则将左子节点入队

(4)如果当前节点右子节点存在则将右子节点入队


目录
相关文章
|
10月前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。
249 0
|
6月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
141 3
 算法系列之数据结构-Huffman树
|
6月前
|
存储 自然语言处理 数据库
【数据结构进阶】AVL树深度剖析 + 实现(附源码)
在深入探讨了AVL树的原理和实现后,我们不难发现,这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题,还通过其独特的平衡机制,确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
456 19
|
8月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
185 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
8月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
173 12
|
8月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
159 10
|
8月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
240 3
|
11月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
301 64
|
10月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
253 5
|
10月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
368 16