挑战408——数据结构（19）——树的遍历（先序，中序，后序）

树的存储结构

之前我们提到过堆是一棵特殊的树，在堆的存储方式中，我们选择了数组的方式去存储。因为只要知道一个节点的位置我们就能找到其他的节点的位置。但是前提是堆是一棵完全二叉树。树的结构多种多样，没人规定说一个节点只能有一个孩子。
我们先看下图，一个最简单的二叉树：

怎么表达？看到箭头，我们应该立马反应过来一个基本的工具，没错就是指针，应该立马反应过来一个数据结构，那就是链表！

把value换成我们的A B C,分别定义两个指针，一个指向左边的节点，一个指向右边的节点，其他的节点类似，就能把一棵二叉树表达出来了。很完美对吧。那么我们怎么用c++来描述这一个数据结构呢？代码如下：

struct Tree{
    string value;
    Tree *left;
    Tree *right;
};

代码对应的结构图应该是这样的：

那么三叉树呢？n叉树呢是不是也可以同样的方式来定义呢？当然！就先说说三叉树，其实三叉树就是在中间多了一个往下的箭头对吧，那么我们的数据结构按上面的结构，多用一个指向中间的指针不就完事了？看下图：

推广到n叉树：

但是对于N叉树我们通常不使用全部列出具体指针的方式，而是像上图一般，把这些指针存进一个vector中。
在实际的内存中，存储的结果是这样的：

树的遍历

这是一棵简单的二叉树，现在我们来看看什么叫树的遍历:
遍历树的节点并在每个节点执行一些操作的过程称为遍历或行走树(traversing or walking the tree)。在许多情况下，将需要按照数值的的顺序遍历树 这种处理在左右子树的递归调用之间的节点的方法被称为中序遍历（inorder traversal）。 另外还经常发生另外两种类型的树遍历，它们被称为前序遍历和后序遍历（preorder and postorder traversals）。

先序遍历（preOrder）

先序遍历的步骤就是：

• Do something
• Go left
• Go right

结合代码跟上面的树我们来讲解一下具体的步骤，为了便于观察，将用例的图都放上来

void preOrder(Tree *tree){
    if (tree == NULL) return; //如果树为空，直接返回函数，递归的simple case
    cout << tree -> value << endl;   //这里输出节点的数值
    preOrder(tree -> left);
    preOrder(tree -> right);
}

首先，判断树是否为空，是，则直接返回，否则进行下一步。先执行操作（这里是输出节点的值），为Grumpy，然后继续先序遍历节点的左子树，此时的tree指向的是doc节点，判断这子树是否为空？结果是否，因为doc下面还有子节点（孩子分别为Bashful和Dopey）,判断为否后执行操作，输出Doc，继续先序遍历，此时tree指向Bashful，判断这子树是否为空，结果为否！（这是个叶子，没有子节点，但是也是一棵孤立的树），执行输出操作，输出Bashful。继续执行先序遍历操作，此时指针指向Bashful的左孩子，由于它没有孩子，于是判断这子树为空，返回程序（return；）。此时指针往上回退，对右边进行先序遍历，输出Dopey。判断这个节点有无孩子，继续执行上述操作。这样子，我们可以看到先序遍历是先遍历左边的子树，再遍历右边的子树。输出为：

中序遍历（inOrder）

中序遍历的步骤为：

• Go left
• Do something
• Go right

用C++代码表示为：

void inOrder(Tree *tree){
    if (tree == NULL) return;
    inOrder(tree -> left);
    cout << tree -> value << endl;
    inOrder(tree -> right);
}

首先判断树是否为空，是直接返回，否则继续。继续中序遍历树的左节点，在这个例子中，一开始的指针指向的是Grumpy，因为树不为空，因此遍历它的左节点，也就是这个时候指针指向Doc，树仍然不为空，那么继续遍历其左节点，此时指针指向Bashful，此时bashful是个孤立的树叶，但仍是一棵子树。继续遍历其左子树，发现此时为空，程序直接返回上一级指针，也就是指向Bashful，并执行输出操作。接下来遍历其右节点，同理发现没有，指针回退到Doc，由于是由inOrder(tree -> left);回退而来，所以接下来输出Doc，然后执行inOrder(tree -> right)，指针指向Doc的右节点，也就是Dopey。过程同Bashful。完成后指针就会退至Grumpy。由于是由inOrder(tree -> left);回退而来，所以接下来输出Doc，然后执行inOrder(tree -> right)，指针此时指向Sleepy，树为空吗，否，指针继续往下，遍历左节点，也就是指针此时指向Happy，此时Happy是个孤立的树叶，但仍是一棵子树。继续遍历其左子树，发现此时为空，程序直接返回上一级指针，也就是指向Happy，并执行输出操作。然后重复上述的操作，得出结果应该是这样的：

后序遍历（postOrder）

步骤为：

• Go left
• Go right
• Do something

void postOrder(Tree * tree) {
    if(tree == NULL) return;
    postOrder(tree -> left);
    postOrder(tree -> right);
    cout<< tree->value << endl;
}

