樹(shù)的深度廣度優(yōu)先搜索算法

1、深度優(yōu)先搜索算法(Depth First Search)，是搜索算法的一種。是沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)，盡可能深的搜索樹(shù)的分支。當(dāng)節(jié)點(diǎn)v的所有邊都己被探尋過(guò)，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。這一過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過(guò)程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問(wèn)為止。I. B J- C I.、D J I、E J F G 如右圖所示的二叉樹(shù)：A是第一個(gè)訪問(wèn)的，然后順序是B、D，然后是E。接著再是C、F、G。那么，怎么樣才能來(lái)保證這個(gè)訪問(wèn)的順序呢？分析一下，在遍歷了根結(jié)點(diǎn)后，就開(kāi)始遍歷左子樹(shù)，最后才是右子樹(shù)

2、。因此可以借助堆棧的數(shù)據(jù)結(jié)構(gòu)，由于堆棧是后進(jìn)先出的順序，由此可以先將右子樹(shù)壓棧，然后再對(duì)左子樹(shù)壓棧，這樣一來(lái)，左子樹(shù)結(jié)點(diǎn)就存在了棧頂上，因此某結(jié)點(diǎn)的左子樹(shù)能在它的右子樹(shù)遍歷之前被遍歷。深度優(yōu)先遍歷代碼片段/深度優(yōu)先遍歷void depthFirstSearch(Tree root)stack nodeStack; /使用 C+的 STL 標(biāo)準(zhǔn)模板庫(kù)nodeStack.push(root);Node *node;while(!nodeStackempty()node = nodeStacktop();printf(format, node-data);/遍歷根結(jié)點(diǎn)nodeStackpop();i

3、f(node-rchild)nodeStack.push(node-rchild); /先將右子樹(shù)壓棧 if(node-lchild)nodeStack.push(node-lchild); /再將左子樹(shù)壓棧廣度優(yōu)先搜索算法(Breadth First Search)，又叫寬度優(yōu)先搜索，或橫向優(yōu)先搜索。是從根節(jié)點(diǎn)開(kāi)始，沿著樹(shù)的寬度遍歷樹(shù)的節(jié)點(diǎn)。如果所有節(jié)點(diǎn)均被訪問(wèn)，則算法中止。如右圖所示的二叉樹(shù)，A是第一個(gè)訪問(wèn)的，然后順序是B、C，然后再是D、E、F、G。那么，怎樣才能來(lái)保證這個(gè)訪問(wèn)的順序呢？借助隊(duì)列數(shù)據(jù)結(jié)構(gòu)，由于隊(duì)列是先進(jìn)先出的順序，因此可以先將左子樹(shù)入隊(duì)，然后再將右子樹(shù)入隊(duì)。這樣一來(lái)，左子

4、樹(shù)結(jié)點(diǎn)就存在隊(duì)頭，可以先被訪問(wèn)到。廣度優(yōu)先遍歷代碼片段/廣度優(yōu)先遍歷void breadthFirstSearch(Tree root)queue nodeQueue;/使用 C+的 STL 標(biāo)準(zhǔn)模板庫(kù)nodeQueue.push(root);Node *node;while(!nodeQueue.empty()node = nodeQueue.front();nodeQueue.pop();printf(format, node-data);if(node-lchild)nodeQueue.push(node-lchild);/先將左子樹(shù)入隊(duì)if(node-rchild)nodeQueue.

5、push(node-rchild);/再將右子樹(shù)入隊(duì)完整代碼:/*:2013-02-03夫夫夫夫夫夫*/#include#include#include#include#includeusing namespace std;#defineElement char#defineformat %ctypedefstruct Node Element data;struct Node*lchild;struct Node*rchild; *Tree;int index = 0;/全局索引變量/二叉樹(shù)構(gòu)造器,按先序遍歷順序構(gòu)造二叉樹(shù)/無(wú)左子樹(shù)或右子樹(shù)用#表示void treeNodeConstruct

6、or(Tree &root, Element data)Element e = dataindex+;if (e#)root = NULL;elseroot = (Node *)malloc(sizeof(Node);root-data = e;/遞歸構(gòu)建左子樹(shù)/遞歸構(gòu)建右子樹(shù)treeNodeConstructor(root-lchild, data);treeNodeConstructor(root-rchild, data);/深度優(yōu)先遍歷void depthFirstSearch(Tree root)stack nodeStack;/使用 C+的 STL 標(biāo)準(zhǔn)模板庫(kù)nodeStack.p

7、ush(root); Node *node;while(!nodeStackempty() node = nodeStacktop(); printf(format, node-data); /遍歷根結(jié)點(diǎn) nodeStackpop(); if(node-rchild)nodeStack.push(node-rchild);/先將右子樹(shù)壓棧 if(node-lchild)nodeStack.push(node-lchild);/再將左子樹(shù)壓棧 /廣度優(yōu)先遍歷void breadthFirstSearch(Tree root)queue nodeQueue;/使用 C+的 STL 標(biāo)準(zhǔn)模板庫(kù)nod

8、eQueue.push(root);Node *node;while(!nodeQueue.empty()node = nodeQueue.front();nodeQueue.pop();printf(format, node-data);if(node-lchild)nodeQueue.push(node-lchild);/先將左子樹(shù)入隊(duì) if(node-rchild)nodeQueue.push(node-rchild);/再將右子樹(shù)入隊(duì) 二叉樹(shù)的深度優(yōu)先遍歷（中序遍歷）：當(dāng)我們利用樹(shù)的深度優(yōu)先遍歷找到滿(mǎn)足條件的一條路徑時(shí)，需要設(shè)置一個(gè)bool類(lèi)型標(biāo)志，如果 在左子樹(shù)中已經(jīng)找到，則不需遞歸右子樹(shù)，一般采用以下步驟：Bool findPath（pCur,pNode）If（滿(mǎn)足條件）Return true;s.push(pcur);Bool found=false;/設(shè)置一個(gè)標(biāo)志，來(lái)判斷是否已經(jīng)找到了一條路徑If(pCur-left)found=findPath(pCur-left,pNode);If(pCur-right & !found) / 找到了就不用遞歸found=findPath(pCur-right,pNode);If(!found)s.pop();Return found;當(dāng)我們需要找到所有滿(mǎn)足條件的路徑時(shí)，一般采用如下步驟：Void findPath(pc