|
1 樹的廣度優(yōu)先遍歷算法
廣度優(yōu)先遍歷算法，又叫寬度優(yōu)先遍歷，或橫向優(yōu)先遍歷，是從根節(jié)點(diǎn)開始，沿著樹的寬度遍歷樹的節(jié)點(diǎn)。如果所有節(jié)點(diǎn)均被訪問，則算法中止。
如上圖所示的二叉樹，A 是第一個訪問的，然后順序是 B、C，然后再是 D、E、F、G。
那么，怎樣才能來保證這個訪問的順序呢？
借助隊(duì)列數(shù)據(jù)結(jié)構(gòu)，由于隊(duì)列是先進(jìn)先出的順序，因此可以先將左子樹入隊(duì)，然后再將右子樹入隊(duì)。
這樣一來，左子樹結(jié)點(diǎn)就存在隊(duì)頭，可以先被訪問到。 //廣度優(yōu)先遍歷 void breadthFirstTravel(Node* root){queue nodeQueue; //使用C++的STL標(biāo)準(zhǔn)模板庫 nodeQueue.push(root); Node *node; while(!nodeQueue.empty()){ node = nodeQueue.front(); nodeQueue.pop(); printf(format, node->data); if(node->lchild){ nodeQueue.push(node->lchild); //先將左子樹入隊(duì) } if(node->rchild){ nodeQueue.push(node->rchild); //再將右子樹入隊(duì) } }}廣度遍歷層級輸出：struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) :val(x), left(NULL), right(NULL) {}};void levelOrder(TreeNode* root){ if (root == NULL) return ; int curLevelCount = 1, nextLevelCount = 0; queue q; q.push(root); TreeNode* curPtr; while (!q.empty()) { curPtr = q.front(); q.pop(); cout < curptr-="">val < '="" '; ="" ="" curlevelcount--; ="" ="" if="" (null="" !="curPtr-">left) { q.push(curPtr->left); nextLevelCount++; } if (NULL != curPtr->right) { q.push(curPtr->right); nextLevelCount++; } if (0 == curLevelCount) { endl(cout); curLevelCount = nextLevelCount; nextLevelCount = 0; } }}
2 樹的深度優(yōu)先遍歷算法
深度優(yōu)先遍歷算法是遍歷算法的一種。是沿著樹的深度遍歷樹的節(jié)點(diǎn)。 當(dāng)節(jié)點(diǎn)v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。 如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，則選擇其中一個作為源節(jié)點(diǎn)并重復(fù)以上過程，整個進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止。
如上圖所示的二叉樹： A 是第一個訪問的，然后順序是 B、D，然后是 E。接著再是 C、F、G。 那么，怎么樣才能來保證這個訪問的順序呢？ 分析一下，在遍歷了根結(jié)點(diǎn)后，就開始遍歷左子樹，最后才是右子樹。 因此可以借助堆棧的數(shù)據(jù)結(jié)構(gòu)，由于堆棧是后進(jìn)先出的順序，由此可以先將右子樹壓棧，然后再對左子樹壓棧， 這樣一來，左子樹結(jié)點(diǎn)就存在了棧頂上，因此某結(jié)點(diǎn)的左子樹能在它的右子樹遍歷之前被遍歷。 //深度優(yōu)先遍歷 void depthFirstTravel(Node* root){ stack nodeStack; //使用C++的STL標(biāo)準(zhǔn)模板庫 nodeStack.push(root); Node *node; while(!nodeStack.empty()){ node = nodeStack.top(); printf(format, node->data); //遍歷根結(jié)點(diǎn) nodeStack.pop(); if(node->rchild){ nodeStack.push(node->rchild); //先將右子樹壓棧 } if(node->lchild){ nodeStack.push(node->lchild); //再將左子樹壓棧 } }}
|
