本文的copyleft归gfree.wind@gmail.com所有,使用GPL发布,可以自由拷贝,转载。但转载请保持文档的完整性,注明原作者及原链接,严禁用于任何商业用途。
作者:gfree.wind@gmail.com
博客:linuxfocus.blog.chinaunix.net
最近需要复习一下基础算法,今天先来个二叉树的几种遍历方式的伪代码吧。
其中每种遍历方式都分为递归和非递归两种。
下面的代码我没有进行优化,可能代码有些冗余,不够简洁。因为没有真正的进行严格的测试,只是在纸上画了话,走了一下流程,欢迎大家指正错误。在代码中使用access作为访问节点数据的方式。其实最好的方法是将access作为类型为函数指针的参数,但是今天只为了温习一下实现,而不是真正的去写代码。就按照简单的来了。
对于非递归的实现,在上学的时候,当时并没有真正理解为什么要这样实现,来消除递归。现在我会把将递归转为非递归的过程描述得清楚一些。
1. 先序遍历:先访问根节点,然后遍历左子树,最后遍历右子树
a) 递归算法
- void preorder_traverse(const struct bi_tree *tree)
-
{
-
if (tree) {
- /* 访问根节点*/
-
access(tree->data);
-
if (tree->left) {
- /* 访问左节点 */
-
preorder_traverse(tree->left);
-
}
-
if (tree->right) {
- /* 访问右节点 */
- preorder_traverse(tree->right);
-
}
-
}
-
}
递归实现太简单了,而且非常清晰,便于理解。
b) 非递归算法
- void preorder_traverse(const struct bi_tree *tree)
-
{
-
/*
- 为什么要选择用栈呢。
- 当我们遍历先序遍历二叉树时,按照先序的定义,先根节点,然后左节点,然后在右节点。
- 这样当按照不断地访问左节点而向下时,为了以后打印右节点,所以需要保存右节点。
- 之所以选择栈保存,因为打印右节点顺序与栈的特性先进后出相符,所以选择栈来保存右节点。
后面的其他遍历方式,同样因为上面这个原因选择栈作为非递归遍历的一个保存方式。
-
*/
-
struct stack s;
-
-
init_stack(&s);
-
-
const struct node *n = tree;
-
-
while (n) {
- /* 访问节点 */
-
access(n->data);
/* 该节点有左子节点,需要不断的往下遍历 */
-
while (n->left) {
- /* 有右节点,那么将右节点压栈 */
-
if (n->right) {
-
s.push(n->right);
-
}
-
- /* 移到左节点 */
-
n = n->left;
- /* 访问该节点,在这里也可看作新的根节点 */
-
access(n->data);
-
}
/* 开始访问右节点 */
if (n->right) {
/* 移到右节点 */
n = n->right;
}
else {
/* 需要弹出上一个保存的右节点 */
n = s.pop();
}
-
}
-
}
2. 中序遍历:先遍历左子树,然后根节点,最后是右子树
a) 递归算法
- void midorder_traverse(const struct bi_tree *tree)
-
{
-
if (tree->left) {
-
midorder_traverse(tree->left);
-
}
-
access(tree->data);
-
if (tree->right) {
-
midorder_traverse(tree->right);
-
}
-
}
递归实现就是简单啊
b) 非递归算法
- void midorder_traverse(const struct bi_tree *tree)
-
{
-
struct stack s;
-
-
init_stack(&s);
-
-
const struct node *n = tree;
-
-
while (n) {
/* 不断的沿左节点向下走 */
-
while (n->left) {
-
s.push(n);
- n = n->left;
-
}
/* 访问节点*/
-
access(n->data);
/* 弹出父节点 */
-
while (n = s.pop()) {
- access(n->data)
-
if (n->right) {
- /* 如果父节点有右节点,那么需要再次检查该右节点的左节点*/
-
break;
-
}
- /* 没有右节点,继续弹出保存的节点 */
- }
-
}
-
}
3. 后序遍历:先左节点,然后右节点,最后根节点
a) 递归算法
- void lastorder_traverse(const struct bi_tree *tree)
-
{
-
if (tree->left) {
-
lastorder_traverse(tree->left);
-
}
-
if (tree->right) {
-
lastorder_traverse(tree->right);
-
}
-
access(tree->data);
-
}
不得不感叹递归的实现太简单了。。。
b) 非递归算法
之前的写法有错误,当从栈中弹出节点时,且该节点又有右子节点时,需要再次尝试先遍历该右子节点的所有左子节点时,会将该节点丢失。
那么,这时需要重新将该节点压栈,但是当再次弹出时,需要区分其右子节点是否已经遍历过了。所有在节点中添加了一个成员变量access。当被access函数访问时,该access被置位。
还有一个想法,看是否能够避免引入这个成员变量,暂时还没有答案。
- void lastorder_traverse(const struct bi_tree *tree)
-
{
-
struct stack s;
-
-
init_stack(&s);
-
-
const struct node *n = tree;
-
-
while (n) {
- /* 沿左节点向下走 */
-
while (n->left) {
-
s.push(n);
-
n = n->left;
-
}
-
-
do {
- /* 如果有右节点,仍然需要检查左节点 */
-
if (n->right && !n->right->access) {
- /* 右节点还未访问过,需要把该节点再次压栈 */
- s.push(n);
-
n = n->right;
-
break;
-
}
/* 没有右节点,访问节点, 并弹出上一个父节点 */
-
access(n->data);
-
} while (n = s.pop());
-
}
-
}
4. 按层访问:从根节点,由上及下,由左向右访问节点
a) 递归算法:
这个。。。这个。。。似乎没有递归的用武之地呵。。。
b) 非递归算法:
- void layorder_traverse(const struct bi_tree *tree)
-
{
- /*
- 这里选用queue而非stack,因为这种遍历方式需要的是FIFO,即先进先出
- */
-
struct queue q;
-
-
init_queue(&q);
-
-
const struct node *n = tree;
-
-
while (n) {
- /* 访问节点 */
-
access(n->data);
-
if (n->left) {
- /* 将左节点放入队列 */
-
q.push(n);
-
}
-
if (n->right) {
- /* 将右节点放入队列 */
-
q.push(n);
-
}
/* 取出下一个节点 */
- n = q.pop();
-
}
-
}
再次说明,以上代码未经测试,只是我在纸上简单的画了画,想了一下流程。思路基本上应该没有什么问题,再次欢迎大家指正。
阅读(402) | 评论(0) | 转发(0) |