计算机树（1）

从链表到二叉树

了解了数学图论中的图和树，接下来思考一下计算机中的树。

链表：

        我们再算法最开始接触到的也是最常用的数据结构，就是链表，为什么说树要从链表开始？这就是一个数据结构的问题：

一般我们的链表形态是这样的：

 

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}

        我们是在当前节点上，保存下一个节点，形成一个链式结构。

        在java基础中我们就看过，对于数据结构的选择：增加，删除操作比较频繁的话，我们倾向选择链表结构；查询，修改较多的话我们倾向选择数组结构。究其原因就是如果我们要查找一个元素，遍历链表的时间复杂度是O（n）（链式结构）只能从前向后一个一个遍历；而数组依据自己的索引下标，可以通过各种排序和查找算法降低O，提高性能，所以链表搜索和访问速度是相对数组来说较慢的。

综上所述，链表结构存在两个问题：

        1.链表作为线性结构，不能像数组一样通过下标方便的取值，只能从头到尾遍历元素

        2.存数据的时候，我们拿到数据，添加到链表的尾端，这是一个无序的过程，并且排序也相对困难（不能记录下标swap）。

所以为了不是单纯的从前往后遍历，新的两种数据结构就出现了：

        1.双向链表：在链表的基础上存入上一个节点的信息，以便反向遍历。

class ListNode {int val;ListNode next;ListNode prev;ListNode(int x) { val = x; }
}

 2.树：在链表的基础上存入多个下一节点的信息。

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}

 所以这样，树就应运而生了。

树：

        我们把一个节点中存入多个下一节点的数据结构称为树，首节点称为根节点。

        相比数学的树，我们更倾向于吧计算机树抽象成一个根系的结构：

         从根root开始向下展开，根据树的结构分析，我们又可以将树进行细分。比较常减的树就包括了二叉树（Binary Tree），二叉搜索树（Binary Search Tree）哈夫曼树(Huffman Tree)，平衡二叉树（ALV Tree），红黑树（R-B Tree），B树（B Tree）和B+树

二叉树（Binary Tree）：

二叉树是树的特殊一种，具有如下特点：

1、每个结点最多有两颗子树，结点的度最大为2。

2、左子树和右子树是有顺序的，次序不能颠倒。

3、即使某结点只有一个子树，也要区分左右子树。（left subtree）（right subtree）

二叉树又可以分为以下几种：

普通二叉树

        由一个根节点加上两棵分别称为左子树和右子树组成

 满二叉树

叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点

1. 叶子只能出现在最下一层。

2. 非叶子结点度一定是2.

3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

 完全二叉树

 

        叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大：

        假设这个树有K层，此树前提是二叉树，K-1层必须是满的，K层左边（左子树）必须先满右边才能为空。

1. 叶子结点只能出现在最下一层（满二叉树继承而来）

2. 最下层叶子结点一定集中在左 部连续位置。

3. 倒数第二层，如有叶子节点，一定出现在右部连续位置。

4. 同样结点树的二叉树，完全二叉树的深度最小（满二叉树也是对的）。

 

二叉树的储存

        那么，对于这种二叉树结构，我们是如何储存的呢

想要存储一棵二叉树，一种方法是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。也就是基于链表和数组。

二叉链式存储法：

        链式存储更为直观，也比较简单。图中，每个节点有三个字段，其中一个存储数据，另外两个指向左右子节点的指针。只要找到根节点，就可以通过左右子节点的指针，把整棵树都串联起来，大部分二叉树都是通过这种结构实现的。

 

数组顺序存储法：

        如下图所示，基于数组的顺序存储法，图中，我们把根节点A存储在下标i=1的位置，那么左子节点B存储在下标2*i=2的位置，右子节点C存储在2 * i +1=3的位置，以此类推。总结：如果节点X存储在数组中下标为i的位置，下标为2i的位置存储的就是其左子节点，下标为2 * i +1的位置存储的就是右子节点，反过来也可以倒推。因此，我们只要知道根节点的存储位置（一般情况下，为了方便计算，根节点都会存储在下标为1的位置），这样就可以通过下标计算，把整棵树的节点串联起来。

 

        完全二叉树，就只浪费了一个下标为0的存储位置。但如果是非完全二叉树，就会浪费比较多的位置。

 二叉树的遍历

        数据存进去以后，我们要怎么查找呢？这就涉及到二叉树的遍历问题了，二叉树的遍历有三种方式，前序遍历，中序遍历和后序遍历。

        前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树——根左右

        中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树——左根右

        后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身——左右根

 

从这个例子来举例说明的话：

        先序遍历是我们从A点开始，A，B，D，H，I，E，J，C，F，G

        中序遍历是我们从A点开始，H，D，I，B，J，E，A，F，C，G

        后序遍历是我们从A点开始，H，I，D，J，E，B，F，G，C，A

        我们了解了二叉树，发现这种结构，相比较单向链表，如果我们已知元素在哪个子树，可能会加快查找的速度，要是乱序状态下查找，还是需要遍历整个树才能找到需要查找的值。那么有没有可能我们可以提前知道我们要的值在哪一个子树中呢？