非遞歸實(shí)現(xiàn)二叉樹主要利用queue和stack的特點(diǎn),對(duì)于層次遍歷二叉樹主要運(yùn)用queue隊(duì)頭出,隊(duì)尾插入,先進(jìn)先出的特點(diǎn),先將根插入隊(duì)尾,然后輸出隊(duì)頭的元素,同時(shí)將隊(duì)頭的左子樹和右子樹元素插入隊(duì)尾,依次輸出輸出隊(duì)頭的元素,同時(shí)將隊(duì)頭的左子樹和右子樹元素插入隊(duì)尾,直到隊(duì)列為空。
目前創(chuàng)新互聯(lián)已為上千的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)站空間、成都網(wǎng)站托管、企業(yè)網(wǎng)站設(shè)計(jì)、東莞網(wǎng)站維護(hù)等服務(wù),公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略,正道將秉承"和諧、參與、激情"的文化,與客戶和合作伙伴齊心協(xié)力一起成長,共同發(fā)展。
void levelorder()
{
queue<BinaryTreeNode<T> *>s;
if (_root == NULL)
return;
s.push(_root);
while (!s.empty())
{
BinaryTreeNode<T> *front=s.front();
cout << front->_data << " ";
if (front->_left)
s.push(front->_left);
if (front->_right)
s.push(front->_right);
s.pop();
}
}
非遞歸實(shí)現(xiàn)二叉樹前序遍歷主要運(yùn)用stack的先進(jìn)后出的特點(diǎn),先把根壓入棧里,同時(shí)先把左子樹的左子樹元素以此壓入棧底,最后左子樹的最后一個(gè)元素壓入棧底之后,再將棧底元素彈出棧,再判斷棧底最后一個(gè)元素的右子樹,利用以上的方法。代碼如下:
void prevorder()
{
stack<BinaryTreeNode<T> *>s;
if (_root == NULL)
return;
s.push(_root);
while (!s.empty())
{
BinaryTreeNode<T> *cur = s.top();
cout << cur->_data << " ";
s.pop();
if (cur->_right)
s.push(cur->_right);
if (cur->_left)
s.push(cur->_left);
}
}
非遞歸實(shí)現(xiàn)二叉樹中序遍歷主要運(yùn)用stack的先進(jìn)后出的特點(diǎn),先把根壓入棧里,同時(shí)先把左子樹的左子樹元素以此壓入棧底,最后左子樹的最后一個(gè)元素壓入棧底之后,判斷棧底最后一個(gè)元素的右子樹,利用以上的方法。代碼如下:
void inorder()
{
stack<BinaryTreeNode<T> *>s;
if (_root == NULL)
return;
BinaryTreeNode<T> *cur = _root;
while (cur||!s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cout << s.top()->_data << " ";
cur = s.top()->_right;
s.pop();
}
}
非遞歸實(shí)現(xiàn)二叉樹后序遍歷主要運(yùn)用stack的先進(jìn)后出的特點(diǎn),在利用前序和后序的共同特點(diǎn)
void postorder()
{
stack<BinaryTreeNode<T> *>s;
if (_root == NULL)
return;
BinaryTreeNode<T> *cur = _root;
BinaryTreeNode<T> *prev = NULL;
s.push(cur);
while (cur || !s.empty())
{
while (cur->_left&&cur->_left!=prev)
{
s.push(cur->_left);
cur = cur->_left;
}
if (s.top()->_right&&s.top()->_right != prev)
{
cur = s.top()->_right;
s.push(cur);
}
else
{
cout << s.top()->_data << " ";
prev = s.top();
s.pop();
cur = s.top();
cur->_left =NULL;
}
}
}
本文標(biāo)題:非遞歸實(shí)現(xiàn)遍歷二叉樹
URL網(wǎng)址:http://muchs.cn/article2/jpgeoc.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供網(wǎng)站建設(shè)、Google、營銷型網(wǎng)站建設(shè)、網(wǎng)站維護(hù)、移動(dòng)網(wǎng)站建設(shè)、面包屑導(dǎo)航
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)