二叉樹的非遞歸遍歷（前序、中序塞颁、后序）

一.前序遍歷

? ? 非遞歸實現(xiàn)

　　根據(jù)前序遍歷訪問的順序浦箱，優(yōu)先訪問根結(jié)點，然后再分別訪問左孩子和右孩子祠锣。即對于任一結(jié)點酷窥，其可看做是根結(jié)點，因此可以直接訪問伴网，訪問完之后蓬推，若其左孩子不為空，按相同規(guī)則訪問它的左子樹澡腾；當訪問其左子樹時沸伏，再訪問它的右子樹。因此其處理過程如下：

　　對于任一結(jié)點P：

? ? 1)訪問結(jié)點P动分，并將結(jié)點P入棧;

? ? 2)判斷結(jié)點P的左孩子是否為空毅糟，若為空，則取棧頂結(jié)點并進行出棧操作澜公，并將棧頂結(jié)點的右孩子置為當前的結(jié)點P姆另，循環(huán)至1);若不為空，則將P的左孩子置為當前的結(jié)點P;

? ? 3)直到P為NULL并且棧為空玛瘸，則遍歷結(jié)束蜕青。

1 void preOrder2(BinTree *root)? ? //非遞歸前序遍歷

2 {

3? ? stack<BinTree*> s;

4? ? BinTree *p=root;

5? ? while(p!=NULL||!s.empty())

6? ? {

7? ? ? ? while(p!=NULL)

8? ? ? ? {

9? ? ? ? ? ? cout<<p->data<<" ";

10? ? ? ? ? ? s.push(p);

11? ? ? ? ? ? p=p->lchild;

12? ? ? ? }

13? ? ? ? if(!s.empty())

14? ? ? ? {

15? ? ? ? ? ? p=s.top();

16? ? ? ? ? ? s.pop();

17? ? ? ? ? ? p=p->rchild;

18? ? ? ? }

19? ? }

20 }

二.中序遍歷

　非遞歸實現(xiàn)

　　根據(jù)中序遍歷的順序，對于任一結(jié)點糊渊，優(yōu)先訪問其左孩子右核，而左孩子結(jié)點又可以看做一根結(jié)點，然后繼續(xù)訪問其左孩子結(jié)點渺绒，直到遇到左孩子結(jié)點為空的結(jié)點才進行訪問贺喝，然后按相同的規(guī)則訪問其右子樹菱鸥。因此其處理過程如下：

　　對于任一結(jié)點P，

? 　1)若其左孩子不為空躏鱼，則將P入棧并將P的左孩子置為當前的P氮采，然后對當前結(jié)點P再進行相同的處理；

　 2)若其左孩子為空染苛，則取棧頂元素并進行出棧操作鹊漠，訪問該棧頂結(jié)點，然后將當前的P置為棧頂結(jié)點的右孩子茶行；

? 　3)直到P為NULL并且棧為空則遍歷結(jié)束躯概。

1 void inOrder2(BinTree *root)? ? ? //非遞歸中序遍歷

2 {

3? ? stack<BinTree*> s;

4? ? BinTree *p=root;

5? ? while(p!=NULL||!s.empty())

6? ? {

7? ? ? ? while(p!=NULL)

8? ? ? ? {

9? ? ? ? ? ? s.push(p);

10? ? ? ? ? ? p=p->lchild;

11? ? ? ? }

12? ? ? ? if(!s.empty())

13? ? ? ? {

14? ? ? ? ? ? p=s.top();

15? ? ? ? ? ? cout<<p->data<<" ";

16? ? ? ? ? ? s.pop();

17? ? ? ? ? ? p=p->rchild;

18? ? ? ? }

19? ? }? ?

20 }

三.后序遍歷

? ? 非遞歸實現(xiàn)

? ? ? 第一種思路：對于任一結(jié)點P，將其入棧畔师，然后沿其左子樹一直往下搜索娶靡，直到搜索到?jīng)]有左孩子的結(jié)點，此時該結(jié)點出現(xiàn)在棧頂看锉，但是此時不能將其出棧并訪問姿锭，因此其右孩子還為被訪問。所以接下來按照相同的規(guī)則對其右子樹進行相同的處理伯铣，當訪問完其右孩子時呻此，該結(jié)點又出現(xiàn)在棧頂，此時可以將其出棧并訪問腔寡。這樣就保證了正確的訪問順序趾诗。可以看出蹬蚁，在這個過程中恃泪，每個結(jié)點都兩次出現(xiàn)在棧頂，只有在第二次出現(xiàn)在棧頂時犀斋，才能訪問它贝乎。因此需要多設(shè)置一個變量標識該結(jié)點是否是第一次出現(xiàn)在棧頂。

