摘要：前言本章将正式开启数据结构中树部分的讲解，本章将介绍树的概念和结构，以及树的表示方法。树的概念树是一种非线性的数据结构，它是由个有限节点组成的一个具有层次关系的集合。叶子结点又称终端节点，度为的节点称为叶子结点。
本章将正式开启数据结构中 “树” 部分的讲解，本章将介绍树的概念和结构，以及树的表示方法。
? 树是一种非线性的数据结构，它是由 n（n >= 0）个有限节点组成的一个具有层次关系的集合。
❓ 那么为什么叫 "树" 呢？
? 我们之所以把它成为 "树"，是因为它很像我们现实生活中的树。只是它是倒过来的，根朝上叶子朝下。
① 有一个特殊的节点，成为根节点，根节点不存在前驱节点。
② 除根节点外，其余节点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm，期中没一个集合 Ti(1 <= i <= m) 又是一颗结构于树类似的字数。每颗子树的节点有且只有一个前驱，可以有0个或多个后继。
③ 因此，树是递归定义的。因为任何树都会被分成根和子树。
?注意：树型结构中，子树之间不能有交集，否则就不是树形结构。
? 节点的度：一个节点含有的子树的个数称为该节点的度。 比如上图中，A的度为6。
? 叶子结点：又称终端节点，度为0的节点称为叶子结点。 比如上图中，BCHIPQ等节点就是叶子结点，因为它们的度为0。
➰ 分支节点：又称非终端节点，度不为0的节点称为分支节点。 比如上图中，DEFG等节点就是分支节点，因为他们的度不为0。
? 父节点：又称双亲结点，若一个节点有子节点，则这个节点称作其子节点的父节点。 比如上图中，A是B的父节点。
? 子节点：又称孩子节点，若一个节点有根节点，则称为该节点的子节点。 如上图，B是A的子节点。
? 兄弟节点：具有相同父节点的节点互相称为兄弟节点。 同一个父亲生的才算。如上图，B和C是兄弟节点，它们的父节点都是A。
? 树的度：一棵树中最大的节点的度称为树的度。 如上图，最大的节点是A，有6个子树，故A的度为6，所以树的度为6。
? 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。 也有将根定义为第0层，根的子节点为第1层的。但是我们建议还是使用根为第1层来定义比较好。
? 树的高度：又称树的深度，树中节点的最大层次。 如上图，树的高度为 4。
?♂️ 堂兄弟节点：父节点在同一层的节点，它们互为堂兄弟。如上图，H 和 I 互为堂兄弟。
? 节点的祖先：从根到该节点所经分支上的所有节点。 如上图·，A是所有节点的祖先。
??? 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。 如上图，所有节点都是A的子孙。
? 森林：由 m(m > 0) 棵互不相交的树的集合称为森林。 比如并查集，多个树构成森林。
❓ 以前学单链表时只有一个指针，双链表两个指针，但是树有多少个指针是不确定的，因为树没有规定一个节点最多有多少个孩子。那我们该如何定义结构呢？
? 方式一：假设说明了树的度为N，才能勉强用
struct TreeNode { int data; struct TreeNode* sub[N]; // 指针数组};问题点：
① 可能会存在不少的空间浪费。
② 万一没有限定树的度为多少呢？这个方式就废了。
? 方式二：vector
// 假设我们定义了一个顺序表// typedef int STLDataType; //顺序表的数据类型// 顺序表中存节点的指针typedef struct TreeNode* SLDataType; //SeqListstruct TreeNode { int data; SeqList s; // s为SLDataType* array;};（C++中这里可以用 vector，但是C里没有）
即使你没有告诉我度是多少，我有多少个孩子我就存多少个孩子，所以这里不需要关心度的问题。但是这里 s 的结构相对复杂，s 里面有一个类型为SLDataType* 的数组，这个数组已经是二级指针了，SLDataType 展开后又是一个 struct TreeNode* 。
? 方式三：双亲表示法
利用结构数组存储（更加复杂）
struct TreeNode { int parenti; int data;};[ A -1] [ B0 ] [ C0 ] [ D0 ] ...... [ H 3 ]
? 每一个元素中存的是结构体 struct TreeNode arr[10]
每个元素内只存自己的值和父亲的下标（A没有父亲是-1，B的父亲下标是0…… H的父亲是D下标为3），可以通过一个值找到自己父亲。
❓ 上列的方式各有优缺点，那么有没有最优的方法？
⚡ 当然有，它就是 —— 《左孩子右兄弟表示法》 有了这个方法，其他的都是渣渣！
typedef int DataType;struct Node { struct Node* _firstChind1; // 永远指向第一个孩子 struct Node* _pNextBrother; // 指向孩子右边的兄弟 DataType _data;};? 解读：无论你有多少个孩子，它都只存两个指针。一个指针永远指向第一个孩子，另一个指针指向孩子右边的兄弟（亲兄弟）。这个树的度无论为多少，也不需要用顺序表存，但是你任何一个节点有多少个孩子都能给你表示出来，通过第一个孩子把所有孩子都找出来。不复杂也没有浪费，只用两个指针就把链接关系都表示出来了，不得不说设计这个的人真是太??了！
文件系统的目录树结构、网络拓扑，最短路径问题，搜索引擎、思维导图等
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/125025.html
摘要：什么是树前面说到的几种数据结构都是线性的，例如链表栈队列等，今天就来学习一种非线性的数据结构树。在上图中的几种二叉树中，有两个是比较特殊的，分别是满二叉树和完全二叉树。除了使用数组存储二叉树外，最常用的便是使用链表法来储存二叉树了。 1. 什么是树？ 前面说到的几种数据结构都是线性的，例如链表、栈、队列等，今天就来学习一种非线性的数据结构——树。先来看看几种树的结构： showImg(...
摘要：图是构成网页的超文本标记语言中的标签相互关联关系所构成的树。节点节点是树的基本构成部分。子树子树是一个父节点的某个子节点的所有边和后代节点所构成的集合。高度树的高度等于所有节点的层数的最大值。每个子树的根节点和其父树的根节点之间通过边相连。 树的例子 我们已经学过了像栈和队列这样的线性数据结构，同时我们对递归也有了一定的了解，现在让我们来看看另一种常见的数据结构——树（Tree）。树在...
摘要：所以，如果中序遍历二叉搜索树，会得到一个有序的数据，时间复杂度是，所以二叉搜索树又叫做二叉排序树。所以，我们需要一种方式来维持二叉树的平衡，最好是将其维持为满二叉树或者完全二叉树，这就是后面会说到的平衡二叉查找树，常见的有树，红黑树。 1. 概述 前面的文章说到了二叉树，其实今天讲的二叉搜索(查找)树就是二叉树最常用的一种形式，它支持高效的查找、插入、删除操作，它的定义是这样的：对于树...
摘要：数据结构程序数据结构算法数据结构基本概念数据的逻辑结构反映数据元素之间的关系的数据元素集合的表示。这两部分信息组成数据元素的存储映象，称为结点。 本文涉及更多的是概念，代码部分请参考之前写过的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本数据结构和查找算法 本文主要是基础的数据结构和算法概念，可能部分地方会涉及更高级的算法和算法，具体内容以...
摘要：是现在广泛流行的代从开始学习系列之向提交代码掘金读完本文大概需要分钟。为了进行高效的垃圾回收，虚拟机把堆内存划分成新生代老年代和永久代中无永久代，使用实现三块区域。 React Native 开源项目 - 仿美团客户端 (Android、iOS 双适配) - Android - 掘金推荐 React Native 学习好项目，仿照美团客户端... 极简 GitHub 上手教程 - 工具...
阅读 1085·2023-04-26 01:03
阅读 497·2021-11-25 09:43
阅读 1645·2021-11-23 09:51
阅读 3095·2021-11-22 15:24
阅读 1162·2021-09-24 09:48
阅读 2477·2021-09-22 15:18
阅读 806·2021-09-03 10:28
阅读 767·2019-08-30 15:55
