数据结构是一种将数据组织、存储起来的方式。存储数据并不是为了存储而存储，存储是为了将来增删改查方便。仔细想想，我们开发任何数据库的过程，是不是也始终绕不开增、删、改、查四个字对吧？
大家想必已经熟悉了数组和链表两种数据结构，它们都是类似序列的形式。有没有想过它们在增删改查性能上的不同呢？
数组注重给予每个元素唯一的下标，根据下标查询、更改都非常的方便。可是要插入和删除数据时，如果不是末尾操作，那操作位后的所有数据都要后移或前移一位。另外，根据值查询非常笨重，需要按照下标遍历。
链表没有下标的概念，每一个数据都记录下一个数据的地址。查询都是用遍历的方法从头开始查询。但是增删非常方便，只需要更改少数数据的地址即可。
由此可见，数组和链表都在按值查询效率上力有不逮（只能遍历），有没有优化遍历查询效率的方法呢？这便是树结构，他诞生的一个重要目的就是提升按值查询效率。
一、什么是树结构？
你可能已经知道树结构的一些知识，甚至见过如下图这样的二叉树。
图1-典型二叉树
不过在学习树结构之前，我们必须知道什么样的结构才算一棵树。
在《离散数学结构》中，树是这样定义的：
图2-树的定义
比起图片，数学书上对于树的定义显得太抽象了。那么我们就结合图1来分析这个定义到底说的是什么。
首先，我们注意到图1中的二叉树，由两种主要的元素构成，一种是一个圆圈，里面设定了一个v0~v9的标号。一种是由一个圆圈指向另一个圆圈的箭头。
图1中的圆圈，我们称之为顶点，计算机中也经常叫作节点。这些顶点指代集合A中的所有元素。
图1中的箭头，我们称之为边。这些边指代A中两个元素vi~vj的关系。关系可以是多种多样的，假设v0和v1都是数，那么v1v0就是一种关系，v1整除v0是另一种关系。当然，一棵树中的关系只能是一种。
T是A上的关系，指的是T是A中某种关系的集合，也就是图1中所有边的集合。当这些边满足了定义，那么T就可以被称为树。当然，我们平时讨论树的时候，也会把顶点加进来，不影响结论。
道路，指的是从某个顶点沿着边的箭头方向依次到达另一个顶点——如果这能够做到，那么经过的边的集合就是一条道路。如图3，从v0到v9经过的三条边，就组成了v0到v9的道路。
图3道路
以上就是对关系、顶点、边、道路这几个概念的简单描述，更详细的定义请翻阅《离散数学结构》。在理解了这些概念之后，我们来看定义，它实际上说的就是：
1、一棵树里面必须有一个顶点v0，只有箭头往外指的边，没有从其它顶点指向它的边。
2、除v0之外的任何顶点，一定能从v0开始沿着箭头找到它，且经过的路线唯一。
在熟悉了这个定义之后，我们来看看下面的结构到底是不是树：
（a）
(b)
（c）
（d）
图（a）不是树，v0，v2，v5，v4，v1构成了一个环，这导致没有任何一个顶点是不被箭头指向的，也就没有顶点可以成为根。
图（b）是树，树的定义里没有规定顶点必须要多少个箭头指向外面，也没有规定道路必须朝哪个方向延伸。我们习惯把根画在上面，枝叶画在下面，与现实中的树相反，只是因为这么画比较方便而已。
图（c）不是树，因为从v0到v8有v0-v1-v3-v8和v0-v1-v4-v8两条路。也就是说树结构中允许出现“盘根错节”的情况。
图（d）不是树，虽然v0和v2都有成为树根的潜质，但是这也导致没有路线从v0到v2，或者从v2到v0。树的根只能有一个。
二、树结构有哪些特性？
在对树的定义有一定程度的理解后，我们再多说几个概念，回过头来看图1：
1、树有一个根v0，我们常把v0称作树的第0层。
2、从v0出发的边到达的顶点，如v1和v2，被称为第1层，以此类推，v1，v2出发的边到达的顶点为第2层……
3、树最大的层数，被称为树高——H，直观地看H代表了一棵树向外延伸的程度。
4、第1层的v1，v2是第0层v0的孩子（也可称后代或者子节点）。第0层的v0是第1层v1，v2的父亲（也可称父节点）。同层节点v1，v2是兄弟（兄弟节点）。如果兄弟间排个1，2，3次序，那么树就会成为有序树。
图5-更多概念
5、没有任何后代的顶点，如v5、v7等，被称为叶子（叶子节点）。注意叶子不一定处在最大层，但在最大层的一定是叶子。
结合前面探索树的定义的过程，我们可以发现树结构的一些性质：
1、树的根v0有且只有一个。
2、除v0外，任何节点都有且只有一条边指向它。
3、树中不存在任何回路。（如图b中的环，或者既有v1到v3又有v3到v1的边）
4、树中的任何节点v，它和后代乃至后代的后代可以构成一棵新的树，v就是其根节点。
总结这些概念和性质有什么意义呢？前面说到，树结构是优化链表的查询效率的一种解决方案。链表虽然遍历查询十分笨重，但是至少不会出现纰漏。树是怎么保证查询过程严谨合理不出错的呢？
1表示树只有一个根，任何查询从根开始，就像链表从表头开始一样。
2和3表示树中的任何节点都可以被访问到，且访问过程唯一，不会因为存在回路陷入死循环。
4表示树可以用递归方法构造。根和其他节点、父节点和子节点之间其实没有本质上的区别，可以套用一种数据单元。
树高H则体现了树结构的查询效率。如果树构造得当，那么查询任何一个元素的步数最多不会超过树高H。可以很直观地看到，如果需要查询图1中的v8，那么v2及其子树，还有v4下属的节点等，都是不需要访问的。
三、怎样搭建树结构？
那么，如何在计算机中构造一个树呢？难道要把它画出来？
其实并非如此，树的构造更接近于链表，不是像数组那样直接声明一个数组然后一个个往里塞数据，而是建立一个个数据单元然后规定它们之间的联系，使之称为一个抽象的结构。
树结构使用的数据单元很简单，链表的数据单元是两个格子，一个格子放数据，另一个格子放下一个数据的地址对吧？
树结构的数据单元就是多加几个格子，除了第一个放数据，后面几个都是各个子节点数据的地址。
在计算机中，数据之后要安排几个格子，一般都是固定的。因而诞生了n-树的概念。《离散数学结构》中n-树的定义如下：
图6-n-树的定义
如果我要构造一棵n-树，那我就在数据单元后放n个格子用来存地址。同时需要定义好规则，我访问到这个数据单元之后，接下来判断我要去访问它的哪个子节点，还是说要回到父节点。
定义访问哪个子节点的规则，是构造树中最重要的部分。平时我们最常使用二元树（也经常叫二叉树、二杈树），就是因为非常方便，小于走左边，大于走右边。关于这块，涉及二叉堆和二叉搜索树的知识，我们留到下期再讲。
留言区
预览时标签不可点收录于话题#个上一篇下一篇