typedef struct BiTree* Node;
typedef struct BiTree* Tree;
struct BiTree
{
int Element;
Node Left;
Node Right;
bool isFirst; //從下向上出棧過程中,第一次出現(xiàn)在棧頂
};
//先序遍歷, 遞歸
void TraverseTreePreOrder(Tree T)
{
if(T != NULL)
{
cout<<T->Element<<" ";
TraverseTreePreOrder(T->Left);
TraverseTreePreOrder(T->Right);
}
}
//中序遍歷, 遞歸
void TraverseTreeInOrder(Tree T)
{
if(T != NULL)
{
TraverseTreeInOrder(T->Left);
cout<<T->Element<<" ";
TraverseTreeInOrder(T->Right);
}
}
//后序遍歷,遞歸
void TraverseTreePostOrder(Tree T)
{
if(T != NULL)
{
TraverseTreePostOrder(T->Left);
TraverseTreePostOrder(T->Right);
cout<<T->Element<<" ";
}
}
//先序遍歷. 非遞歸
void TraverseTreePreOrder2(Tree T)
{
stack<Node> Stack;
while(T!= NULL && !Stack.empty()) //每進行一次while,都是從左兒子到右兒子
{
while(T != NULL) //一直遍歷最左邊的節(jié)點
{
cout<<T->Element<<" ";
Stack.push(T);
T = T->Left;
}
//如果遍歷到底了,就向上一層, 遍歷右兒子
T =Stack.top();
T = T->Right;
Stack.pop();
}
}
//中序遍歷, 非遞歸
void TraverseTreeInOrder2(Tree T)
{
stack<Node> Stack;
while(T!= NULL && !Stack.empty())
{
while(T != NULL)
{
Stack.push(T);
T = T->Left;
}
T = Stack.top;
Stack.pop();
cout<<T->Element<<" ";
T = T->Right;
}
}
//后序遍歷, 非遞歸
void TraverseTreePostOrder(Tree T)
{
stack<Node> Stack;
while(T != NULL && !Stack.empty())
{
while(T != NULL)
{
Stack.push(T);
T->isFirst = true; //所有節(jié)點在初始入棧時都會在此被設(shè)為true.
T = T->Left;
}
T = Stack.top();
//Stack.pop();
if(T->isFirst) //左節(jié)點被遍歷完,準(zhǔn)備向右節(jié)點遍歷時
{
T->isFirst = false;
//Stack.push(T);
T = T->Right;
}
else //右節(jié)點被遍歷完,又回到這個節(jié)點,準(zhǔn)備走向父節(jié)點
{
Stack.pop();
cout<<T->Element<<" ";
T = NULL:
}
}
}
二叉樹的遍歷
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門惯疙，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人妖啥，你說我怎么就攤上這事霉颠。” “怎么了荆虱？”我有些...
- 文/不壞的土叔 我叫張陵蒿偎，是天一觀的道長。 經(jīng)常有香客問我怀读，道長诉位，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任菜枷，我火速辦了婚禮苍糠，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘啤誊。我一直安慰自己岳瞭，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布蚊锹。 她就那樣靜靜地躺著瞳筏，像睡著了一般。 火紅的嫁衣襯著肌膚如雪牡昆。 梳的紋絲不亂的頭發(fā)上姚炕，一...
- 文/蒼蘭香墨 我猛地睜開眼狐史，長吁一口氣：“原來是場噩夢啊……” “哼痒给！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起骏全，我...
- 正文 年R本政府宣布币喧，位于F島的核電站，受9級特大地震影響袱耽，放射性物質(zhì)發(fā)生泄漏杀餐。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一扛邑、第九天 我趴在偏房一處隱蔽的房頂上張望怜浅。 院中可真熱鬧，春花似錦蔬崩、人聲如沸恶座。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽跨琳。三九已至，卻和暖如春桐罕，著一層夾襖步出監(jiān)牢的瞬間脉让，已是汗流浹背。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 準(zhǔn)備工作 我們在學(xué)習(xí)二叉樹的遍歷之前设捐，先繼續(xù)上一講的內(nèi)容，我們來構(gòu)造一個二叉樹塘淑，并且打印出來萝招！ 將下圖中的二叉樹打...
- 正文之前 在實習(xí)的時候?qū)W習(xí)環(huán)境太差了，今天就結(jié)束生產(chǎn)實習(xí)啦存捺！所以后面可以回去好好看書了槐沼！高興，特地來發(fā)篇排過版的文...
- 樹（tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合母赵。...
- 結(jié)果顯而易見 前序遍歷ABDHKECFIGJ中序遍歷HKDBEAIFCGJ后序遍歷KHDEBIFJGCA
- 棧實現(xiàn)前序遍歷 棧實現(xiàn)前序遍歷較簡單逸爵，由于每次先輸出根節(jié)點具滴，再輸出左節(jié)點隨后是右節(jié)點凹嘲。因此我的處理邏輯是： 1、若...
