实现树结构的基本算法和相应的数据结构( 二 ) _树结构

def traverse(tree):if tree is not empty:process data at tree’s root# preorder traversaltraverse(tree’s left subtree)traverse(tree’s right subtree)把这个算法应用于图7.2里的树的话，节点将会按照2、7、5、3、6、8、4这样的顺序进行处理。
当然，我们也可以通过简单地移动实际处理数据的位置来修改遍历算法。中序遍历（inorder traversal）将会在处理两个子树之间的时候处理根节点的数据。对于我们那个例子里的树，中序遍历将会按照7、3、5、2、8、6、4的序列来处理节点。你现在可能已经猜到了，后序遍历（postorder traversal）会在处理完两个子树之后再去处理根节点，这就给了我们这样一个顺序：3、5、7、8、4、6、2 。
7.3　示例应用程序：表达式树树在计算机科学中的一个重要应用是存储程序的内部结构。当解释器或编译器分析程序的时候，它会构造一个用来提取程序结构的解析树（parse tree）。例如，考虑这样一个简单的表达式：(2 + 3) * 4 + 5 * 6 。这个表达式可以用图7.4所示的树的形式来表现。可以仔细看看，树的层次结构是怎么消除对括号的需要的。表达式的基本操作数是树的叶节点，而运算符是树的内部节点。在树的低层级里的操作必须要被优先执行，只有这样它的结果才能够被用在更高层级的表达式里。很明显，加法2 + 3必须是第一个需要执行的操作，这是因为它出现在了树的最底层。

文章插图

图7.4　数学表达式的树呈现
将表达式表现为树结构之后，我们就能够做很多有趣的事情了。编译器将遍历这个结构来生成执行计算的一系列机器指令。解释器也会使用这个结构来执行这个表达式。它可以获取两个子节点的值，再使用这个操作来计算出每个节点的值。如果其中的一个或两个子节点本身是一个运算符，那么就必须要先对这个子节点进行计算。一个简单的树的后序遍历就能够被用来计算表达式：

def evaluateTree(tree):if tree’s root is an operand:return root dataelse:# root contains an operatorleftValue = https://www.isolves.com/it/cxkf/sf/2020-06-01/evaluateTree(tree’s left subtree)rightValue = evaluateTree(tree’s right subtree)result = Apply operator at root to leftValue and rightValuereturn result

如果你够仔细的话，你会发现这个算法其实是一个用来计算表达式的后缀版本的递归算法。简单地进行后序遍历，这个表达式树会产生这个序列：2 3 + 4 * 5 6 * + 。而这正好是我们最初的表达式的后缀表示法。在第5章里，我们用了一个堆栈的算法来计算后缀方程。在这里，通过利用递归隐式地使用计算机的运行时堆栈，我们也完成了相同的任务。顺便说一句，你也可以通过执行恰当的遍历，来获取表达式的前缀版本和中缀版本。当这一切的知识都相互交织在一起的时候，难道不令人着迷吗？
7.4　树的存储方式现在，你已经了解了树可以做什么，接下来考虑一下树可能的具体存储方式。构建树的一种简单明了的方法是使用链接来表示。和我们处理链表一样，我们可以创建一个类来表示树的节点。每个节点都有一个实例变量来保存对节点数据的引用，同时还有用来引用左右子节点的变量。我们将使用None对象来表示空子树。于是，我们有了这样一个Python的类：

# TreeNode.pyclass TreeNode(object):def __init__(self, data = https://www.isolves.com/it/cxkf/sf/2020-06-01/None, left=None, right=None):"""creates a tree node with specified data and references to leftand right children"""self.item = dataself.left = leftself.right = right

使用这个TreeNode类，就能够很方便地直接像镜像一样创建我们已经看到过的二叉树图的链式结构。比如，下面这段代码就可以构建一个包含3个节点的简单树：
left = TreeNode(1)right = TreeNode(3)root = TreeNode(2, left, right)通过简单地对TreeNode类的构造函数进行组合调用，我们也可以用一行代码来达到相同的目的：
root = TreeNode(2, TreeNode(1), TreeNode(3))更进一步，我们甚至可以利用这种方法来创建各个树的节点，从而构建出任意复杂度的树结构。下面这段代码可以创建出类似于图7.2这样的树结构：
root = TreeNode(2,TreeNode(7,None,TreeNode(5,TreeNode(3),None))TreeNode(6,TreeNode(8),TreeNode(4)))这里使用了缩进来帮助我们直观地让表达式的布局与树的结构相匹配。比如说，从例子里我们可以看到，在根节点（2）的下面，有两个缩进的子树（7和6）。如果你觉得这样并不是很直观的话，可以试着把头侧着看这段代码。