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

文章大纲

树的知识点

树的定义

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

        树是n (n>=0)个节点的有限集。n=0时，我们称为空树。在任意一棵非空树中，有且仅有一个称为“根”的节点。每个节点有零个或多个子节点，没有双亲节点的节点称为根节点，每一个非根节点有且仅有一个双亲节点。除了根节点外，每个子节点可以分为多个不相交的子树。

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

树或非树

       如上图所示，（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

二叉树

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

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点  。

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

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

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

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

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

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

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