1.前言
2.预备知识
3.二叉树
4.查找树ADT–二叉查找树
5.总结
1前言对于大量的输入数据，链表的线性访问时间太慢，不宜使用。这部分介绍一种简单的数据结构，其大部分操作的运行时间平均O(logN)。
2预备知识定义树的一种自然的方式递归的方法。一棵树是一些节点的集合。这个集合可以是空集；若非空，则一棵树由称做根（root）的节点r以及0个或多个非空的（子）树T1,T2,…,Tk组成，这些子树中每一棵的根都被来自根r的一条有向的边（edge）所连接。
每一棵子树的根叫做根r的儿子（child），而r是每一棵子树的根的父亲（parent）。
从递归的定义中我们发现，一棵树是N个节点和N-1条边的集合，其中的一个节点叫做根。没有儿子的节点称为树叶（leaf）；具有相同父亲节点的为兄弟（sibling），用类似的方法可以定义祖父（grandparent）和孙子（grandchild）关系。
从节点n1到ni的路径（path）定义为节点n1,n2,…,nk的一个序列，使得1≤i≤k，节点ni是ni+1的父亲。这个路径的长（length）为该路径上边的条数，即k-1。从每一个节点到它自己有一条长为0的路径。注意，在一棵树中从根到每一个节点恰好存在一条路径。
对任意节点ni，ni的深度（depth）为从根到ni的惟一路径的长。因此，根的深度为0。ni的高（height）是从ni到一片树叶的最长路径的长。因此所有树叶的高都是0。一棵树的高等于它的根的高。一个树的深度等于它的最深的树叶的深度；该深度总是等于这棵树的高。
2.1树的实现实现树的一种方法可以是在每一个节点除数据外还要有一些指针，使得该节点的每一个儿子都有一个指针指向它。
2.2树的遍历和应用流行的用法之一是包括UNIX、VAX/VMS和DOS在内的许多常用操作系统中的目录结构。
先序遍历（preordertraversal）。在先序遍历中，对节点的处理工作是在它的诸儿子节点被处理之前（pre）进行的。例子，列出分级文件系统中的目录。
后续遍历（postordertraversal）。在后序遍历中，对节点的处理工作是在它的诸儿子节点被计算后（post）进行的。例子，计算一个目录大小。
3二叉树二叉树（binarytree）是一棵树，其中每个节点都不能有多于两个的儿子。
上图显示一棵由一个根和两棵子树组成的二叉树，TL和TR均可能为空。
二叉树的一个性质是平均二叉树的深度要比N小得多，这个性质有时很重要。分析表明，这个平均深度为O(N)，而对于特殊类型的二叉树，即二叉查找树（binarysearchtree），其深度的平均值是O(logN)。不幸的例子如图所示，深度大到N-1。
3.1实现因为一棵二叉树最多有两个儿子，所以我们可以用指针直接指向它们。树节点的声明在结构上类似于双链表的声明，在声明中，一个节点就是由Key（关键字）信息加上两个指向其他节点的指针（Left和Right）组成的结构。
3.2表达式树表达式树的树叶式操作数（operand），而其它节点为操作符（operator）。
中缀表达式（infixexpression）使用（左，节点，右）的中序遍历（inordertraversal）。
另一种遍历策略是递归打印左子树、右子树，然后打印运算符。这种策略称为后序遍历（postordertraversal）。
第三种遍历策略是先打印运算符，然后递归地打印出左右子树。是不常用的前缀（prefix）记法，这种遍历策略为先序遍历（preordertraversal）。
4查找树ADT–二叉查找树二叉查找树的性质是，对于树中的每个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。
因为二叉查找树的平均深度是O(logN)，所以我们一般不必担心栈空间被用尽。
4.1二叉查找树的编程实现重复元的插入可以通过在节点记录中保留一个附加域以指示发生的频率来处理。
对于删除，复杂的情况是处理具有两个儿子的节点。一般的删除策略是用其右子树的最小数据（很容易找到）代替该节点的数据并递归地删除掉那个节点（现在它是空的）。如果删除的次数不多，则通常使用的策略是懒惰删除（lazydeletion）：当一个元素要被删除时，它仍留在树中，而是只做了个被删除的记号。
4.2平均情形分析直观上，除MakeEmpty外，我们期望所有的操作都花费log(N)时间，因为我们用常数时间在树中降低了一层，这样一来，对树的操作大致减少一半左右。因此，除MakeEmpty外，所有的操作都是O(d)，其中d是包含所访问的关键字的节点的深度。
一棵树的所有节点的深度的和称为内部路径长(internalpathlength)。
如果向一棵预先排序的树输入数据，那么一连串Insert操作将花费二次时间，而链表实际的代价会非常巨大，因为此时的树将只由哪些没有左儿子的节点组成。一种解决办法就是要有一个称为平衡（balance）的附加的结构条件：任何节点的深度均不得过深。有许多一般的算法实现平衡树，后面讨论最老的一种平衡查找树，即AVL树。
另外较新的方法是放弃平衡条件，允许树有任意深度，但是在每次操作之后要使用一个调整规则进行调整，使得后面的操作效率更高。这种类型的数据结构一般属于自调整（self-adjusting）类结构。在二叉查找树的情况下，对于任意单个运算我们不在保证O(logN)的时间界，但是可以证明任意连续M次在最坏情形下花费O(MlogN)。一般这足以防止令人棘手的最坏情形。后面讨论的这种数据结构叫做伸展树（SplayTree）。
5总结本节介绍了树在操作系统、编译器设计以及查找中的应用。表达式树是所谓的分析树（parsetree）的小例子。分析树是编译器设计中的核心数据结构。分析树不是二叉树，而是表达式树相对简单的扩充。
查找树在算法设计中是非常重要的。它们几乎支持所有有用的操作，而其对数平均开销很小。查找树的非递归实现多少要快一些，但是递归实现更讲究、更精彩，而且易于理解。
全文完。
如果觉得不错，就随手点个「在看」吧。
预览时标签不可点收录于话题#个上一篇下一篇