树与树的表示

什么是树？

在我们现实世界中存在很多事物都是层次关系，比如：

• 人类社会家谱：一代一代的关系就是层次关系
• 社会组织结构：主席、部长、处长、厅长....
• 图书信息管理：字典

为什么我们要用这种分层次的组织关系?
因为这种分层次的组织管理是非常具有效率的

举个栗子：
在实现查找这种基本操作时，我们可以有以下几种：

1. 顺序查找：就是从头或者从尾一个一个的查找，这种查找时间复杂度是O(n)

2. 二分查找：如果我们要查找一个有序的数组时，可以先查中间的数，和要查找的数进行比较。如果大于要查找的数则在这个中间的数左边查找，如果小于则在右边查找。以此类推。这种查找的方式时间复杂度可以根据公式推断出来是O(long2n)

二分查找的代码：

其实这种二分查找我们可以抽象成一个“树”：

比如要在11个元素中进行二分查找：

Paste_Image.png

从这个树上我们可以观察出，我们要查找的节点所需要的查找次数正式结点所在的层数，所以我们可知成功查找的次数不会超过树的深度：long2n + 1

那么我们可以思考，如果能把我们的计算机里数据结构能抽象成树的岂不是在做基本操作，不只是查找的时候，比如删除，添加的时候更加的方便快捷。

树的定义

树：是由n个节点构成的有限集合，n=0时称为空树，对于任意一个非空树，它有以下属性：

• 树有一个叫根节点的特殊节点
• 其余节点可以分为m个互不相交的有限集T1....Tm，其中每个集合本身又是一棵树，称为子树
• 子树是不可相交的
• 除了根节点之外，每个界定啊有且只有一个父节点
• 一棵N个节点的树有N-1条边

树的基本术语：

1. 节点的度：节点的子树个数
2. 树的度：树的所有节点中最大的度数
3. 叶子节点：度为0的
4. 父节点
5. 子节点
6. 兄弟节点
7. 路径和路径的长度：从节点n1到nk的路径是一个结点序列：n1,n2...nk，这个路径包含的边的个数是路径的长度
8. 节点的层次
9. 树的深度：树种所有结点种最大的层次是树的深度

那么我们该如何去表示一棵树呢？

1. 我们用数组能表示一棵树吗？很显然这样是很困难的，而且很难再树上做操作

2. 我们用链表该如何表示：
   我们可以把指向子结点的的边都用一个引用表示，这样的数据结构就类似于下面这样。

   
   1
   

   这样虽然可以表示一棵树，但是它有一个明显的缺点：就是每个结点的引用的个数都是不确定的，如果我们用确定的表示，那么每个结点的指针的个数就是这棵树的最大度数，这样虽然能够统一结构，但是会造成空间的浪费。

那么有没一种表示方法可以格式统一还能不造成空间浪费呢？

儿子-兄弟表示法：

具体表示方法如下图：

Paste_Image.png

我们每个结点用三个域来表示，其中一个是这个结点的值和属性什么的，另外两个是指针，其中一个是指向它的第一个儿子结点，另外一个指向它的兄弟节点。如果没有儿子或兄弟那么就是用null表示。

这样我们就可以实现格式的统一还没有很多的空间的浪费。

我们可以仔细观察这个用儿子-兄弟表示法表示的树

Paste_Image.png

我们换个角度可以看到它其实每个结点都有且最多只有两个边，这种的树我们称之为二叉树，其实所有的树都可以转成二叉树表示，所以学习二叉树的特点是很关键的。