您好,登錄后才能下訂單哦!
樹的定義本是遞歸定義,所以采用遞歸的方法實(shí)現(xiàn)遍歷算法,更加讓人理解,且代碼簡單方便。若采用非遞歸的方法實(shí)現(xiàn),須得利用棧模擬實(shí)現(xiàn)。
棧的特點(diǎn)(后進(jìn)先出)
非遞歸實(shí)現(xiàn)二叉樹的前序遍歷:
原理如圖所示:
參考代碼如下:
void _PrevOrder(Node* root)//非遞歸實(shí)現(xiàn)前序遍歷
{
stack<Node*> s;
if(root == NULL)
return;
s.push(root);
while (!s.empty())
{
root = s.top();
cout<<root->_data<<" ";
s.pop();
if (root->_right)
{
s.push(root->_right);
}
if(root->_left)
{
s.push(root->_left);
}
}
}
非遞歸實(shí)現(xiàn)二叉樹的中序遍歷
原理:
先從二叉樹的最左邊進(jìn)行遍歷(1、2、3),且一邊遍歷,一邊入棧,當(dāng)當(dāng)?shù)竭_(dá)結(jié)點(diǎn)3時(shí),因?yàn)?的左右子樹都為空,此時(shí)需彈出結(jié)點(diǎn)3,棧頂元素變?yōu)?,再遍歷2的右子樹的左結(jié)點(diǎn),因?yàn)?的左右子樹都為空,此時(shí)需彈出2,壓人4,左子樹已遍歷結(jié)束,彈出4,再彈出1,依照遍歷左子樹,遍歷右子樹。
參考代碼如下:
void _InOrder(Node* root)//非遞歸實(shí)現(xiàn)中序遍歷
{
stack<Node*> s;
Node* cur = root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
cout<<top->_data<<" ";
s.pop();
cur = top->_right;
}
}
非遞歸實(shí)現(xiàn)二叉樹的后序遍歷
步驟:
1、借助棧實(shí)現(xiàn)后序遍歷,先找到最左邊且為最下邊的結(jié)點(diǎn)3(一邊找,一邊入棧)
2、若3沒有右子樹,則彈出3且打印結(jié)點(diǎn)3,還需要引入一個(gè)指向當(dāng)前彈出結(jié)點(diǎn)的指針prev
3、若3有右子樹,則需要遍歷右子樹,遍歷結(jié)束才可以打印并彈出結(jié)點(diǎn)3,重復(fù)此三步驟可完成后序遍歷。
參考代碼如下:
void _PosOrder(Node* root)//非遞歸實(shí)現(xiàn)后序遍歷
{
Node* cur = root;
Node* prev = NULL;
stack<Node*> s;
if(root == NULL)
return;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cur = s.top();
if(cur->_right == NULL || cur->_right == prev)
{
cout<<cur->_data<<" ";
s.pop();
prev = cur;
cur = NULL;
}
else
{
cur = cur->_right;
}
}
}
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。