数据结构与算法分析笔记——树，二叉树，表达式树

数据结构与算法分析笔记——树，二叉树，表达式树

树

树和表、栈或队列等一样，也是一种数据结构。我们先来普及树这种数据结构中，常见的一些概念。

树：一棵树是一系列节点的集合，可以是空集。若不是空集，则由一个根节点以及0或多个子树构成。一棵树的每个子树的根，都由一条来自根r的有向的边连接。

儿子/父亲：子树的根称之为根r的儿子，r是每棵子树的根的父亲。

树叶：没有儿子的节点称之为树叶。

兄弟：拥有相同父亲的节点称之为兄弟节点。

祖父/孙子：有了父子关系，自然可以找到祖父和孙子，或者还可以更上，或者更下。

边：前面提到过，从父节点到子节点的连接线称之为边。

路径：从节点n1到节点nk，可以找到一系列节点，如n1，n2，……，nk。令i为满足 1

深度：节点的尝试等于根到该节点的路径的长。

高：如果一个树的某个树叶的深度是该树所有树叶中最长或之一，那么，该树叶的深度即为该树的高度。

祖先/后裔：从n1到n2，如果存在一条路径，则n1为n2的祖先，n2为n1的后裔。

真祖先/真后裔：互为祖先/后裔关系的两个节点，如果它们不是同一个节点，我们称之为真祖先或真后裔。

树的实现

充分理解了树以后，我们可以通过程序来实现一棵树。一种方案是，在每个节点上增加若干额外的链，这样，使得节点的每个儿子都有一个链指向它。然后，由于每个节点的儿子数是变化的，事先不知道，所以，这种方式会造成太多的空间浪费。

另一种可行方案是，每个节点都保存一个指向第一个子节点的链和指向下一个兄弟节点的链。如下：

基于这种实现方式，如果想要遍历一个树的所有节点，有以下两种方式：

先序遍历：从根节点出发，先处理根节点的信息，再向下找到子节点，处理子节点的信息。

后序遍历：从根节点出发，先向下找到子节点，处理完子节点的信息，再回过头来处理根节点。

两种遍历方式我们在二叉树中的学习中会有更深的体会。

二叉树

每个节点的子节点都不多于两个的树，我们称之为二叉树。

代码实现如下：

表达式树

表达式树是一棵特殊的二叉树，它的根是操作符，树叶是操作树。我们以表达式树为例，来学习一下树的各种遍历方式。如下，即是一个表达式树：

先序遍历

先序遍历是先处理根节点，再处理子节点，那么，对于上述表达式树，先序遍历的结果如下：

a * b c * + * d e f g

加上适当的括号帮助阅读，如下：

( + ( a * ( b c ) ) ( * ( + ( * ( d e) f ) g) )

后序遍历

后序遍历是先处理叶子节点，再处理根节点，结果如下：

a b c * + d e * f + g * +

加上适当的括号帮助阅读，如下：

后序遍历是先处理叶子节点，再处理根节点，结果如下：

( a ( b c ) * + ) ( ( ( d e ) * f ) + g ) * +

中序遍历

我们发现，无论是先序还是后序，得到的结果似乎都不是那么易读，事实上，对于二叉树来说，还有一种特殊的中序遍历方式。表达式树如果采用中序遍历的话，结果将会是易读的。

中序遍历的操作方式是先遍历左节点，再到根节点，再到右节点，结果如下：

a + b * c + d * e + f * g

加上适当的括号帮助阅读，如下:

( a + ( b * c ) ) + ( ( ( d * e ) + f ) * g )

我们发现，中序遍历果然是非常适合表达式树，这样得到的表达式，非常符合我们已有的数学知识体系，如果把abc换成数字，我们可以直接计算出表达式的结果。

构造表达式树

将树读取成表达式，采用中序遍历得到的结果最为易读，但是，如果说要把一个表达式还原成树，你会发现，后序遍历得到的结果最容易还原，接下来，我们就来尝试把一个后序遍历得到的结果还原成树。

a b + c d e + * *

对于后序表达式来说，我们可以找到规律如下：

操作符a向前，最近的两个元素如果是操作数b和c，那么，在树中，b和c一定是c的子节点。

操作符a向前，最近的两个元素中如果包含操作符d，那么，在树中，以d为根的子树一定是以a为根的树的子树，且d一定是a的子节点。

通过栈这种数据结构，可以帮助我们把后序遍历得到的后缀表达式，还原成树。

过程如下：

依次读取表达式中的每个元素。

如果得到的是操作数，将该操作数压入栈中。

如果得到是的操作符，将栈中之前的两个元素弹出，和操作符形成一个树，将该树作为一个整体元素压入栈中。

继续读取元素并按2或3处理，直到结束。