二叉樹的遍歷一般分為三種遍歷方法，即先序遍歷、中序遍歷和後序遍歷。在中序遍歷中,一個節點的前驅,是其左子樹的最右下角結點,後繼,是其右子樹的最左下角結點。
在後序遍歷中,
• 若結點是根結點,則其後繼為空;
• 若結點是雙親的右子樹,或是左子樹但雙親無右子樹,則其後繼為雙親結點;
• 若結點是雙親的左子樹且雙親有右子樹,則其後繼為右子樹按後序遍歷的第一個結點
二叉樹的遍歷實現如下：
#include <stack>
#include <queue>
/*
*@struct
*@brief 二叉樹結點
*/
typedef struct binary_tree_node_t
{
binary_tree_node_t *lchild; /* 左孩子 */
binary_tree_node_t *rchild; /* 右孩子 */
void* data; /* 結點的數據 */
}binary_tree_node_t;
/**
* @brief 先序遍歷,遞歸.
* @param[in] root 根結點
* @param[in] visit 訪問數據元素的函數指針
* @return 無
*/
void pre_order_r(const binary_tree_node_t *root, int (*visit)(void*))
{
if(root != NULL)
{
(void)visit(root->data);
pre_order_r(root->lchild, visit);
pre_order_r(root->rchild, visit);
}
}
/**
* @brief 中序遍歷,遞歸.
*/
void in_order_r(const binary_tree_node_t *root, int (*visit)(void*))
{
if(root != NULL)
{
pre_order_r(root->lchild, visit);
(void)visit(root->data);
pre_order_r(root->rchild, visit);
}
}
/**
* @brief 後序遍歷,遞歸.
*/
void post_order_r(const binary_tree_node_t *root, int (*visit)(void*))
{
if(root != NULL)
{
pre_order_r(root->lchild, visit);
pre_order_r(root->rchild, visit);
(void)visit(root->data);
}
}
/**
* @brief 先序遍歷,非遞歸.
*/
void pre_order(const binary_tree_node_t *root, int (*visit)(void*))
{
const binary_tree_node_t *p;
std::stack<const binary_tree_node_t *> s;
p = root;
if(p != NULL)
{
s.push(p);
}
while(!s.empty())
{
p = s.top();
s.pop();
visit(p->data);
if(p->rchild != NULL)
{
s.push(p->rchild);
}
if(p->lchild != NULL)
{
s.push(p->lchild);
}
}
}
/**
* @brief 中序遍歷,非遞歸.
*/
void in_order(const binary_tree_node_t *root, int (*visit)(void*))
{
const binary_tree_node_t *p;
std::stack<const binary_tree_node_t *> s;
p = root;
while(!s.empty() || p!=NULL)
{
if(p != NULL)
{
s.push(p);
p = p->lchild;
}
else
{
p = s.top();
s.pop();
visit(p->data);
p = p->rchild;
}
}
}
/**
* @brief 後序遍歷,非遞歸.
*/
void post_order(const binary_tree_node_t *root, int (*visit)(void*))
{
/* p,正在訪問的結點,q,剛剛訪問過的結點 */
const binary_tree_node_t *p, *q;
std::stack<const binary_tree_node_t *> s;
p = root;
do {
while(p != NULL)
{
/* 往左下走 */
s.push(p);
p = p->lchild;
}
q = NULL;
while(!s.empty())
{
p = s.top();
s.pop();
/* 右孩子不存在或已被訪問,訪問之 */
if(p->rchild == q)
{
visit(p->data);
q = p; /* 保存剛訪問過的結點 */
}
else
{
/* 當前結點不能訪問,需第二次進棧 */
s.push(p);
/* 先處理右子樹 */
p = p->rchild;
break;
}
}
}while(!s.empty());
}
/**
* @brief 層次遍歷,也即 BFS.
*
* 跟先序遍歷一模一樣,唯一的不同是棧換成了隊列
*/
void level_order(const binary_tree_node_t *root, int (*visit)(void*))
{
const binary_tree_node_t *p;
std::queue<const binary_tree_node_t *> q;
p = root;
if(p != NULL)
{
q.push(p);
}
while(!q.empty())
{
p = q.front();
q.pop();
visit(p->data);
if(p->lchild != NULL)
{
/* 先左後右或先右後左無所謂 */
q.push(p->lchild);
}
if(p->rchild != NULL)
{
q.push(p->rchild);
}
}
}
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