1 void postOrder2(BinTree *root)? ? //非遞歸后序遍歷

2 {

3? ? stack<BTNode*> s;

4? ? BinTree *p=root;

5? ? BTNode *temp;

6? ? while(p!=NULL||!s.empty())

7? ? {

8? ? ? ? while(p!=NULL)? ? ? ? ? ? ? //沿左子樹一直往下搜索叽粹，直至出現(xiàn)沒有左子樹的結(jié)點

9? ? ? ? {

10? ? ? ? ? ? BTNode *btn=(BTNode *)malloc(sizeof(BTNode));

11? ? ? ? ? ? btn->btnode=p;

12? ? ? ? ? ? btn->isFirst=true;

13? ? ? ? ? ? s.push(btn);

14? ? ? ? ? ? p=p->lchild;

15? ? ? ? }

16? ? ? ? if(!s.empty())

17? ? ? ? {

18? ? ? ? ? ? temp=s.top();

19? ? ? ? ? ? s.pop();

20? ? ? ? ? if(temp->isFirst==true)? ? ? ? ? //表示是第一次出現(xiàn)在棧頂

21? ? ? ? ? ? ? {

22? ? ? ? ? ? ? temp->isFirst=false;

23? ? ? ? ? ? ? ? s.push(temp);

24? ? ? ? ? p=temp->btnode->rchild;? ?

25? ? ? ? ? ? }

26? ? ? ? ? ? else? ? ? ? ? ? ? ? ? ? ? ? //第二次出現(xiàn)在棧頂

27? ? ? ? ? ? ? {

28? ? cout<<temp->btnode->data<<" ";

29? ? ? ? ? ? ? ? p=NULL;

30? ? ? ? ? ? }

31? ? ? ? }

32? ? }? ?

33 }

　　第二種思路：要保證根結(jié)點在左孩子和右孩子訪問之后才能訪問览效，因此對于任一結(jié)點P，先將其入棧虫几。如果P不存在左孩子和右孩子锤灿，則可以直接訪問它；或者P存在左孩子或者右孩子辆脸，但是其左孩子和右孩子都已被訪問過了但校，則同樣可以直接訪問該結(jié)點。若非上述兩種情況啡氢，則將P的右孩子和左孩子依次入棧状囱，這樣就保證了每次取棧頂元素的時候术裸，左孩子在右孩子前面被訪問，左孩子和右孩子都在根結(jié)點前面被訪問亭枷。

1 void postOrder3(BinTree *root)? ?

//非遞歸后序遍歷

2 {

3? ? stack<BinTree*> s;

4? ? BinTree *cur;? ? ? ? ? ? ? ? ? ? ? //當前結(jié)點

5? ? BinTree *pre=NULL;? ? ? ? ? ? ? ? //前一次訪問的結(jié)點

6? ? s.push(root);

7? ? while(!s.empty())

8? ? {

9? ? ? ? cur=s.top();

10if((cur->lchild==NULL&&cur-? ? ? ? ? >rchild==NULL)||

11? ? ? ? ? ? (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))

12? ? ? ? {

13? ? ? ? ? ? cout<<cur->data<<" ";?

//如果當前結(jié)點沒有孩子結(jié)點或者孩子節(jié)點都已被訪問過

14? ? ? ? ? ? ? s.pop();

15? ? ? ? ? ? pre=cur;

16? ? ? ? }

17? ? ? ? else

18? ? ? ? {

19? ? ? ? ? ? if(cur->rchild!=NULL)

20? ? ? ? ? ? ? ? s.push(cur->rchild);

21? ? ? ? ? ? if(cur->lchild!=NULL)? ?

22? ? ? ? ? ? ? ? s.push(cur->lchild);

23? ? ? ? }

24? ? }? ?

25 }

四.整個程序完整的代碼

? 1 /*二叉樹的遍歷* 2011.8.25*/