首先，指针指向Grumpy,判断树是否为空，是则返回，否则继续。后序遍历树的左节点，此时指针指向Doc，树为空吗？否，指针继续指向左子树，也就是Bashful。树仍然不为空，继续往下，发现左右子树都为空，立刻返回，然后输出该节点的值，也就是Bashful。指针往上返回，指向Doc，然后执行postOrder(tree -> right);此时指针指向Dopey，同上操作，输出Dopey。随后指针回退，指向Grumpy，此时树为空吗？否，遍历左边，输出Doc，然后遍历右边，指针指向Sleepy，此时树为空吗？否，继续遍历Happy，为空吗？否，查看树的左节点，为空，立刻返回，输出Happy，随后指针返回Sleep中，查看右节点，为空吗？否，遍历左右子树，为空，立刻返回，然后输出Sneezy，指针回退到Grumpy中，输出Sleepy，最后输出根节点。因此最终的结果为：

层次遍历（levelOrder）

考虑这样一个问题，如果我们需要将树的节点按顺序从左往右，依次按顺序输出（也就是一层一层输出），我们应该怎么办呢？能否按上述的步骤进行递归实现呢？唔。。。似乎不太容易，但是按顺序依次输出似乎让我们想到了什么？我们前面介绍过一种顺序数据结构，没错，就是我们的栈跟队列，显然这种情况我们选用队列好多了。我们要做的步骤为：

1. 将树装进我们的队列中，如果队列未空执行下列操作
2. 将树根移出队列
3. 对节点进行操作
4. 如果有左节点，进行出队列操作
5. 如果有右队列，进行出队列操作

这样，出队列的顺序就是树的层次顺序。代码为：

void levelOrder(Tree *tree) {
    Queue<Tree *>treeQueue; //建立一个队列存储树，类型为指向树的指针
    treeQueue.enqueue(tree);//将树装进我们的队列中
    while (!treeQueue.isEmpty()) { //判断树是否为空
        Tree *node = treeQueue.dequeue(); //定义一个Tree类型的指针，指向出队的节点
        cout << node->value << " ";  //输出该节点的值

       if (node->left != NULL) {     //如果存在左节点，将左节点移除
            treeQueue.enqueue(node->left);
        }
        if (node->right != NULL) {   //如果存在右节点，将右节点移除
            treeQueue.enqueue(node->right);
        }
    }
}

输出为：

再去做一下严蔚敏《数据结构(C语言版）》P129的那个表达式，能受益匪浅！！！

将上述的所有步骤都整成一个测试代码，就有下面的代码：

树的遍历方式（C++代码）

#include <iostream>
#include <string>
#include "Queue.h"  //我们之前实现过
using namespace std;

/*先建立二叉树的结构*/
struct Tree{
    string value; //数据
    Tree *left; //指向左节点的指针
    Tree *right;//指向右节点的指针
};
/*
 *再写一个将节点组装成的二叉树
 *因为我们是组装成树，所以返回类型肯定是Tree类型
 *我们指针指向Tree的根部，接收一个值
*/
Tree *makeTree(string value){
    Tree *t = new Tree; //在堆上建立一个Tree类型的数据结构
    t -> value = value;
    t -> left = NULL;
    t -> right = NULL; //这里我一开始写错了，写成left，导致调试了很久，最后找到，非语法错误真的是很致命
    return t;
}

/*
 *初始化树，将我们图画中的单词按要求插入
 *
 */
Tree *initTree(){
    Tree * root = new Tree;
    root->value = "this";
    root->left = makeTree("is");
    root->left->left = makeTree("a");
    root->left->right = makeTree("correctly");
    root->right = makeTree("written");
    root->right->right = makeTree("sentence.");
    return root;
}
//先序遍历
void preOrder(Tree * tree) {
    if(tree == NULL) {
        return;
    }
    cout << tree->value << " ";
    preOrder(tree->left);
    preOrder(tree->right);
}

//中序遍历
void inOrder(Tree * tree) {
    if(tree == NULL) {
        return;
    }
    inOrder(tree->left);
    cout << tree->value << " ";
    inOrder(tree->right);
}

//后序遍历
void postOrder(Tree * tree) {
    if(tree == NULL) {
        return;
    }
    postOrder(tree->left);
    postOrder(tree->right);
    cout << tree->value << " ";
}

//层次遍历
void levelOrder(Tree *tree) {
    Queue<Tree *>treeQueue;
    treeQueue.enqueue(tree);
    while (!treeQueue.isEmpty()) {
        Tree *node = treeQueue.dequeue();
        cout << node->value << " ";

        if (node->left != NULL) {
            treeQueue.enqueue(node->left);
        }
        if (node->right != NULL) {
            treeQueue.enqueue(node->right);
        }
    }
}

int main() {
    Tree * tree = initTree();
    cout << "1) Pre-order" << endl;
    cout << "2) In-order" << endl;
    cout << "3) Post-order (Yoda?)" << endl;
    cout << "4) Level-order" << endl << endl;
    int choice = -1;
    while (choice != 0) {
        cout << "请选择 1-4 (0 退出):" ;
        cin >> choice;
        switch (choice) {
        case 1: preOrder(tree); break;
        case 2: inOrder(tree); break;
        case 3: postOrder(tree); break;
        case 4: levelOrder(tree); break;
        }
        cout << endl << endl;
    }
    cout << "Goodbye!" << endl;
    return 0;
}

假设现在有一颗树的结构是这样的：

测试的结果如下：