数据结构——树的简介

发表时间：2024-07-13 01:17:50 来源：网友投稿

最近数据结构的课程讲到了树，在这课程尾声将至之时，写一篇基础性的小文章，介绍一下“树”这种数据结构。

看看书本是怎么对“树”进行定义的：

前面的都好理解，问题是最后一句话，什么是互不相交？光说无益，来看图。

如上图所示，（A）和（B）是符合树的定义的，而（C）和（D）不是树，用术语来说是因为它们都有相交的子树，直观地看图而言，是因为它们的节点形成了回路。

那么我们已经知道如何辨别一棵树了。接下来就是零零碎碎的知识点了，话不多说，上图！

孩子节点：一个节点含有的子树的根节点称为该节点的子节点。如1的子节点为2、3

节点的度：一个节点含有的子节点个数称为该节点的度。如2的度为2，6的度为1

树的度：树中最大的节点的度称为树的度。如该树节点的度最大为2，故树的度为2

叶子节点：度为0的节点。如4、5、8、7

内部节点：除根节点外，度不为0的节点。如2、3、6

双亲结点：含有孩子节点的节点。如1、2、3、6

兄弟节点：具有相同的双亲节点的节点互为兄弟节点。如2和3、4和5、6和7

节点的祖先：从根到该节点所经路径上所有的节点。如8的祖先为6、3、1

节点的子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如3的子孙为6、7、8

在相关的算法题中，最常见的就是二叉树了（我也是下午刚做完一道），我们来看一下它的定义：

也就是说，二叉树中的节点的度不超过2。值得一提的是，左子树和右子树是有顺序的，有左右之分。

下面，我们来看看特殊的二叉树，顺便也熟悉一下二叉树的定义：

满二叉树：所有分支节点都存在左子树和右子树，而且所有的叶子节点都在同一层。

完全二叉树：树的叶子节点只能出现在最下层和倒数第二层，并且最下层的叶子节点必须从左到右“铺满”，中间不能有空缺。

这么说好像也有一些绕口，现在我们来看一下图例。

由图例我们不难看出，满二叉树也是完全二叉树的一种特例。

斜二叉树：顾名思义，“斜二叉树”就是斜着的二叉树，它的节点只有左子树或者右子树。节点只有左子树的称为左斜树，只有右子树的称为右斜树。

免责声明：本站发布的教育资讯（图片、视频和文字）以本站原创、转载和分享为主，文章观点不代表本网站立场。

如果本文侵犯了您的权益，请联系底部站长邮箱进行举报反馈，一经查实，我们将在第一时间处理，感谢您对本站的关注！