? 2

? 3 #include <iostream>

? 4 #include<string.h>

? 5 #include<stack>

? 6 using namespace std;

? 7

? 8 typedef struct node

? 9 {

10? ? char data;

11? ? struct node *lchild,*rchild;

12 }BinTree;

14 typedef struct node1

15 {

16? ? BinTree *btnode;

17? ? bool isFirst;

18 }BTNode;

21 void creatBinTree(char *s,BinTree *&root)? //創(chuàng)建二叉樹袭艺，s為形如A(B,C(D,E))形式的字符串

22 {

23? ? int i;

24? ? bool isRight=false;

25? ? stack<BinTree*> s1;? ? ? ? ? //存放結(jié)點

26? ? stack<char> s2;? ? ? ? ? ? ? //存放分隔符

27? ? BinTree *p,*temp;

28? ? root->data=s[0];

29? ? root->lchild=NULL;

30? ? root->rchild=NULL;

31? ? s1.push(root);

32? ? i=1;

33? ? while(i<strlen(s))

34? ? {

35? ? ? ? if(s[i]=='(')

36? ? ? ? {

37? ? ? ? ? ? s2.push(s[i]);

38? ? ? ? ? ? isRight=false;

39? ? ? ? }? ?

40? ? ? ? else if(s[i]==',')? ?

41? ? ? ? {

42? ? ? ? ? ? isRight=true;

43? ? ? ? }

44? ? ? ? else if(s[i]==')')

45? ? ? ? {

46? ? ? ? ? ? s1.pop();

47? ? ? ? ? ? s2.pop();

48? ? ? ? }

49? ? ? ? else if(isalpha(s[i]))

50? ? ? ? {

51? ? ? ? ? ? p=(BinTree *)malloc(sizeof(BinTree));

52? ? ? ? ? ? p->data=s[i];

53? ? ? ? ? ? p->lchild=NULL;

54? ? ? ? ? ? p->rchild=NULL;

55? ? ? ? ? ? temp=s1.top();

56? ? ? ? ? ? if(isRight==true)? ?

57? ? ? ? ? ? {

58? ? ? ? ? ? ? ? temp->rchild=p;

59? ? ? ? ? ? ? ? cout<<temp->data<<"的右孩子是"<<s[i]<<endl;

60? ? ? ? ? ? }

61? ? ? ? ? ? else

62? ? ? ? ? ? {

63? ? ? ? ? ? ? ? temp->lchild=p;

64? ? ? ? ? ? ? ? cout<<temp->data<<"的左孩子是"<<s[i]<<endl;

65? ? ? ? ? ? }

66? ? ? ? ? ? if(s[i+1]=='(')

67? ? ? ? ? ? ? ? s1.push(p);

68? ? ? ? }

69? ? ? ? i++;

70? ? }? ?

71 }

73 void display(BinTree *root)? ? ? ? //顯示樹形結(jié)構(gòu)

74 {

75? ? if(root!=NULL)

76? ? {

77? ? ? ? cout<<root->data;

78? ? ? ? if(root->lchild!=NULL)

79? ? ? ? {

80? ? ? ? ? ? cout<<'(';

81? ? ? ? ? ? display(root->lchild);

82? ? ? ? }

83? ? ? ? if(root->rchild!=NULL)

84? ? ? ? {

85? ? ? ? ? ? cout<<',';

86? ? ? ? ? ? display(root->rchild);

87? ? ? ? ? ? cout<<')';

88? ? ? ? }

89? ? }

90 }

92 void preOrder1(BinTree *root)? ? //遞歸前序遍歷

93 {

94? ? if(root!=NULL)

95? ? {

96? ? ? ? cout<<root->data<<" ";

97? ? ? ? preOrder1(root->lchild);

98? ? ? ? preOrder1(root->rchild);

99? ? }

100 }

101

102 void inOrder1(BinTree *root)? ? ? //遞歸中序遍歷

103 {

104? ? if(root!=NULL)

105? ? {

106? ? ? ? inOrder1(root->lchild);

107? ? ? ? cout<<root->data<<" ";

108? ? ? ? inOrder1(root->rchild);

109? ? }

110 }

111

112 void postOrder1(BinTree *root)? ? //遞歸后序遍歷

