数据结构笔记
关于树的定义
对于大量的输入数据，链表的线性访问时间太慢，不宜使用。故我们引用了一种新的数据结构，它的大部分操作的运行时间平均为O(log N)，这种数据结构保证了在最坏情形下的时间界。
没错，这就是数。
当然，更精准的说，是二叉查找树。
树可以使用几种方式进行定义，其中一种自然的方式是递归方法，如下：
树是n(n>=0)个节点的有限集。它 (1)或者是一棵空树（n=0），空树中不包含任何结点 (2)或者是一棵非空树（n>0），此时有且仅有一个特定的称为 根（root） 的节点；当n>1时，其余节点可以分为m(m>0)个互不相交的有限集T1,T1,…,Tm，其中每一个本身又是一棵树，并且称为根的 子树(sub tree)
递归定义通常是非常不好理解的(笑)，这很正常，那么我们简化一下定义。
首先，树是这样一个数据集合，它含有若干个由数据构成的元素并且这些节元素之间人为的定义了一些关系。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊地位，这个节点称为该树的根节点，或简称树根。
而二叉树则是一种特殊的树，它的每个节点只有最多两个子节点，故称为二叉树。
树的实现
实现树的一种方法，是在每一个节点除数据外定义一些指针，使得该节点的每一个儿子都有一个指针指向它。然而由于每个节点的儿子数可以变化很大而且事先并不知道，因此在数据结构中定义到各个儿子节点的直接指针是不现实的，这会浪费很多空间。
实际上的解法很简单，如下：
using PtrToNode = struct TreeNode *; //将PtrToNode定义为TreeNode的指针的别名
struct TreeNode
{
ElementType Element; //节点中存储的数据
PtrToNode FirstChild; //节点自身的第一个儿子节点
PtrToNode NextSibling; //节点的下一个兄弟节点
};
这里的下一个兄弟就是指有相同父节点的节点。
以上是普通树的定义，以下是二叉树的定义：
using PtrToNode = struct TreeNode *; //将PtrToNode定义为TreeNode的指针的别名
using Tree = struct PtrToNode; //将Tree定义为PtrToNode的别名
struct TreeNode
{
ElementType Element; //节点中存储的数据
Tree Left; //节点的左子树
Tree Right; //节点的右子树
};
树的遍历及应用
树有许多种常见应用，流行的用法之一就是包括UNIX，VAX/VMS和DOS等常用操作系统中的目录结构。即每个文件夹下的文件和文件夹都是这个文件夹的子节点。
若要打印这样一个文件目录则可以i使用如下函数遍历它：
static void ListDir( DirectoryOrFile D, int Depth)
{
if ( D is a legitimate entry )
{
PrintName( D , Depth);
if ( D is a directory )
for each child, C, of D
ListDir( C, Depth + 1 );
}
}
void ListDirectory( DirectoryOrFile D)
{
ListDir( D, 0);
}
算法逻辑简单易懂，即递归的访问节点的每一个儿子。
比起树，二叉树的应用往往更加广泛。除搜索外，还广泛应用于编译器的设计领域。
表达式树
既然提到”二叉树广泛应用于编译器的设计领域”，不如就好好唠唠。
首先要提到一个基础概念：计算机最喜欢后缀表达式。
后缀表达式又称逆波兰表达式，其最大的特点在于，运算符位于操作数之后，举例说明：
” 5 + 6 “的后缀表达式就是” 5 6 + “
” 1 + 2 + 3 “的后缀表达式就是” 3 2 1 + + “
运用后缀表达式进行计算的具体做法如下：
建立一个栈。从左到右读表达式，如果读到操作数就将它压入栈中，如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符运算，再将运算的结果代替原栈顶的n项，压入栈中 。如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。
对于计算机来说这会比我们输入的表达式(即中缀表达式)方便处理的多，然而将一个表达式反复转换为中缀和后缀是非常浪费时间的，同时存储一个式子的两个形式也很浪费空间。那么有没有一种数据结构可以解决这个问题呢？
答案是有的，即表达式树。
表达式树的叶节点是操作数，其他节点是操作符。假设所有的运算符都是双目运算符，那么刚好形成一颗二叉树。我们可以通过递归计算左子树和右子树的值，从而得到整个表达式树的值。
根据遍历方式的不同，我们能够通过一个表达式树获得这个式子的不同形式。
二叉树有三种遍历方式，分别为前序遍历，中序遍历和后序遍历，其区别就在于访问根节点的顺序。比如前序遍历就是先访问根节点，然后是左子树，最后是右子树。中序遍历则是先访问左子树，然后根节点，最后右子树。同理后序遍历就是最后访问根节点。
这里有一点需要注意，很明显不访问根节点就无法访问后续子树，所以这三种遍历本质上都是前序遍历，所谓的顺序不同，实际是指取出数据的顺序不同。
我们常用的遍历表达式树的方式是中序遍历和后序遍历。这样可以得到我们人喜欢使用的中缀表达式和计算机喜欢的后缀表达式。
由于中序表达式有时会出现逻辑混乱，故输出时可以加上括号以表明计算顺序。
