二叉樹的遍歷
遍歷即按照一定規(guī)律訪問節(jié)點(diǎn)禁谦，且每個(gè)節(jié)點(diǎn)只訪問一次的過程显设。
線性結(jié)構(gòu)前驅(qū)和后繼的唯一性決定了遍歷路線只有一條，而二叉樹是非線性結(jié)構(gòu)涩盾，每個(gè)節(jié)點(diǎn)可能存在兩個(gè)后繼節(jié)點(diǎn)十气，這導(dǎo)致存在多條遍歷路線。在任意給定的節(jié)點(diǎn)上春霍，判斷不為空后砸西，可以按照某種次序執(zhí)行3個(gè)操作：訪問節(jié)點(diǎn)本身，遍歷該節(jié)點(diǎn)的左子樹址儒，遍歷該節(jié)點(diǎn)的右子樹芹枷。實(shí)際問題一般要求左子樹較右子樹先遍歷，故只采用：1莲趣，左杖狼、根、右 2妖爷，根蝶涩、左、右 3絮识，左绿聘、右、根 次舌，分別稱為：中序遍歷熄攘、先序遍歷和后續(xù)遍歷。
遍歷的遞歸實(shí)現(xiàn)
遞歸實(shí)現(xiàn)比較簡單,已先序遍歷為例彼念。
void preOrder(BinTree *root) //遞歸先序遍歷
{
if(root!=NULL)
{
cout<<root->data<<" ";//調(diào)換此三條語句即可
preOrder(root->lchild);
preOrder(root->rchild);
}
}
遍歷的非遞歸實(shí)現(xiàn)
先序遍歷的非遞歸實(shí)現(xiàn)作為例子挪圾，先申請(qǐng)一個(gè)棧存儲(chǔ)，
- 從根節(jié)點(diǎn)出發(fā)逐沙，沿著左子樹走哲思，訪問一個(gè)節(jié)點(diǎn)后就將這個(gè)節(jié)點(diǎn)放入棧中，代表此節(jié)點(diǎn)訪問過根節(jié)點(diǎn)吩案，但沒有訪問左右子樹棚赔，
- 之后沿著左子樹走，上一根節(jié)點(diǎn)的左子樹就開始被訪問了。直到走到左子樹為空指針靠益。
- 此時(shí) 遍歷的指針指向空丧肴，判斷棧中是否有節(jié)點(diǎn)，若有胧后，則將棧頂元素取出芋浮，將遍歷指針指向此元素的右子樹，棧頂元素的右子樹開始被訪問了壳快，繼續(xù)重復(fù)二步驟纸巷，若棧中無元素則遍歷結(jié)束。
void preOrder(BinTree *root) //非遞歸先序遍歷
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
中序遍歷的代碼與先序遍歷類似濒憋，不同的是何暇，中序遍歷是先訪問左子樹后才能訪問根節(jié)點(diǎn)，所以要在從棧中取出元素時(shí)讀取元素?cái)?shù)據(jù)凛驮。
void inOrder2(BinTree *root) //非遞歸中序遍歷
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
}
二叉樹的后序遍歷的非遞歸實(shí)現(xiàn)最為有難度裆站，一般使用遞歸方式即可。
二叉樹的層次遍歷
首先把根節(jié)點(diǎn)入隊(duì)黔夭，之后開始執(zhí)行出隊(duì)操作宏胯，每出隊(duì)一個(gè)節(jié)點(diǎn)就把該節(jié)點(diǎn)的左右孩子加入到隊(duì)列中（即下一層的節(jié)點(diǎn)），隊(duì)頭節(jié)點(diǎn)就是接下來要遍歷的節(jié)點(diǎn)本姥，直到葉子節(jié)點(diǎn)沒有左右子樹進(jìn)而沒有新節(jié)點(diǎn)入隊(duì)肩袍，知道隊(duì)列為空時(shí)遍歷結(jié)束。
#include
#include
using namespace std;
void PrintAtLevel(Tree T) {
queue myqueue;
myqueue.push(T);
while (!myqueue.empty()) {
Tree tmp = myqueue.front();
if (tmp->lchild != NULL)
myqueue.push(tmp->lchild);
if (tmp->rchild != NULL)
myqueue.push(tmp->rchild);
cout << tmp->value << " ";
myqueue.pop();
}
}
森林的遍歷
森林的第一棵樹的根相當(dāng)于二叉樹的根婚惫，第一棵樹的子樹組成的森林對(duì)應(yīng)于二叉樹的左子樹氛赐，而除第一棵樹外其余樹組成的森林相當(dāng)于二叉樹的右子樹。
