在计算机数据结构中，树(Tree)结构是基础的结构之一，对于其定义、实现以及相关算法在一般的算法与数据结构书中都有详细介绍和分析。不过本文还是想要罗列一下树结构基本的遍历算法，同时简单随机介绍各种遍历算法的使用情境。
本文中将会实现树遍历主要两种方式：深度优先和广度优先。对于深度优先也会包括其三种不同方式：前序遍历、中序遍历、后续遍历。同时对于深度优先的三种方式还会包括最简单直观的递归实现，和相对复杂的迭代实现。
为方便起见文中的算法将基于二叉树(Binary Tree)结构，其树节点的结构也简单定义如下：
[codesyntax lang=”cpp” lines=”normal”]
using namespace std;
class Node {
public:
Node *left;
Node *right;
int value;
};
[/codesyntax]
深度优先遍历
深度优先遍历隐藏着回溯法(Backtracking)应用，因此利用递归自动创建堆栈(stack)的性质，就可以非常好的实现这些遍历算法。虽然递归可以通过创建自定义的栈对象来变成迭代，但对于进栈出栈的控制，三种遍历方式有着不同的条件，因而实现反而变得复杂。
递归实现
对于节点的访问操作，定义了如下的方法，其实只是简单的输出节点的值再以空格分隔。对于空节点也将预留输出特别的符号来指示。
[codesyntax lang=”cpp” lines=”normal”]
#define NULL_NODE "#"
void operate(Node *node) {
if (node == NULL) {
// cout << (NULL_NODE" ");
} else {
cout << node->value << " ";
}
}
[/codesyntax]
三种深度优先遍历的算法实现如下
[codesyntax lang=”cpp” lines=”normal”]
void preorder(Node *node) {
if (node == NULL) {
operate(NULL);
return;
}
// operate node before any children
operate(node);
preorder(node->left);
preorder(node->right);
}
void inorder(Node *node) {
if (node == NULL) {
operate(NULL);
return;
}
inorder(node->left);
// operate node in the middle of children
operate(node);
inorder(node->right);
}
void postorder(Node *node) {
if (node == NULL) {
operate(NULL);
return;
}
postorder(node->left);
postorder(node->right);
// operate node after all child
operate(node);
}
[/codesyntax]
可以看到三个算法的实现几乎一模一样，都是对子节点一次递归调用遍历方法，唯一的区别只是在于访问自身节点的位置不同：前序在所有节点之前，后序在所有节点之后，中序则是在两节点之间。
不过中序遍历也只对二叉树有意义，因为对于多个子节点的树结构来说，中间的位置在哪里很难定义。
下边来说说三个遍历的应用情况：
前序遍历因为在所有节点之前访问当前节点，所以常用来创建树结构，通过优先创建父节点，才能在创建子节点时确保其能找到父节点的位置。
后续遍历则正好相反，多用在销毁树结构的时候，这样每次销毁的节点都只是叶子节点，保持了树的相对完整性，而不会从一棵树变成多棵小子树。
中序遍历就比较有趣了，如果将树节点的内容按中序遍历输出，就会发现对任意节点的左子树的内容都会在其左侧，而右子树的内容则全都在其右侧。对于一棵二叉查找树(Binary Search Tree)，其中序遍历的输出结果就正好是一个有序的数字(因此这也是验证一棵二叉树是不是二叉查找树的方法)。所以通过中序遍历，就可以创建额外的索引了指示直接前序节点和直接后序节点，这样就可以方便的在树结构上实现基于中序遍历的迭代器(Iterator)了。
迭代实现
前序遍历的非递归实现非常的简单，唯一要注意的是在进栈是要先进右子节点再进左子节点：
[codesyntax lang=”cpp” lines=”normal”]
void preorderWithStack(Node *root) {
stack<Node *> nodeS;
nodeS.push(root);
while (!nodeS.empty()) {
Node *node = nodeS.top();
nodeS.pop();
operate(node);
if (node == NULL) {
continue;
}
// Push right node to stack first, as left should pop out first
nodeS.push(node->right);
nodeS.push(node->left);
}
}
[/codesyntax]
可以看到无论节点是否为空，都先放入栈中，在出栈时才查是否是空节点。这种实现方式也跟之前递归的实现完全一致。不过也可以在入栈钱判定空节点，这样可以减少出入栈的次数，也减少内存使用。
[codesyntax lang=”cpp” lines=”normal”]
void preorderWithStack2(Node *root) {
if (root == NULL) {
return;
}
stack<Node *> nodeS;
nodeS.push(root);
while (!nodeS.empty()) {
Node *node = nodeS.top();
nodeS.pop();
operate(node);
// Push right node to stack first, as left should pop out first
if (node->right != NULL) {
nodeS.push(node->right);
}
if (node->left != NULL) {
nodeS.push(node->left);
}
}
}
[/codesyntax]
中序遍历的非递归实现就有些复杂了，不过根据“先输出左子树” 这一条件，就明白需要不停地将左子节点如栈，直到遇到空节点为止。然后就可以出栈一个节点进行操作，之后将转向其右子节点：
[codesyntax lang=”cpp” lines=”normal”]
void inorderWithStack(Node *root) {
stack<Node *> nodeS;
Node *node = root;
while (node != NULL || !nodeS.empty()) {
// Push nodes until find current left-most node
while (node != NULL) {
nodeS.push(node);
node = node->left;
}
if (!nodeS.empty()) {
node = nodeS.top();
nodeS.pop();
// Inorder visit current node,
operate(node);
// then move to its right childrens.
node = node->right;
}
}
}
[/codesyntax]
后序遍历的非递归实现就更加复杂了，因为当前节点进栈等待左子树都操作完了还不能出栈，还要等右子树操作之后才行，而这条件很难判定。观察前序遍历和后序遍历的递归实现可以发现，如果从下往上看后序遍历的遍历过程，其实跟前序遍历的遍历过程极其相似，只是后序遍历从下往上看是先访问右子树再访问左子树。
另外通过小小验证也不难发现，其实后序遍历的结构，相当于前序遍历访问左右子树的顺序互换，再把最后的结构前后反一下就可以了。所以可以使用子节点顺序互换的前序遍历把结构先输入到临时数组中，再把数组中的结构从尾到头再输出出去即可。这里的数组可以用另一个栈对象。
[codesyntax lang=”cpp” lines=”normal”]
void postorderWithStack(Node *root) {
if (root == NULL) {
return;
}
stack<Node *> nodeS;
stack<Node *> stackR; // Result stack
nodeS.push(root);
while (!nodeS.empty()) {
Node *node = nodeS.top();
nodeS.pop();
// save node to result stack
stackR.push(node);
// Push left node to stack first
if (node->left != NULL) {
nodeS.push(node->left);
}
if (node->right != NULL) {
nodeS.push(node->right);
}
}
while (!stackR.empty()) {
Node *node = stackR.top();
stackR.pop();
operate(node);
}
}
[/codesyntax]
这个实现显然要比前序遍历所占的内存要高，不仅仅因为这个实现用了两个栈对象，还因为第二个栈要把所有的结果都保存下来，因此空间复杂度就成了O(n)，其中n表示树中节点的数量。而其他两种的实现方式空间复杂度其实只有O(l)，l代表的是树的层数。
结合中序遍历的实现，其实只需要在节点将要出栈时判定其右子树是否已经访问完毕，在决定是否出栈该节点进行访问。如果只是完成了左子树访问，那么就其留在堆栈中，再做个标记表明该节点已经开始右子树的访问。这里用了一个集合了作为标示。
[codesyntax lang=”cpp” lines=”normal”]
void postorderWithStack2(Node *root) {
stack<Node *> nodeS;
unordered_set<Node *> ready;
Node *node = root;
while (node != NULL || !nodeS.empty()) {
// Push nodes until find current left-most node
while (node != NULL) {
nodeS.push(node);
node = node->left;
}
if (!nodeS.empty()) {
node = nodeS.top();
if (ready.count(node) > 0) {
nodeS.pop();
ready.erase(node);
operate(node);
node = NULL;
} else {
ready.insert(node);
// then move to its right chirens.
node = node->right;
}
}
}
}
[/codesyntax]
这个的空间复杂度差不多是2个O(l)，因此依然还是O(l)。在引用列表中也有一片文章介绍了只使用一个栈的实现方式，非常巧妙地判定右子树有没访问完毕，当然空间复杂基本与上述实现差不多。
广度优先遍历
深度优先遍历是基于栈的后进先出因此有递归和迭代两种方式，而广度优先遍历则是依照队列的先进先出，因而只有一种靠自己维护队列来实现：
[codesyntax lang=”cpp” lines=”normal”]
void levelorder(Node *root) {
if (root == NULL) {
return;
}
queue<Node *> nodeQ;
nodeQ.push(root);
while (!nodeQ.empty()) {
Node *node = nodeQ.front();
nodeQ.pop();
operate(node);
// push children if exist
if (node->left != NULL) {
nodeQ.push(node->left);
}
if (node->right != NULL) {
nodeQ.push(node->right);
}
}
}
[/codesyntax]
对比前序遍历，可以看出两者非常相似，只是在存储节点的数据结构上一个用的是栈一个是队列。
应用访问者模式
最后简单介绍一下访问者模式在树结构遍历中的应用。之前的实现可以看到对于节点的操作是事先定义好的，这样就没有扩展性，想要对不同的树结构有不同的操作就要事先额外的遍历方法。引入访问者模式，就只需要实现相关的方法即可。
[codesyntax lang=”cpp” lines=”normal”]
class NodeVisitor {
public:
virtual void preorder(Node *node);
virtual void inorder(Node *node);
virtual void postorder(Node *node);
};
void depthfirst(Node *node, NodeVisitor& visitor) {
if (node == NULL) {
return;
}
visitor.preorder(node);
depthfirst(node->left, visitor);
visitor.inorder(node);
depthfirst(node->left, visitor);
visitor.postorder(node);
}
[/codesyntax]
如果将节点和遍历方法都定义成模板的形式，还能做到进一步的抽象，不过这不在文章讨论范围了。
1 Comment