二叉树的遍历

二叉树的遍历

二叉树的遍历一般分为三种遍历方法，即先序遍历、中序遍历和后序遍历。在中序遍历中,一个节点的前驱,是其左子树的最右下角结点,后继,是其右子树的最左下角结点。

　　在后序遍历中,

　　•　　若结点是根结点,则其后继为空;

　　•　　 若结点是双亲的右子树,或是左子树但双亲无右子树,则其后继为双亲结点;

　　•　　 若结点是双亲的左子树且双亲有右子树,则其后继为右子树按后序遍历的第一个结点

二叉树的遍历实现如下：

#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);
　　　　}
　　}
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

本文永久更新链接地址：