二叉树的深度优先搜索_二叉树 深度优先搜索

（一）基本思想

分析：使用两个栈来存放节点元素，栈1用来存放未遍历过的节点，栈2用来存放遍历的节点。

具体步骤：
（1）把第一个节点压进栈1。见图（a）
（2）把栈1中的栈顶节点弹出，压进栈2；若栈1为空，且被弹出节点有子节点，则把被弹出节点的子节点按从右到左的顺序压进栈1。见图（b）
（3）重复步骤2，直至栈1为空。见图（c）~图（h）
（4）至此，遍历过程结束。遍历顺序就是栈2中节点的入栈顺序。

（二）C++实现代码

#include <iostream>
#include <stack>
using namespace std;

struct node
{
    int data;
    node *left;
    node *right;
};

void dfs(int a[], int size)
{
    stack<node *> visited, unvisited;
    node nodes[size];
    node *current;

    // 构建二叉树
    for(int i = 0; i < size; i++)
    {
        nodes[i].data = a[i];
        // 左子节点
        int child = 2 * i + 1;
        if(child < size)
        {
            nodes[i].left = &nodes[child];
        }
        else
        {
            nodes[i].left = NULL;
        }

        // 右子节点
        child++;
        if(child < size)
        {
            nodes[i].right = &nodes[child];
        }
        else
        {
            nodes[i].right = NULL;
        }
    }

    // 先把第0个节点加到unvisited栈中
    unvisited.push(&nodes[0]);
    while (!unvisited.empty())
    {
        current = unvisited.top();
        unvisited.pop();

        if(NULL != current->right)
        {
            // 把右子节点先压入unvisited栈，因为右子节点的访问次序在左子节点之后
            unvisited.push(current->right);
        }

        if(NULL != current->left)
        {
            unvisited.push(current->left);
        }

        visited.push(current);

        cout << current->data << "  ";
    }
}

int main(int argc, const char * argv[])
{
    int a[] = {0, 1, 2, 3, 4, 5, 6};
    int size = sizeof(a)/sizeof(int);
    dfs(a, size);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

运行结果：

0  1  3  4  2  5  6
1