這里涉及到二叉樹的非遞歸操作有：先序遍歷、中序遍歷、后序遍歷

====數(shù)據(jù)結(jié)構(gòu)====

樹結(jié)點：
struct?Node
{
????char?data;
????Node?*?left;
????Node?*?right;
};
標(biāo)志：
enum?Tag{goLeft,?goRight,?goBack?}; goLeft指示訪問左子樹
goLeft指示訪問右子樹（左子樹已訪問）
goBack指示回溯(左右子樹均已訪問)

兩個棧:
vector<Node?*>?vec_node;
vector<Tag>?vec_flag; 兩個棧同時消長、空

所有操作相同的部分：
Node?*curNode?=?vec_node.back();//棧頂
Tag?curFlag?=?vec_flag.back();??//棧頂

switch(curFlag)
????????{
????????????case?goLeft:
????????????????//更改標(biāo)志
????????????????vec_flag.pop_back();
????????????????vec_flag.push_back(goRight);

????????????????//左子樹入棧
????????????????if(curNode->left?!=?NULL)
????????????????{
????????????????????vec_node.push_back(curNode->left);
????????????????????vec_flag.push_back(goLeft);
????????????????}
????????????????break;

????????????case?goRight:
????????????????//更改標(biāo)志
????????????????vec_flag.pop_back();
????????????????vec_flag.push_back(goBack);

????????????????//右子樹入棧
????????????????if(curNode->right?!=?NULL)
????????????????{
????????????????????vec_node.push_back(curNode->right);
????????????????????vec_flag.push_back(goLeft);
????????????????}
????????????????break;

????????????case?goBack:
????????????????//結(jié)點出棧
????????????????vec_flag.pop_back();
????????????????vec_node.pop_back();
????????????????break;

????????????default:
????????????????break;
????????}//switch-end
幾種操作唯一不同的是：需要的操作放置的位置不同。
先序遍歷：打印結(jié)點放在goLeft中
中序遍歷：打印結(jié)點放在goRight中
后續(xù)遍歷：打印結(jié)點放在goBack中
打印所有路徑：在goBack中判斷是否為葉子結(jié)點，如果是，打印棧中所有路徑；如果否，直接出棧

