数据结构：二叉树

gaunthan Posted on Jan 5 2017

? Data Structures ?

## 概述
**二叉树**(Binary Tree)是一棵树，其中每个节点都不能有多于两个的儿子，即结点的出度最多为2。除此以外，对于一个有两个孩子的结点，二叉树区分这两个结点，分别将它们称为左孩子和右孩子。交换两个孩子的顺序，将得到一棵不等的二叉树。

## 性质
二叉树的平均深度要比N小得多（N是树的结点数），这个平均深度为$O(\sqrt N)$。而对于特殊类型的二叉树，如**二叉查找树**(Binary Search Tree)，其深度的平均值是$O(log N)$。

一棵二叉树的示例如下：

![](https://leanote.com/api/file/getImage?fileId=5872478eab6441209e017c5b)

两棵子树T_L和T_R可以是空树。

## 实现
因为一棵二叉树最多有两个儿子，所以可以用指针直接指向它们。树节点的声明在结构上类似于双链表的声明，在声明中，一个节点就是由关键字加上两个指向其他结点的指针组成的结构：

```C
/* Put in header file. */
typedef int ElemType;

struct BinTreeNode;
typedef struct BinTreeNode* BinTree;

/* Put in implement file. */
struct BinTreeNode {
    ElemType elem;
    struct BinTreeNode* left;
    struct BinTreeNode* right;
};
```

## 特殊的二叉树
特殊的二叉树有很多，如下图所示：

![](https://leanote.com/api/file/getImage?fileId=5872478eab6441209e017c5a)

## 表达式树
二叉树的一个应用是表达式树，在编译过程的语法分析阶段将生成一棵语法树，它就是一棵表达式树。

**表达式树**（expression tree）的树叶是操作数（operand），比如常量或变量，而其他的节点为 操作符（operator）。

通过递归计算左子树和右子树所得到的值应用在根处的运算符操作中可以算出表达式树 T 的值。示例如下：

![](https://leanote.com/api/file/getImage?fileId=5872478eab6441209e017c59)

### 表达式树的三种遍历结果

- 前缀表达式（prefix expression）
先打印出运算符，然后递归地打印出左子树和右子树。其结果" + + a * b c * + * d e f g" 是不太常用的前缀表达式。
这种遍历策略（节点，左，右）称为先序遍历（preorder traversal）。

- 中缀表达式（infix expression）
通过递归产生一个带括号的左表达式，然后打印出在根处的运算符，最后再递归地产生一个带括号的右表达式而得到一个中缀表达式。
这种遍历策略（左，节点，右）称为中序遍历（inorder traversal）。

- 后缀表达式（postfix expression）
递归打印出左子树、右子树，然后打印运算符。如果应用这种策略于上面的树，则输出将是后缀表达式 "a b c * + d e * f + g * +"。
这种遍历策略（左，右，节点）称为后序遍历（postorder traversal）。

### 表达式树的构建
#### 后缀表达式构建表达式树
一次一个符号地读入表达式：

* 如果符号是操作数，那么就建立一个单节点树并将一个指向它的指针压入栈中；
* 否则，如果符号是操作符，那么就从栈中弹出指向两棵树$T_1$和$T_2$的那两个指针（$T_1$的先弹出）并形成一棵新的树。该树的树根就是操作符，它的左右儿子分别指向$T_2$和$T_1$。然后将这棵新树的根指针压入栈中。