Algorithm Analysis(算法分析)

在计算机数据结构中，树(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]
Read More →