【数据结构】中有关树的解析

朴灿烈づ我的快乐病毒、 2022-09-30 04:58 130阅读 0赞

在数据结构中，为了更好地存储和查找文件，用了一种非线性的数据结构：树，接下来我们就来仔细的研究一下树。

树的概念以及定义：

树，就是长得像一棵树一样，只不过我们通常画的是一颗倒过来的树：

树（tree）是包含n（n>0）个节点的有穷集合，其中：

（1）每个元素称为节点（node）；

（2）有一个特定的节点被称为根节点或树根（root）。

（3）除根节点之外的其余数据元素被分为m（m≥0）个互不相交的结合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。

![Center][]

有关树的术语：

节点：结点包含数据和指向其它节点的指针。  
根节点：树第一个结点称为根节点。  
结点的度：结点拥有的子节点个数。  
叶节点：没有子节点的节点(度为0)。  
父子节点：一个节点father指向另一个节点child，则child为孩子节点，father为父亲节点 。  
兄弟节点：具有相同父节点的节点互为兄弟节点。  
节点的祖先：从根节点开始到该节点所经的所有节点都可以称为该节点的祖先。  
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。  
树的高度：树中距离根节点最远节点的路径长度。

![Center 1][]

二叉树：二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。

完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树

![Center 2][]

满二叉树：高度为N的满二叉树有2^N - 1个节点的二叉树。

![Center 3][]

树还可以分为红黑树，B树，后缀树等等......

[Center]: /images/20220708/4618e706923241dba597a496e433451c.png
[Center 1]: /images/20220708/1cfaaf996f35408e91dd21b24ef3ecd3.png
[Center 2]: /images/20220708/77f2a6ca97e84ce5a964041d38440b36.png
[Center 3]: /images/20220708/13ced141c4444ee09706c45a77c4a751.png

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构中树与二叉树原理解析

今天我们分析数据结构中树与二叉树原理：这是数据结构中各种树的基础。 1、树的定义树(Tree):N个结点构成的有限集合。树中有一个称为”根(Root)”的特殊结点其余

Love The Way You Lie/ 2022年10月22日 02:57/ 0 赞/ 106 阅读

相关【数据结构】中有关树的解析

在数据结构中，为了更好地存储和查找文件，用了一种非线性的数据结构：树，接下来我们就来仔细的研究一下树。树的概念以及定义：树，就是长得像一棵树一样，只不过我们通

朴灿烈づ我的快乐病毒、/ 2022年09月30日 04:58/ 0 赞/ 131 阅读

相关数据结构：红黑树解析

本文参考：Google、算法导论、STL源码剖析、计算机程序设计艺术。推荐阅读： 1. Left-Leaning Red-Black Trees, Dagstuhl W

梦里梦外;/ 2022年07月16日 06:14/ 0 赞/ 148 阅读

相关消息队列有关的数据结构

[数据结构][Link 1]： 1．ipc\_perm 系统使用ipc\_perm 结构来保存每个IPC 对象权限信息。在Linux 的库文件linux/ipc.h 中，

淩亂°似流年/ 2022年07月16日 01:13/ 0 赞/ 174 阅读

相关【数据结构】中平衡搜索树的旋转方式解析

数据结构中有一种平衡搜索树，在平衡树中，为了保证任意节点的平衡因子的绝对值不超过2，成为平衡树，就需要对树进行降高度的操作在降高度的操作中，有几种旋转方式，左单旋，右单旋，

布满荆棘的人生/ 2022年06月18日 09:48/ 0 赞/ 143 阅读

相关【数据结构】中有关堆的讲解

堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。堆结构的二叉树存储是：最大堆：每个父节点的都大于孩子节点。最小堆：每个父节点的都小于孩子节点。

雨点打透心脏的1/2处/ 2022年06月18日 05:21/ 0 赞/ 177 阅读

相关结构化数据和非结构化数据解析

1.1. 数据分类我们生活中的数据总体分为两种：结构化数据和非结构化数据。结构化数据：指具有固定格式或有限长度的数据，如数据库，元数据等。非结构化数据：指不定长

深碍√TFBOYSˉ_/ 2022年06月06日 13:48/ 0 赞/ 237 阅读

相关《数据结构学习指导与习题解析》-树

树的ADT（抽象数据类型） template <class T> class Tree{ public: Tree();

偏执的太偏执、/ 2022年05月08日 15:40/ 0 赞/ 145 阅读

相关数据结构：简述数据结构中的树

1. 二叉树二叉树是一种从上往下分叉的一种数据结构，其每个节点最多有两个孩子节点，一左一右，左边的称为左孩子，右边的称为右孩子。如下： ![在这里插入图片描述][wa

清疚/ 2022年03月18日 11:10/ 0 赞/ 254 阅读

相关 B+树索引结构解析

一、二分查找法　　二分查找法（binary search）也成为折半查找法。用来查找一组有序的记录组中的某一记录。　　基本思想是：将记录按有序化（递增或递减）排列，

我不是女神ヾ/ 2021年12月09日 01:04/ 0 赞/ 254 阅读