数据结构————树

首先我先给大家找棵树，它大概是下边这个样子。

然后给大家找一颗计算机中的树，它大概是下边这个样子。（感觉不是很好ㄟ( ▔, ▔ )ㄏ）

为什么会有树这种结构

看这篇博客之前，如果大家不太清楚数据结构的概念，可以先去看一下我的另一篇关于数据结构的介绍。
数据结构到底怎么来的
我们一开始学习数据结构，都会先从线性表开始学起，而线性表的逻辑结构，是一对一的关系。在放书的例子中，图书馆放书，一个图书馆里有好多不同类型的图书室，图书室里有不同国家的版块，每个国家又有不同著名的作者。这种一对多的逻辑关系，就需要靠树来解决。

简化后模型如下：

树的官方定义

一定要注意每个节点除了和自己的双亲节点有联系，和其他节点不可相交，否则违背定义。另外树里面的上一级节点叫双亲，雌雄同体。如下所示就不是一颗树。

树中的其他概念

节点的度：节点拥有的子树称为节点的度（degree）
树的度：节点的度的最大值。max(节点的度)；
叶子节点：你可以想象树除了枝干会分叉，叶子上会长出叶子吗，所以叶子节点意思就是这个枝干的终点。终端节点。
非终端节点：除根节点，非终端节点和叶子节点是非的关系，也叫做分支节点，也叫内部节点。

孩子：节点的子树的根节点就是该节点的孩子，相应的该节点就是孩子的双亲
兄弟：同一个双亲的孩子互称兄弟
祖先：根节点到该节点所经分支的所有节点。
子孙：以某节点为根的子树中的任意节点。

层次：类比人类宗族，每代人就是一层。
深度或高度：树节点的最大层次就是树的高度。

有序树和无序树

这个概念本来是属于树中其他概念的，但是这里才是需要解说的重点，我们不可以轻易放过他，不然本文也就没有什么意义了。我们从三个节点根据两种规则各自可以组成多少种不同的树开始说起。官方概念如下：

无序树

树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为*树
三个节点，父子之间有序，而兄弟之间无序。组成的树有多少种。
一个父节点，两个兄弟的情况下，只能改变父节点，那么就是三种情况，每个节点当一次父节点。如下图

链式结构的情况下，因为不存在兄弟问题，根节点，三种情况，然后剩下两个节点，根的子节点，两种情况，然后剩下最后一个节点。就是3✖2✖1的情况，六种。如下图

有序树

树中任意节点的子结点之间有顺序关系，这种树称为有序树
三个节点，父子之间有序，并且兄弟之间有序。组成的树有多少种。
一个父节点，两个兄弟的情况下，改变父节点按照无序树有三种方式，兄弟节点互换位置又是两种，2✖3=6。如下图

链式结构的情况下，因为不存在兄弟问题，根节点，三种情况，然后剩下两个节点，根的子节点，两种情况，然后剩下最后一个节点。就是3✖2✖1的情况，六种。如下图

为啥要这么分

那么问题来了，为什么要这么分。后边学了二叉排序树就知道了，左右孩子的有次序还是很重要的。