二叉树的深度优先搜索

水深无声 2022-06-09 09:58 163阅读 0赞

## （一）基本思想 ##

![bitree.png][]

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

![bitree-dfs.jpg][]

具体步骤：  
（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;
    }

运行结果：

0  1  3  4  2  5  6

[bitree.png]: /images/20220609/74ed23bb3c6a4eb9be8202de21d4b684.png
[bitree-dfs.jpg]: /images/20220609/1c56caec5ac84bf6a5473e889f1a58f8.png