数据结构和算法(树Tree)

树

概述:

树的遍历

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

我们可以通过中序遍历得到一个递增的有序序列

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

值得注意的是，当你删除树中的节点时，删除过程将按照后序遍历的顺序进行。 也就是说，当你删除一个节点时，你将首先删除它的左节点和它的右边的节点，然后再删除节点本身。另外，后序在数学表达中被广泛使用。 编写程序来解析后缀表示法更为容易.

层序遍历

层序遍历就是逐层遍历树结构。

广度优先搜索

是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。

当我们在树中进行广度优先搜索时，我们访问的节点的顺序是按照层序遍历顺序的。

运用递归解决树的问题

树可以以递归的方式定义为一个节点（根节点），它包括一个值和一个指向其他节点指针的列表。 递归是树的特性之一。 因此，许多树问题可以通过递归的方式来解决。 对于每个递归层级，我们只能关注单个节点内的问题，并通过递归调用函数来解决其子节点问题。

“自顶向下” 的解决方案

可以被认为是一种前序遍历“自顶向下” 意味着在每个递归层级，我们将首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。

“自底向上” 的解决方案

“自底向上” 是另一种递归方法。 在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。 这个过程可以看作是后序遍历

总结

总结

了解递归并利用递归解决问题并不容易。

当遇到树问题时，请先思考一下两个问题：

你能确定一些参数，从该节点自身解决出发寻找答案吗？

你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗？

如果答案都是肯定的，那么请尝试使用 “自顶向下” 的递归来解决此问题。

或者你可以这样思考：对于树中的任意一个节点，如果你知道它子节点的答案，你能计算出该节点的答案吗？ 如果答案是肯定的，那么 “自底向上” 的递归可能是一个不错的解决方法。