當前位置：首頁 > 编程语言 > c/c++ >内容正文

c/c++

矮油~ 二叉树的深度优先遍历与广度优先遍历 [ C++ 实现 ]

發布時間：2023/12/15 c/c++ 40 豆豆

生活随笔收集整理的這篇文章主要介紹了矮油~ 二叉树的深度优先遍历与广度优先遍历 [ C++ 实现 ] 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

深度優先搜索算法（Depth First Search），是搜索算法的一種。是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。

當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。

如果還存在未被發現的節點，則選擇其中一個作為源節點并重復以上過程，整個進程反復進行直到所有節點都被訪問為止。

如右圖所示的二叉樹：

A 是第一個訪問的，然后順序是 B、D，然后是 E。接著再是 C、F、G。

那么，怎么樣才能來保證這個訪問的順序呢？

分析一下，在遍歷了根結點后，就開始遍歷左子樹，最后才是右子樹。

因此可以借助堆棧的數據結構，由于堆棧是后進先出的順序，由此可以先將右子樹壓棧，然后再對左子樹壓棧，

這樣一來，左子樹結點就存在了棧頂上，因此某結點的左子樹能在它的右子樹遍歷之前被遍歷。

深度優先遍歷代碼片段

//深度優先遍歷

void?depthFirstSearch(Tree root){

????stack<Node *> nodeStack;??//使用C++的STL標準模板庫

????nodeStack.push(root);

????Node *node;

????while(!nodeStack.empty()){

????????node = nodeStack.top();

????????printf(format, node->data);??//遍歷根結點

????????nodeStack.pop();

????????if(node->rchild){

????????????nodeStack.push(node->rchild);??//先將右子樹壓棧

????????}

????????if(node->lchild){

????????????nodeStack.push(node->lchild);??//再將左子樹壓棧

????????}

????}

}

　　廣度優先搜索算法（Breadth First Search），又叫寬度優先搜索，或橫向優先搜索。

是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則算法中止。

如右圖所示的二叉樹，A 是第一個訪問的，然后順序是 B、C，然后再是 D、E、F、G。

那么，怎樣才能來保證這個訪問的順序呢？

借助隊列數據結構，由于隊列是先進先出的順序，因此可以先將左子樹入隊，然后再將右子樹入隊。

這樣一來，左子樹結點就存在隊頭，可以先被訪問到。

廣度優先遍歷代碼片段

//廣度優先遍歷

void?breadthFirstSearch(Tree root){

????queue<Node *> nodeQueue;??//使用C++的STL標準模板庫

????nodeQueue.push(root);

????Node *node;

????while(!nodeQueue.empty()){

????????node = nodeQueue.front();

????????nodeQueue.pop();

????????printf(format, node->data);

????????if(node->lchild){

????????????nodeQueue.push(node->lchild);??//先將左子樹入隊

????????}

????????if(node->rchild){

????????????nodeQueue.push(node->rchild);??//再將右子樹入隊

????????}

????}

}

　　完整代碼:

/**

?* <!--

?* File?? : binarytree.h

?* Author : fancy

?* Email? : fancydeepin@yeah.net

?* Date?? : 2013-02-03

?* --!>

?*/

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

#include <Stack>

#include <Queue>

using?namespace?std;

#define Element char

#define format "%c"

typedef?struct?Node {

????Element data;

????struct?Node *lchild;

????struct?Node *rchild;

} *Tree;

int?index = 0;??//全局索引變量

//二叉樹構造器,按先序遍歷順序構造二叉樹

//無左子樹或右子樹用'#'表示

void?treeNodeConstructor(Tree &root, Element data[]){

????Element e = data[index++];

????if(e ==?'#'){

????????root = NULL;

????}else{

????????root = (Node *)malloc(sizeof(Node));

????????root->data = e;

????????treeNodeConstructor(root->lchild, data);??//遞歸構建左子樹

????????treeNodeConstructor(root->rchild, data);??//遞歸構建右子樹

????}

}

//深度優先遍歷

void?depthFirstSearch(Tree root){

????stack<Node *> nodeStack;??//使用C++的STL標準模板庫

????nodeStack.push(root);

????Node *node;

????while(!nodeStack.empty()){

????????node = nodeStack.top();

????????printf(format, node->data);??//遍歷根結點

????????nodeStack.pop();

????????if(node->rchild){

????????????nodeStack.push(node->rchild);??//先將右子樹壓棧

????????}

????????if(node->lchild){

????????????nodeStack.push(node->lchild);??//再將左子樹壓棧

????????}

????}

}

//廣度優先遍歷

void?breadthFirstSearch(Tree root){

????queue<Node *> nodeQueue;??//使用C++的STL標準模板庫

????nodeQueue.push(root);

????Node *node;

????while(!nodeQueue.empty()){

????????node = nodeQueue.front();

????????nodeQueue.pop();

????????printf(format, node->data);

????????if(node->lchild){

????????????nodeQueue.push(node->lchild);??//先將左子樹入隊

????????}

????????if(node->rchild){

????????????nodeQueue.push(node->rchild);??//再將右子樹入隊

????????}

????}

}

/**

?* <!--

?* File?? : BinaryTreeSearch.h

?* Author : fancy

?* Email? : fancydeepin@yeah.net

?* Date?? : 2013-02-03

?* --!>

?*/

#include "binarytree.h"

int?main() {

????//上圖所示的二叉樹先序遍歷序列,其中用'#'表示結點無左子樹或無右子樹

????Element data[15] = {'A',?'B',?'D',?'#',?'#',?'E',?'#',?'#',?'C',?'F','#',?'#',?'G',?'#',?'#'};

????Tree tree;

????treeNodeConstructor(tree, data);

????printf("深度優先遍歷二叉樹結果: ");

????depthFirstSearch(tree);

????printf("\n\n廣度優先遍歷二叉樹結果: ");

????breadthFirstSearch(tree);

????return?0;

}

https://www.cnblogs.com/rednodel/p/7737686.html?

總結

以上是生活随笔為你收集整理的矮油~ 二叉树的深度优先遍历与广度优先遍历 [ C++ 实现 ]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：西游记中孙悟空的家业历史
下一篇： JavaScript中的标签语句