詳細代碼見下面:(注意其中紅色的地方是唯一差別的地方：
#include?<iostream>
#include?<vector>
#include?<cstdlib>
using?namespace?std;


struct?Node
{
????char?data;
????Node?*?left;
????Node?*?right;
};

enum?Tag{goLeft,?goRight,?goBack?};

void?PreOrder(Node?*root)
{
????assert(root?!=?NULL);

????vector<Node?*>?vec_node;
????vector<Tag>?vec_flag;
????//init
????vec_node.push_back(root);
????vec_flag.push_back(goLeft);

????while(!vec_node.empty())
????{
????????Node?*curNode?=?vec_node.back();
????????Tag?curFlag?=?vec_flag.back();

????????switch(curFlag)
????????{
????????????case?goLeft:
????????????????cout?<<?curNode->data?<<?"??";
????????????????vec_flag.pop_back();
????????????????vec_flag.push_back(goRight);

????????????????if(curNode->left?!=?NULL)
????????????????{
????????????????????vec_node.push_back(curNode->left);
????????????????????vec_flag.push_back(goLeft);
????????????????}
????????????????break;

????????????case?goRight:
????????????????vec_flag.pop_back();
????????????????vec_flag.push_back(goBack);

????????????????if(curNode->right?!=?NULL)
????????????????{
????????????????????vec_node.push_back(curNode->right);
????????????????????vec_flag.push_back(goLeft);
????????????????}

????????????????break;


????????????case?goBack:
????????????????vec_flag.pop_back();
????????????????vec_node.pop_back();
????????????????break;

????????????default:
????????????????break;
????????}//switch-end
????}//while-end

}

void?InOrder(Node?*root)
{
????assert(root?!=?NULL);

????vector<Node?*>?vec_node;
????vector<Tag>?vec_flag;
????//init
????vec_node.push_back(root);
????vec_flag.push_back(goLeft);

????while(!vec_node.empty())
????{
????????Node?*curNode?=?vec_node.back();
????????Tag?curFlag?=?vec_flag.back();

????????switch(curFlag)
????????{
????????????case?goLeft:
????????????????vec_flag.pop_back();
????????????????vec_flag.push_back(goRight);

????????????????if(curNode->left?!=?NULL)
????????????????{
????????????????????vec_node.push_back(curNode->left);
????????????????????vec_flag.push_back(goLeft);
????????????????}
????????????????break;

????????????case?goRight:
????????????????cout?<<?curNode->data?<<?"??";
????????????????vec_flag.pop_back();
????????????????vec_flag.push_back(goBack);

????????????????if(curNode->right?!=?NULL)
????????????????{
????????????????????vec_node.push_back(curNode->right);
????????????????????vec_flag.push_back(goLeft);
????????????????}

????????????????break;


????????????case?goBack:


????????????????vec_flag.pop_back();
????????????????vec_node.pop_back();
????????????????break;

????????????default:
????????????????break;
????????}//switch-end
????}//while-end

}

void?PostOrder(Node?*root)
{
????assert(root?!=?NULL);

????vector<Node?*>?vec_node;
????vector<Tag>?vec_flag;
????//init
????vec_node.push_back(root);
????vec_flag.push_back(goLeft);

????while(!vec_node.empty())
????{
????????Node?*curNode?=?vec_node.back();
????????Tag?curFlag?=?vec_flag.back();

????????switch(curFlag)
????????{
????????????case?goLeft:
????????????????vec_flag.pop_back();
????????????????vec_flag.push_back(goRight);

????????????????if(curNode->left?!=?NULL)
????????????????{
????????????????????vec_node.push_back(curNode->left);
????????????????????vec_flag.push_back(goLeft);
????????????????}
????????????????break;

????????????case?goRight:
????????????????vec_flag.pop_back();
????????????????vec_flag.push_back(goBack);

????????????????if(curNode->right?!=?NULL)
????????????????{
????????????????????vec_node.push_back(curNode->right);
????????????????????vec_flag.push_back(goLeft);
????????????????}

????????????????break;


????????????case?goBack:
????????????????cout?<<?curNode->data?<<?"??";

????????????????vec_flag.pop_back();
????????????????vec_node.pop_back();
????????????????break;

????????????default:
????????????????break;
????????}//switch-end
????}//while-end

}


/*?打印從根到葉子結(jié)點之路徑?*/
void?PrintPath(?const?vector<Node?*>?&?v?)
{
????vector<?Node?*>::const_iterator?vi;
????for(?vi?=?v.begin();?vi!=v.end();?++vi?)
????{
????????Node?*?n?=?reinterpret_cast<?Node?*>(*vi);
????????cout<<?n->data<<?"?";
????}
????cout<<?endl;
}

void?PrintAllPaths(Node?*root)
{
????assert(root?!=?NULL);

????vector<Node?*>?vec_node;
????vector<Tag>?vec_flag;
????//init
????vec_node.push_back(root);
????vec_flag.push_back(goLeft);

????while(?!vec_node.empty())
????{
????????Node?*curNode?=?vec_node.back();
????????Tag?curFlag?=?vec_flag.back();


????????switch(curFlag)
????????{
????????????case?goLeft:
????????????????vec_flag.pop_back();
????????????????vec_flag.push_back(goRight);

????????????????if(curNode->left?!=?NULL)
????????????????{
????????????????????vec_node.push_back(curNode->left);
????????????????????vec_flag.push_back(goLeft);
????????????????}
????????????????break;

????????????case?goRight:
????????????????vec_flag.pop_back();
????????????????vec_flag.push_back(goBack);

????????????????if(curNode->right?!=?NULL)
????????????????{
????????????????????vec_node.push_back(curNode->right);
????????????????????vec_flag.push_back(goLeft);
????????????????}

????????????????break;


????????????case?goBack:
????????????????if(NULL?==?curNode->left?&&?NULL?==?curNode->right)
????????????????????PrintPath(vec_node);

????????????????vec_flag.pop_back();
????????????????vec_node.pop_back();
????????????????break;

????????????default:
????????????????break;
????????}//switch-end
????}//while-end
}

int?main()
{
????Node?root,?b,?c,?d,?e,?f,?g,?h;
????root.data='a';
????root.left=&b;
????root.right=&e;

????b.data='b';
????b.left=&c;
????b.right=&d;

????c.data='c';
????c.left=NULL;
????c.right=NULL;

????d.data='d';
????d.left=NULL;
????d.right=NULL;

????e.data='e';
????e.left=&f;
????e.right=&g;

????f.data='f';
????f.left=NULL;
????f.right=NULL;

????g.data='g';
????g.left=NULL;
????g.right=&h;

????h.data='h';
????h.left=NULL;
????h.right=NULL;


????cout?<<?"Print?all?paths:\n";
????PrintAllPaths(&root);
????cout?<<?"\n";

????cout?<<?"PostOrder:\n";
????PostOrder(&root);
????cout?<<?"\n";

????cout?<<?"PreOrder:\n";
????PreOrder(&root);
????cout?<<?"\n";

????cout?<<?"InOrder:\n";
????InOrder(&root);
????cout?<<?"\n\n";

????system("PAUSE");
????return?0;
}

運行結(jié)果：

轉(zhuǎn)載于:https://www.cnblogs.com/chio/archive/2007/10/24/935784.html

總結(jié)

以上是生活随笔為你收集整理的二叉树的非递归操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。