06《数据布局入门教程》树形布局——二叉树

手机游戏开发者 · 2024-9-14 14:48:50

1. 媒介

前面的章节我们先容了两种告急的数据布局，数组和链表，由于他们各自的特性使得他们的优缺点非常分明，在查询速率和插入速率上顾此失彼，不能分身，那么有没有一种数据布局可以同时高效的完成插入和查询操纵呢，答案固然是肯定的，本日我们就来相识 —— 树布局。

2. 树的界说及常用概念

顾名思义，树布局就是以树为原型的数据布局，用来模仿具有树形布局的数据聚集。大自然的鬼斧神工让人不得不惊叹它的神奇之力，怎样最高效的为每一片叶子供给养分，同时还可以不停的抽枝发芽分支出新的枝干，大树为它的枝叶们提供了最科学的布局底子。而我们也仿照大自然中树的布局，构建了盘算机范畴里的树形布局。下面我们先界说一些有关树形布局用到的概念。

节点：树布局中用于存储数据元素的部门称为节点。
根节点：我们的树是倒挂的，因此最上面的节点我们称之为根节点。
边：毗连元素之间的引用我们称之为边。边是有方向的，从上游节点指向鄙俚节点。
路径：顺着边，将颠末的节点按次序记载下来，称之为路径。路径上节点的个数称之为路径的长度。
父节点：节点的上游节点称之为父节点，通过指向某一节点的边可以找到它的父节点。
子节点：节点的鄙俚节点称之为子节点，通过向下发出的边可以找到它的子节点。
兄弟节点：具有雷同父节点的节点之间互称为兄弟节点。
叶节点：没有子节点的节点称之为叶节点，它是树在这个路径上的末了。
条理：根节点为第一层，根的全部子节点为第二层，第二层的全部子节点构成第三层，以此类推。
深度：从根节点到某一个节点的路径长度称之为该节点的深度。根节点的深度为 0。
高度：从某一节点出发到最远的叶节点的路径长度称之为该节点的高度。叶节点的高度为 0。

3. 二叉树

当一个树形布局上的每个节点最多只有两个子节点时，这个树可以称之为二叉树。二叉树根据节点和元素的分布又可以细分很多类型，好比：

满二叉树：除叶节点外，每一个节点都有两个子节点。
完全二叉树：当我们从上至下，从左至右，按照二叉树的布局依次排满每一个节点的时间，这个树就是完全二叉树，其中当最下面一层的叶节点排满时，这个完全二叉树同时也是满二叉树。

二叉搜索树：当一个节点有左子节点时，左子树上的全部节点肯定小于它，同时当一个节点有右子节点时，右子树上的全部节点肯定大于它，这个树称之为二叉搜索树，大概二叉查找数。通过这个特殊的约定，我们得到了一个规律性很强的树形布局，给我们做进一步的搜索查找提供了很大的便利。

4. 遍历树

对树上节点的访问次序实在是一样的，但是输出次序差异，根据输出次序我们将遍历分为三种：前序遍历、中序遍历、后序遍历。

前序遍历的规则是根节点 > 左子树 > 右子树；

中序遍历的规则是左子树 > 根节点 > 右子树；

后序遍历的规则是左子树 > 右子树 > 根节点；

5. 小结

本节我们学习了树形布局，我们要清楚把握常用的概念，知道树是由节点和边构成的一种抽象数据类型，相识二叉树的界说和特点，知道二叉树的每个节点最多有两个子节点，说出几种最常见的二叉树类型好比满二叉树和完全二叉树，相识当二叉树中任意一个节点下的左子树的全部节点都比该节点小，右子树的全部节点又都比该节点大时，这个树称之为二叉搜索树。此外各人要根据前序遍历、中序遍历、后序遍历的规则，联合动图把握二叉树遍历的思绪和方法。

06《数据布局入门教程》树形布局——二叉树

所属分类: 问答交流

新帖推荐: 30日

推荐作品