开发中虚函数应用，大大减少开发时间

树的应用非常广泛，比如，数据库就是由树构造而成的，C编译器的词法分析器也是经过语法分析生成的树。

树是一种管理象树干、树枝、树叶一样关系的数据的数据结构，通常一棵树由根部长出一个树干，接着从树干长出一些树枝，然后树枝上又长出更小的树枝，而叶子则长在最细的树枝上，树这种数据结构正是象一棵树倒过来的树木。

树是由结点（顶点）和枝构成的，由一个结点作为起点，这个起点称为树的根结点。从根结点上可以连出几条枝，每条枝都和一个结点相连，延伸出来的这些结点又可以继续通过枝延伸出新的结点。这个过程中的旧结点称作父结点，而延伸出来的新结点称作子结点，一个子结点都没有的结点就叫做叶子结点。另外，从根结点出发到达某个结点所要经过的枝的个数叫做这个结点的深度。

从家谱树血缘关系来看，家谱树使得介绍计算机科学中用于描述树结构的术语变得更简单了。树中的每一个结点都可以有几个孩子，但是只有一个双亲。在树中祖先和孙子的意义与日常语言中的意义完全相同。

与根形成对比的是没有孩子的结点，这些结点称为叶，而既不是根又不是叶的结点称为内部结点，树的长度定义为从根到叶的最长路径的长度（或深度）。在一颗树里，如果从根到叶的每条路径的长度都大致相等，那么这颗树被称为平衡树。实际上，要实现某种永远能够保证平衡的树是很复杂的，这也是为什么存在多种不同种类的树的原因。

实际上，在树的每一层次都是分叉形式，如果任意选取树中的一个结点和它的子树，所得到的部分都符合树的定义。树中的每个结点都可以看成是以它自己为根的子树的根，这就是树结构的递归特性。如果以递归的观点考察树，那么树只是一个结点和一个附着其上的子树的集合——在叶结点的情景下该集合为空，因此树的递归特性是其底层表示和大部分针对树操作的算法的基础。

树的一个重要的子类是二叉树，二叉树是一种常用的树形数据结构。二叉树的每个结点最多只有两个子结点（left和right），且除了根以外的其它结点，要么是双亲结点的左孩子，要么是右孩子。

>>> 1.1.2 表达式算术树

1. 问题

求解算术表达式就是一种二叉树，它的结点包含两种类型的对象：操作符和终值。操作符是拥有操作数的对象，终值是没有操作数的对象。表达式树背后的思想——存储在父结点中的是操作符，其操作数是由子结点延伸的子树组成的。操作数有可能是终值，或它们本身也可能是其它的表达式。表达式在子树中展开，终值驻留在叶子结点中，这种组织形式的好处是可以通过表达式将一个表达式转换为3种常见的表示形式：前缀、中缀和后缀，但中缀表达式是在数学中学到的最为熟悉的表达方式。在这里，将以2*（3+4）+5中缀表达式算术树结构为例。

首先将"2*（3+4）+5"拆分为左子树和右子树，其中，"+" 为根节点，左子树的值为2*（3+4），右子树的值为5；接着将2*(3+4)拆分为左子树和右子树，其中，"*"为根节点，左子树的值为2，右子树的值为3+4；然后将3+4拆分为左子树和右子树，其中，"+"为根节点，左子树的值为3，右子树的值为4，详见图 4.6。注意，树的表示法中不需要任何小括号或运算符优先级的知识，因为它描述的计算过程是唯一的。

图 4.6 表达式算术树

由此可见，从根结点（Node）到叶进行分析，该表达式算术树的结点是算术运算符"+（Additive）"和"*（Multiplicative）"，它的树叶是操作数（Number）。由于这里所有的操作都是二元（Binary）的，即每个结点最多只有两个孩子，这颗特定的树正好是二叉树。因此可以用以下方式计算（calculate，简写为calc）每个结点：

● 如果是一个数字，则返回它的值；

● 如果是一个运算符，则计算左子树和右子树的值。

其计算过程是先分别输入3和4，接着计算3+4；然后输入2，再接着计算2*(3+4)；接着输入5，最后计算2*(3+4)+5。

传统的做法是定义一个struct _Node，包含二元运算符和数字结点，详见程序清单 4.12。

程序清单 4.12 表达式算术树接口（calctree.h）

1    #pragma once 

2

3    #define NUM_NODE    1 

4    #define ADD_NODE     2