二叉树的深度优先遍历

刺骨的言语ヽ痛彻心扉 2022-02-28 08:18 236阅读 0赞

# [二叉树的深度优先遍历][Link 1] #

\--- 欢迎指正---

今天继续树的遍历。 这里要说的是 二叉树的 深度优先遍历。

深度优先遍历：从根结点开始，先遍历根的左子树，再遍历根右子树。以此类推输出结果。如下图：

![1630599-20190323074354104-1491516131.png][]

深度优先结果： 5 、3、1、4、7、9

分析：

1、先将5入栈， 此时栈中只有5一个元素。

2、将占栈中的5弹栈，在将其右孩子7压栈，此时栈中只有7一个元素。

3、再将右孩子3入栈，此时栈中栈顶到栈底的顺序是：3、7。

4、此时在弹栈， 重复2、3步骤，直到遍历结束

结点的结构：

struct node 
    {
        // 数据域
        int data;
    
        // 左节点
        node *lc;
    
        // 右结点
        node *rc;
    
        // 构造函数
        node()
            : data(0)
            , lc(NULL)
            , rc(NULL)
        {
        }
    };

深度优先遍历函数：

// 3-23-2019 07:11 新增深度优先遍历
        void dfs()
        {
            cout <<  endl << endl << "深度优先遍历" << endl;
    
            stack<node*> vs;
    
            // 思路： 先将根结点入栈，再将其右孩子入栈，再将其左孩子入栈。一次遍历输出
            if (NULL != root)
                vs.push(root);
            
    
            node *tmp_node = NULL;
            while (false == vs.empty())
            {
                tmp_node = vs.top();
                cout << tmp_node->data << " -> ";
    
                // 弹出已经输出的元素
                vs.pop();
    
                // 将其右孩子入栈
                if (NULL != tmp_node->rc)
                    vs.push(tmp_node->rc);
                
                // 再将其左孩子入栈
                if (NULL != tmp_node->lc)
                    vs.push(tmp_node->lc);
            }
        }

测试结果：

![1630599-20190323073549572-1686524448.png][]

GitHub 地址： [https://github.com/mohistH/base\_data\_structure][https_github.com_mohistH_base_data_structure]

posted @ 2019-03-23 07:48 [mohist][] 阅读( ...) 评论( ...) [编辑][Link 2] 收藏

[Link 1]: https://www.cnblogs.com/pandamohist/p/10582420.html
[1630599-20190323074354104-1491516131.png]: /images/20220228/adbe4f1bb290462d8ffa6aa636b36746.png
[1630599-20190323073549572-1686524448.png]: /images/20220228/8fd1a19a445a4517949929356d7632ec.png
[https_github.com_mohistH_base_data_structure]: https://github.com/mohistH/base_data_structure
[mohist]: https://www.cnblogs.com/pandamohist/
[Link 2]: https://i.cnblogs.com/EditPosts.aspx?postid=10582420