|
題目：
遞歸和非遞歸倆種方法實(shí)現(xiàn)二叉樹的前序遍歷。
思路一：
對(duì)二叉樹的遞歸遍歷我相信大家只要學(xué)了數(shù)據(jù)結(jié)構(gòu)后應(yīng)當(dāng)都很容易就能寫出，這里主要是討論二叉樹的非遞歸寫法。按照二叉樹前序遍歷的定義，無論是訪問整棵樹還是其子樹，均應(yīng)該遵循先訪問根結(jié)點(diǎn)，然后訪問根結(jié)點(diǎn)的左子樹，最后訪問根結(jié)點(diǎn)的右子樹的。在整個(gè)二叉樹前序遍歷的過程中，程序始終要做的工作分成倆個(gè)部分：（借用輔助棧來實(shí)現(xiàn)）
1. 當(dāng)前正在處理的樹（子樹）
2. 保存在棧中等待處理的部分。
當(dāng)棧中元素位于棧頂即將出棧時(shí)，意味著其根結(jié)點(diǎn)和左子樹已訪問完成，出棧后，進(jìn)入其右子樹進(jìn)行訪問。
代碼如下：
-
-
-
- #include "stdafx.h"
- #include <assert.h>
- #include <iostream>
- #include <stack>
- using namespace std;
- typedef struct tagBSTreeNode
- {
- int nValue;
- tagBSTreeNode *psLeft;
- tagBSTreeNode *psRight;
- tagBSTreeNode()
- {
- psLeft = psRight = 0;
- nValue = 0;
- }
- }S_BSTreeNode;
- void AddBSTreeNode(S_BSTreeNode *&psRoot, int nValue)
- {
- if (NULL == psRoot)
- {
- psRoot = new S_BSTreeNode;
- assert(psRoot);
- psRoot->nValue = nValue;
- return;
- }
- if (psRoot->nValue < nValue)
- AddBSTreeNode(psRoot->psRight, nValue);
- else
- AddBSTreeNode(psRoot->psLeft, nValue);
- }
- void PreOrder_Recursion(const S_BSTreeNode *psRoot)
- {
- if (NULL == psRoot)
- return;
- cout << psRoot->nValue << " ";
- PreOrder_Recursion(psRoot->psLeft);
- PreOrder_Recursion(psRoot->psRight);
- }
- void PreOrder_Not_Recursion(S_BSTreeNode *psRoot)
- {
- stack<S_BSTreeNode *> stackNode;
- S_BSTreeNode *psCurNode = psRoot;
- while ((!stackNode.empty()) || (psCurNode != NULL))
- {
- if (psCurNode != NULL)
- {
- while (psCurNode)
- {
- cout << psCurNode->nValue << " ";
- stackNode.push(psCurNode);
- psCurNode = psCurNode->psLeft;
- }
- }
- else
- {
- psCurNode = stackNode.top();
- stackNode.pop();
- psCurNode = psCurNode->psRight;
- }
- }
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- S_BSTreeNode *psRoot = NULL;
- AddBSTreeNode(psRoot, 8);
- AddBSTreeNode(psRoot, 6);
- AddBSTreeNode(psRoot, 4);
- AddBSTreeNode(psRoot, 5);
- AddBSTreeNode(psRoot, 12);
- AddBSTreeNode(psRoot, 10);
- AddBSTreeNode(psRoot, 15);
- AddBSTreeNode(psRoot, 13);
- AddBSTreeNode(psRoot, 14);
- cout << "遞歸遍歷的結(jié)果為:" << endl;
- PreOrder_Recursion(psRoot);
- cout << endl;
- cout << "非遞歸遍歷的結(jié)果為:" << endl;
- PreOrder_Not_Recursion(psRoot);
- cout << endl;
-
- return 0;
- }
擴(kuò)展：
如果要求是非遞歸后序遍歷呢？非遞歸后序稍微有點(diǎn)復(fù)雜。按照二叉樹后序遍歷的定義，無論是訪問整棵樹還是起子樹，均應(yīng)該遵循先訪問根結(jié)點(diǎn)左子樹，然后訪問根結(jié)點(diǎn)的右子樹，最后訪問根結(jié)點(diǎn)。值得注意的是，當(dāng)一個(gè)元素位于棧頂即將處理的是，其左子樹的訪問一定完成，如果其右子樹不為空，接下來應(yīng)該進(jìn)入其右子樹訪問，但此時(shí)該棧頂元素時(shí)不能出棧的，因?yàn)樗鳛楦Y(jié)點(diǎn)，其本身的值還未被訪問。只有等到其右子樹也訪問完成后，該棧頂元素才能出棧，并輸出它的值。 因此，在二叉樹后序遍歷的算法中，必須每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)類型為int的整數(shù)nTag，
其每個(gè)元素(節(jié)點(diǎn))的nTag取值為0 或1，用于標(biāo)識(shí)棧中每個(gè)元素的狀態(tài)。
1. 當(dāng)一個(gè)元素剛進(jìn)棧時(shí)，其對(duì)應(yīng)的nTag 值置為0；
2. 當(dāng)它位于棧頂即將被處理時(shí)，其nTag 值為0.意味著應(yīng)該訪問其右子樹，于是將右子樹作為當(dāng)前處理的對(duì)象，此時(shí)該棧頂元素仍應(yīng)該保留在棧中，并將其對(duì)應(yīng)的nTag 值改為1.
3. 當(dāng)其右子樹訪問完成后，該元素又一次位于棧頂，而此時(shí)其nTag 值為1，意味著其右子樹已訪問完成，接下來，應(yīng)該直接訪問的就是它，將其出棧。
代碼如下：
- void PostOrder_Not_Recursion(S_BSTreeNode *psRoot)
- {
- stack<S_BSTreeNode *> stackNode;
- S_BSTreeNode *psCurNode = psRoot;
- while ((!stackNode.empty()) || (psCurNode != NULL))
- {
- if (psCurNode != NULL)
- {
- while (psCurNode )
- {
- stackNode.push(psCurNode);
- psCurNode = psCurNode->psLeft;
- }
- }
- psCurNode = stackNode.top();
- while ((!stackNode.empty()) && (psCurNode->nTag == 1))
- {
- cout << psCurNode->nValue << " ";
- stackNode.pop();
- if (stackNode.empty())
- psCurNode = NULL;
- else
- psCurNode = stackNode.top();
- }
- if (!stackNode.empty())
- {
- psCurNode->nTag = 1;
- psCurNode = psCurNode->psRight;
- }
- else
- psCurNode = NULL;
- }
- }
|
