二叉树的遍历

二叉树的遍历一般分为三种遍历方法，即先序遍历、中序遍历和后序遍历。在中序遍历中,一个节点的前驱,是其左子树的最右下角结点,后继,是其右子树的最左下角结点。在后序遍历中, • 若结点是根结点,则其后继为空; • 若结点是双亲的右子树,或是左子树但双亲无右子树,则其后继为双亲结点; • 若结点是双亲的左子树且双亲有右子树,则其后继为右子树按后序遍历的第一个结点二叉树的遍历实现如下：#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本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-03/115192.htm