Question

数据结构——树的简介

Answer 1

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

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

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

       如上图所示，（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。值得一提的是，左子树和右子树是有顺序的，有左右之分。

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

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

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

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

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

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