113 {

114? ? if(root!=NULL)

115? ? {

116? ? ? ? postOrder1(root->lchild);

117? ? ? ? postOrder1(root->rchild);

118? ? ? ? cout<<root->data<<" ";

119? ? }? ?

120 }

121

122 void preOrder2(BinTree *root)? ? //非遞歸前序遍歷

123 {

124? ? stack<BinTree*> s;

125? ? BinTree *p=root;

126? ? while(p!=NULL||!s.empty())

127? ? {

128? ? ? ? while(p!=NULL)

129? ? ? ? {

130? ? ? ? ? ? cout<<p->data<<" ";

131? ? ? ? ? ? s.push(p);

132? ? ? ? ? ? p=p->lchild;

133? ? ? ? }

134? ? ? ? if(!s.empty())

135? ? ? ? {

136? ? ? ? ? ? p=s.top();

137? ? ? ? ? ? s.pop();

138? ? ? ? ? ? p=p->rchild;

139? ? ? ? }

140? ? }

141 }

142

143 void inOrder2(BinTree *root)? ? ? //非遞歸中序遍歷

144 {

145? ? stack<BinTree*> s;

146? ? BinTree *p=root;

147? ? while(p!=NULL||!s.empty())

148? ? {

149? ? ? ? while(p!=NULL)

150? ? ? ? {

151? ? ? ? ? ? s.push(p);

152? ? ? ? ? ? p=p->lchild;

153? ? ? ? }

154? ? ? ? if(!s.empty())

155? ? ? ? {

156? ? ? ? ? ? p=s.top();

157? ? ? ? ? ? cout<<p->data<<" ";

158? ? ? ? ? ? s.pop();

159? ? ? ? ? ? p=p->rchild;

160? ? ? ? }

161? ? }? ?

162 }

163

164 void postOrder2(BinTree *root)? ? //非遞歸后序遍歷

165 {

166? ? stack<BTNode*> s;

167? ? BinTree *p=root;

168? ? BTNode *temp;

169? ? while(p!=NULL||!s.empty())

170? ? {

171? ? ? ? while(p!=NULL)? ? ? ? ? ? ? //沿左子樹一直往下搜索，直至出現(xiàn)沒有左子樹的結(jié)點

172? ? ? ? ? {

173? ? ? ? ? ? BTNode *btn=(BTNode *)malloc(sizeof(BTNode));

174? ? ? ? ? ? btn->btnode=p;

175? ? ? ? ? ? btn->isFirst=true;

176? ? ? ? ? ? s.push(btn);

177? ? ? ? ? ? p=p->lchild;

178? ? ? ? }

179? ? ? ? if(!s.empty())

180? ? ? ? {

181? ? ? ? ? ? temp=s.top();

182? ? ? ? ? ? s.pop();

183? ? ? ? ? ? if(temp->isFirst==true)? ? //表示是第一次出現(xiàn)在棧頂

184? ? ? ? ? ? ? {

185? ? ? ? ? ? ? ? temp->isFirst=false;

186? ? ? ? ? ? ? ? s.push(temp);

187? ? ? ? ? ? ? ? p=temp->btnode->rchild;? ?

188? ? ? ? ? ? }

189? ? ? ? ? ? else? ? ? ? ? ? ? ? ? ? ? ? //第二次出現(xiàn)在棧頂

190? ? ? ? ? ? ? {

191? ? ? ? ? ? ? ? cout<<temp->btnode->data<<" ";

192? ? ? ? ? ? ? ? p=NULL;

193? ? ? ? ? ? }

194? ? ? ? }

195? ? }? ?

196 }

197

198 void postOrder3(BinTree *root)? ? //非遞歸后序遍歷

199 {

200? ? stack<BinTree*> s;

201? ? BinTree *cur;? ? ? ? ? ? ? ? ? ? ? //當前結(jié)點

202? ? BinTree *pre=NULL;? ? ? ? ? ? ? ? //前一次訪問的結(jié)點

203? ? s.push(root);

204? ? while(!s.empty())

205? ? {

206? ? ? ? cur=s.top();

207? ? ? ? if((cur->lchild==NULL&&cur->rchild==NULL)||

208? ? ? ? ? ? (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))

209? ? ? ? {

210? ? ? ? ? ? cout<<cur->data<<" ";? //如果當前結(jié)點沒有孩子結(jié)點或者孩子節(jié)點都已被訪問過

211? ? ? ? ? ? ? s.pop();

212? ? ? ? ? ? pre=cur;

213? ? ? ? }

214? ? ? ? else

215? ? ? ? {

216? ? ? ? ? ? if(cur->rchild!=NULL)

217? ? ? ? ? ? ? ? s.push(cur->rchild);

218? ? ? ? ? ? if(cur->lchild!=NULL)? ?

219? ? ? ? ? ? ? ? s.push(cur->lchild);

220? ? ? ? }

221? ? }? ?

222 }

