树的定义及表示
这一部分主要介绍一下数据结构中很重要的一个概念：树。那么什么是树呢？在说明这个概念之前，我们先来看看和它相关的一些内容。
1. 查找
查找是根据某个给定关键字K ，从集合R中找出关键字与K相同的记录。查找又分为静态查找和动态查找，静态查找的集合中记录是固定的，没有插入和删除操作，只有查找，而动态查找的集合中记录是动态变化的，除了查找外，还可能发生插入和删除操作。
1.1 静态查找
方法一：顺序查找
顺序查找就是从数组中一个一个地找，直到找到我们想要的元素为止。
如图所示，在长度为8的数组中查找元素K，如果我们从最后一个元素找起来，查找成功就返回所在单元下表，不成功返回0。查找过程中，在第一个几点建立哨兵，哨兵的作用可以让程序知道什么时候应该停下来，同时可以少些一个判断条件。
public int sequentialSearch(int[] array, int k) {
int i;
array[0] = k; // 建立哨兵
for (i = array.length - 1; array[i] != k; i--) ;
// 查找成功返回所在单元下标，不成功返回0
return i;
}
public static void main(String[] args) {
Search search = new Search();
int[] array = new int[9];
for (int i = array.length - 1; i != 0; i--) {
array[i] = i;
}
int target = 7;
int result = search.sequentialSearch(array, target);
System.out.println("search for " + target + " in array is " + result);
}
方法二：二分查找(Binary Search)
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。 但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
注意，二分查找的前提是连续存放（数组）是有序的。
二分查找示例：
在一个按从小到大排序的数组中查找 444 这个元素，用三个指针分别代表左边，右边和中间，每次查找都将中间为止的值和目标值对比，若大于目标值，则在左半部分做二分查找，若小于目标值，则在右半部分做二分查找。
public int binarySearch(int[] array, int k) {
/*在表Tbl中查找关键字为K的数据元素*/
int left, right, mid, NoFound = -1;
left = 1; /*初始左边界*/
right = array.length; /*初始右边界*/
while (left <= right) {
mid = (left + right) / 2; /*计算中间元素坐标*/
if (k < array[mid]) right = mid - 1; /*调整右边界*/
else if (k > array[mid]) left = mid + 1; /*调整左边界*/
else return mid; /*查找成功，返回数据元素的下标*/
}
return NoFound; /*查找不成功，返回-1*/
}
二分查找的时间复杂度为O(logN)
二分查找是一种效率比较高的查找算法，整个二分查找的过程可以描述为以下的这种树形结构：
结点表示的是数组的下标，这样的结构称为二分查找判定树，判定树上每个结点需要的查找次数刚好为该结点所在的层数。反过来讲，我们如果将数据按照树的这种形势存储起来，是不是也能达到二分查找这种效率呢？
2. 树的定义
树是 n （n>=0）个结点构成的有限集合。当n=0时，称为空树。
对于任何一棵非空树，具备以下性质：
- 树中有一个称为 根（root） 的特殊结点
- 其余结点可分为 m（m>0) 个互不相交的有限集， 其中每个集合本身又是一棵树，称为原来树的子树。
2.1 树的一些基本术语
- 结点的度（Degree）：结点的子树个数。
- 树的度：树的所有结点中最大的度数。
- 叶结点：度为 0 的结点。
- 父结点：有子树的结点是其子树的根结点的父结点。
- 子结点：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。
- 兄弟结点（sibling）：具有同一父结点的各结点彼此是兄弟结点。
- 路径和路径长度：从结点n1到nk的路径为一个结点序列n1, n2,… , nk , ni是ni+1的父结点。路径所包含边的个数为路径的长度。
- 祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
- 子孙结点(Descendant)：某一结点的子树中的所有结点是这个结点的子孙。
- 结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。
- 树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度。
2.2 树的表示
采用儿子-兄弟表示法来表示一个树的结点，其中左边的指针指向第一个子节点，右边的指针指向相邻的兄弟结点，兄弟结点或子结点为空则用Null表示。
参考：浙江大学-陈越老师的数据结构课程