二叉樹的4種遍歷方法：前序遍歷，中序遍歷，後序遍歷，層次遍歷
看遍歷的方法之前，先看下二叉樹類的聲明：
class ctree
{
public:
//此處為了簡化，使用了共有數據
//數據類型使用了char,若想寫成通用的類，可以使用template < class T>聲明模板類
char treevalue;
ctree *childleft,*childright;
ctree();
};
二叉樹是遞歸結構，每一個節點都有對應的值以及左右子節點，也就是說，對於二叉樹節點的訪問，其實只需要3步即可：訪問根節點，訪問左子節點左子樹），訪問右子節點右子樹）。
根據訪問節點的順序不同，於是產生了3中不同的訪問方法，那就是：前序遍歷，中序遍歷，後序遍歷。
下面是3種方法的實現，主要是使用遞歸函數實現）
前序遍歷：
void preorderoutput(ctree *tree)
{
if (NULL != tree)
{
cout << tree->treevalue << " ";
preorderoutput(tree->childleft);
preorderoutput(tree->childright);
}
}
中序遍歷：
void inorderoutput(ctree *tree)
{
if (NULL != tree)
{
inorderoutput(tree->childleft);
cout << tree->treevalue << " ";
inorderoutput(tree->childright);
}
}
後序遍歷：
void postorderoutput(ctree *tree)
{
if (NULL != tree)
{
postorderoutput(tree->childleft);
postorderoutput(tree->childright);
cout << tree->treevalue << " ";
}
}
以上是3種遞歸調用的遍歷方法，但是有時候也是需要根據二叉樹的層次來遍歷的。
層次遍歷：
void levelorderoutput(ctree *tree)
{
//將當前能夠訪問到但是未訪問的節點存到隊列中，其實存的就是當前節點的子節點
queue<ctree*> treequeue;
ctree *ptree;
treequeue.push(tree);
while (!treequeue.empty())
{
//訪問當前節點
ptree = treequeue.front();
//將訪問過的節點刪除
treequeue.pop();
cout << ptree->treevalue << " ";
//如果存在左子節點，將左子節點插入隊列中
if (NULL != ptree->childleft)
{
treequeue.push(ptree->childleft);
}
//如果存在右子節點，將右子結點插入隊列中
if (NULL != ptree->childright)
{
treequeue.push(ptree->childright);
}
}
}
本文出自 “adwen2010” 博客，請務必保留此出處http://adwen2010.blog.51cto.com/1820717/1290649