223

224

225 int main(int argc, char *argv[])

226 {

227? ? char s[100];

228? ? while(scanf("%s",s)==1)

229? ? {

230? ? ? ? BinTree *root=(BinTree *)malloc(sizeof(BinTree));

231? ? ? ? creatBinTree(s,root);

232? ? ? ? display(root);

233? ? ? ? cout<<endl;

234? ? ? ? preOrder2(root);

235? ? ? ? cout<<endl;

236? ? ? ? inOrder2(root);

237? ? ? ? cout<<endl;

238? ? ? ? postOrder2(root);

239? ? ? ? cout<<endl;

240? ? ? ? postOrder3(root);

241? ? ? ? cout<<endl;

242? ? }

243? ? return 0;

244 }

圖片發(fā)自簡書App

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末叨粘，一起剝皮案震驚了整個濱河市猾编，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌升敲，老刑警劉巖袍镀，帶你破解...
沈念sama閱讀 218,525評論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異冻晤，居然都是意外死亡，警方通過查閱死者的電腦和手機绸吸，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,203評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門鼻弧，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人锦茁，你說我怎么就攤上這事攘轩。” “怎么了码俩？”我有些...
開封第一講書人閱讀 164,862評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵度帮，是天一觀的道長。經(jīng)常有香客問我稿存，道長笨篷，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,728評論 1贊 294
?港島之戀（遺憾婚禮）
正文為了忘掉前任瓣履，我火速辦了婚禮率翅，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘袖迎。我一直安慰自己冕臭，他們只是感情好，可當我...
茶點故事閱讀 67,743評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布燕锥。她就那樣靜靜地躺著辜贵，像睡著了一般。火紅的嫁衣襯著肌膚如雪归形。梳的紋絲不亂的頭發(fā)上托慨，一...
開封第一講書人閱讀 51,590評論 1贊 305
城市分裂傳說
那天，我揣著相機與錄音暇榴，去河邊找鬼榴芳。笑死嗡靡，一個胖子當著我的面吹牛，可吹牛的內(nèi)容都是我干的窟感。我是一名探鬼主播讨彼，決...
沈念sama閱讀 40,330評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼柿祈！你這毒婦竟也來了哈误？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,244評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤躏嚎，失蹤者是張志新（化名）和其女友劉穎蜜自，沒想到半個月后，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體卢佣，經(jīng)...
沈念sama閱讀 45,693評論 1贊 314
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡重荠，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,885評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了虚茶。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片戈鲁。...
茶點故事閱讀 40,001評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖嘹叫，靈堂內(nèi)的尸體忽然破棺而出婆殿，到底是詐尸還是另有隱情，我是刑警寧澤罩扇，帶...
沈念sama閱讀 35,723評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布婆芦，位于F島的核電站，受9級特大地震影響喂饥，放射性物質(zhì)發(fā)生泄漏消约。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,343評論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一员帮、第九天我趴在偏房一處隱蔽的房頂上張望荆陆。院中可真熱鬧，春花似錦集侯、人聲如沸被啼。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,919評論 0贊 22
一樁弒父案棠枉，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽浓体。三九已至，卻和暖如春辈讶，著一層夾襖步出監(jiān)牢的瞬間命浴，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,042評論 1贊 270
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留生闲，地道東北人媳溺。一個月前我還...
沈念sama閱讀 48,191評論 3贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長得像碍讯，于是被迫代替她去往敵國和親悬蔽。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
茶點故事閱讀 44,955評論 2贊 355

二叉樹的非遞歸遍歷（前序扰法、中序蛹含、后序）

二叉樹的非遞歸遍歷（前序、中序塞颁、后序）

推薦閱讀更多精彩內(nèi)容