top
友情提示
测试消息
确定
友情提示

处理中,请稍后...

二叉树非递归遍历
上一篇文章说到了二叉树,简单实现了一下二叉树的基本操作,用常规的递归思想测试了二叉树的遍历。本篇文章我们来探讨一下二叉树的非递归遍历。【提示:请忽略文章中 “结点”“节点”的混用,懒得改了,输入法承担一半责任】

二叉树的非递归遍历除了前、中、后序遍历外,还有一个层序遍历。前三者常用堆栈辅助完成遍历过程,层序遍历则借助队列完成。本篇文章只探讨前中后三种遍历算法的非递归实现。

在此之前,我们需要准备一个可用的“堆栈”。堆栈不用多解释了,实现方式很多,每个人的写法和实现思路或许都会有一些不一样,但是只要能达到设计目 ”后进先出“ 就行了。此处我也简单实现了一下,简单测试完毕,不排除有潜在问题,仅供参考
stack.h
#ifndef STACK_H
#define STACK_H

#include "misc.h"
#include <stdio.h>
#include <stdlib.h>

stack_t * initStack();
void traverseStackReverse(stack_t * stack, void (*callBack)());
void traverseStack(stack_t * stack, void (*callBack)());
int isStackEmpty(stack_t *stack);
stackDataType popData(stack_t *stack);
int pushData(stack_t *stack, stackDataType data);
stackDataType getTopData(stack_t *stack);
void destroyStack(stack_t **stack);

#endif // STACK_H

由于此次测试需要用到上一篇中二叉树相关的东西,所以增加了一个额外的文件:misc.h
#ifndef MISC_H
#define MISC_H

typedef int dataType;  //数据类型,简单测试,将 DataType 设置为 int

//节点类型
typedef struct nodeData{
    struct nodeData *leftChild;
    struct nodeData *rightChild;
    dataType data;
}node_t;

//堆栈数据类型
typedef node_t stackDataType;

//堆栈数据结点结构
typedef struct stackNode{
     struct stackNode *pre;
     struct stackNode *next;
     stackDataType data;
}stackNode_t;  //堆栈结点类型

//堆栈结构
typedef struct myStack{
    int size;
    stackNode_t *node;
    stackNode_t * stackPointer;
}stack_t;

#endif // MISC_H

stack.c
#include "stack.h"


/**
*初始化堆栈
*/
stack_t * initStack(){

    stack_t *temp = (stack_t *)malloc(sizeof(stack_t));
    if(temp == NULL){
        printf("\nERROR : memory initial error!\n");
        return NULL;
    }

    temp->size = 0;
    temp->stackPointer = NULL;
    temp->node = NULL;

    return temp;
}

/**
*入栈操作
*/
int pushData(stack_t *stack, stackDataType data){

    if(stack == NULL){
        printf("\nERROR: stack is NULL\n");
        return -1;
    }

    if(stack->size == 0){
        stack->node = (stackNode_t *)malloc(sizeof(stackNode_t));
        if(stack->node == NULL){
            printf("\nERROR : push data failed, memory initial error!\n");
            return -1;
        }
        stack->node->next = NULL;
        stack->node->pre = NULL;
        stack->node->data = data;
        stack->size++;
        stack->stackPointer = stack->node;
        return 0;
    }

    stack->stackPointer->next = (stackNode_t *)malloc(sizeof(stackNode_t));
    if(stack->stackPointer->next == NULL){
        printf("\nERROR : push data failed, memory initial error!\n");
        return -1;
    }
    stack->size++;
    stack->stackPointer->next->data = data;
    stack->stackPointer->next->pre = stack->stackPointer;
    stack->stackPointer->next->next = NULL;
    stack->stackPointer = stack->stackPointer->next;
    return 0;

}

/**
*弹出栈顶元素
*/
stackDataType popData(stack_t *stack){
    if(stack == NULL){
        printf("\nERROR: stack is NULL!\n");
        return;
    }

    if(stack->size <= 0){
        printf("\nERROR: stack is empty!\n");
        return;
    }

    stackNode_t *temp = stack->stackPointer;
    stack->stackPointer = stack->stackPointer->pre;
    if(stack->stackPointer != NULL){
        stack->stackPointer->next = NULL;
    }
    stack->size--;
    sizeof(temp->data);
    return temp->data;
    free(temp);
}

/**
*获取栈顶元素
*/
stackDataType getTopData(stack_t *stack){
    if(stack == NULL){
        printf("\nERROR: stack is NULL!\n");
        return;
    }

    if(stack->size <= 0){
        printf("\nERROR: stack is empty!\n");
        return;
    }

    return stack->stackPointer->data;
}

/**
*堆栈是否为空
*@return int  :  空 ----- 1
              :非空 ----- 0
*/
int isStackEmpty(stack_t *stack){
    if(stack == NULL){
        printf("\nERROR:stack is NULL\n");
        return -1;
    }

    return stack->size == 0 ? 1 : 0;
}

/**
*堆栈元素遍历
*/
void traverseStack(stack_t * stack, void (*callBack)()){

    if(stack == NULL){
        printf("\nERROR:stack is NULL\n");
        return;
    }

    if(stack->size == 0){
        printf("\nWARNING : stack is empty\n");
        return;
    }

    stackNode_t *temp = stack->stackPointer;
    while(temp != NULL){
        callBack(temp->data);
        temp = temp->pre;
    }
}

/**
*堆栈元素遍历(反序)
*/
void traverseStackReverse(stack_t * stack, void (*callBack)()){

    if(stack == NULL){
        printf("\nERROR:stack is NULL\n");
        return;
    }

    if(stack->size == 0){
        printf("\nWARNING : stack is empty\n");
        return;
    }

    stackNode_t *temp = stack->node;
    while(temp != NULL){
        callBack(temp->data);
        temp = temp->next;
    }
}


/**
*销毁堆栈
*/
void destroyStack(stack_t **stack){

    if(*stack == NULL){
        return;
    }

    if((*stack)->size != 0){
        stackNode_t *temp = (*stack)->node;
        stackNode_t *temp1 = temp;
        while(temp != NULL){
            temp1 = temp;
            temp = temp->next;
            free(temp1);
        }
    }

    free(*stack);
    *stack = NULL;
}

测试:main函数
int main(){
    node_t *p;
    //初始化
    node_t *tree = initBiTree();
    tree->data = 10;
    p = insertRightChildByData(tree, 20);
    p = insertLeftChildByData(p, 50);
    insertRightChildByData(p, 60);
    insertLeftChildByData(p, 70);
    p = insertLeftChildByData(tree, 30);
    insertLeftChildByData(p, 40);
    /*构建了如下结构的二叉树

                10
               /  \
             30    20
            /     /
          40     50
                /  \
               70   60

    */

    //遍历输出
    printf("============= 二叉树遍历(递归方式) ===========\n");
    puts("former: ");
    formerTraversal(tree, visitNodeAction);
    puts("\nin: ");
    inTraversal(tree, visitNodeAction);
    puts("\nafter: ");
    afterTraversal(tree, visitNodeAction);


    /*********** 堆栈测试 ***********/
    printf("\n\n============= 堆栈测试 ===========\n");
    stackDataType data1 = {NULL, NULL, 1};
    stackDataType data2 = {NULL, NULL, 2};
    stackDataType data3 = {NULL, NULL, 3};
    //构建堆栈
    stack_t *stack = initStack();
    pushData(stack, data1);
    pushData(stack, data2);
    pushData(stack, data3);

    //输出堆栈
    printf("size: %d\n", stack->size);
    traverseStack(stack, visitStack);
    puts("");
    traverseStackReverse(stack, visitStack);
    //获取栈顶元素
    printf("\ntop data: %d\n", getTopData(stack).data);
    //弹出栈顶元素
    printf("data: %d\n", popData(stack).data);
    printf("size: %d\n", stack->size);
    traverseStack(stack, visitStack);
    puts("");
    traverseStackReverse(stack, visitStack);

    printf("\n\n============= 结合堆栈进行二叉树非递归遍历 ===========\n");
    /********  结合堆栈进行二叉树非递归遍历  *********/
    puts("前序遍历(非递归):");
    preOrder(tree, visitNodeAction);
    puts("\n中序遍历(非递归):");
    inOrder(tree, visitNodeAction);
    puts("\n后序遍历(非递归):");
    postOrder(tree, visitNodeAction);

    //销毁二叉树
    destroyBiTree(&tree);
    //销毁堆栈
    destroyStack(&stack);

    return 0;

}

以上只是部分代码,如果您觉得网页不便查看代码,可以下载完整源文件点击此处下载


前序(先序)遍历
先序遍历比较简单,也容易理解,只要保证根节点在子节点之前访问即可。实现步骤:
(1)初始化堆栈
(2)将根节点入栈
(3)当堆栈非空时,循环执行 a、b、c 三步:
        a、出站一个结点,访问该节点
        b、若该节点的右孩子节点非空,则入栈该节点的右孩子节点
        c、若该节点的左孩子节点非空,则入栈该节点的左孩子结点
(4)结束
C语言实现:
/**
*前序(先序)遍历(非递归方式)
*@param tree    :  待遍历二叉树根节点
*@param callack :  回调函数
*/
void preOrder(node_t *tree, void (*callback)()){

    stack_t *stack = initStack();
    node_t temp;
    pushData(stack, *tree);

    while(!isStackEmpty(stack)){
        temp = popData(stack);
        callback(&temp);
        if(temp.rightChild != NULL){
            pushData(stack, *temp.rightChild);
        }
        if(temp.leftChild != NULL){
            pushData(stack, *temp.leftChild);
        }
    }

    destroyStack(&stack);
}


中序遍历
实现步骤:
(1)初始化堆栈
(2)当临时结点不为空或者堆栈不为空的情况下循环执行以下操作:
         a、若临时节点不为空将临时结点指向的当前节点入栈,并让当前节点指向其左孩子节点
         b、若临时结点为空,则出栈一个元素,访问该元素,之后让当前节点指向出栈元素的右孩子节点
(3)结束遍历
C语言实现:
/**
*中序遍历(非递归方式)
*@param tree    :  待遍历二叉树根节点
*@param callack :  回调函数
*/
void inOrder(node_t *tree, void (*callback)()){

    stack_t *stack = initStack();
    node_t *node = tree;
    node_t temp;

    while(node != NULL || !isStackEmpty(stack)){
        if(node != NULL){
            pushData(stack, *node);
            node = node->leftChild;
        }else{
            temp = popData(stack);
            callback(&temp);
            node = temp.rightChild;
        }
    }

    destroyStack(&stack);
}


后序遍历
后序遍历相交于以上两者而言稍微复杂了一些,如果依旧用一个堆栈来操作的话过程很繁琐,期间还需要对一些节点作标记。

注意到 后序遍历 对比 前序遍历的反向过程 非常类似,所以可以借助两个堆栈,堆栈一主要是做一个临时枢纽,每个节点都先入堆栈一,不作访问,堆栈2保留最终待访问的顺序,最后依次输出堆栈2进行访问即可。【或许我描述的不够准确,直接看代码即可】
C语言实现
/**
*后序遍历(非递归方式)
*@param tree    :  待遍历二叉树根节点
*@param callack :  回调函数
*/
void postOrder(node_t *tree, void (*callback)()){
    //利用两个堆栈进行操作
    stack_t *stack = initStack();
    stack_t *stackParent = initStack();
    node_t node;
    pushData(stack, *tree);

    //细心的你可能会发现此步骤和前序遍历有些相似
    //实际上原理一致,仔细对比前序遍历和后序遍历的过程,它们很相似,##但又不仅仅是直接反序那么简单##
    while(!isStackEmpty(stack)){
        node = popData(stack);
        pushData(stackParent, node);
        //此处必须左孩子结点在右孩子结点之前入栈,
        //因为后面出站再入栈(stackParent)又会有一个顺序的转变
        //只有这样才能保证最终遍历结果是正确的(此处体现“但又不仅仅是直接反序那么简单”这句话)
        if(node.leftChild != NULL){
            pushData(stack, *node.leftChild);
        }
        if(node.rightChild != NULL){
            pushData(stack, *node.rightChild);
        }
    }

    while(!isStackEmpty(stackParent)){
        node = popData(stackParent);
        callback(&node);
    }

    //销毁堆栈
    destroyStack(&stack);
    destroyStack(&stackParent);
}


测试结果:
============= 二叉树遍历(递归方式) ===========
former:
 10  30  40  20  50  70  60
in:
 40  30  10  70  50  60  20
after:
 40  30  70  60  50  20  10

============= 堆栈测试 ===========
size: 3
 3  2  1
 1  2  3
top data: 3
data: 3
size: 2
 2  1
 1  2

============= 结合堆栈进行二叉树非递归遍历 ===========
前序遍历(非递归):
 10  30  40  20  50  70  60
中序遍历(非递归):
 40  30  10  70  50  60  20
后序遍历(非递归):
 40  30  70  60  50  20  10


总结
以上简单实现了一下二叉树的非递归遍历,对比递归方式的实现,非递归还是显得有些麻烦。当然并不是说非递归实现不好,此处没有孰好孰坏的说法,只有合不合适的说法。递归固然方便理解和实现且速度快,但是其有一个不可忽视的缺点,那就是内存占用很大,如果一棵非常大的二叉树用常规的递归算法去遍历,每一个结点都是一次递归的调用,这样下来会占用非常大的内存资源,非递归实现对于内存的占用则好很多。所以不同情况下对于遍历算法的选择也是有很多考虑因素的。

完整源文件在文章中已给出链接。此外查看系列文章只需点击文章下面的标签即可

以上只是我个人的见解,能力有限,难免会出错,若您发现问题或者您有不同看法,欢迎留言。


【原创内容,转载请注明出处】


 
标签
数据结构
算法
二叉树
遍历
非递归
上一篇:经典数据结构之二叉树
下一篇:又是一个忙碌的月份
文章阅读完了, 快到评论区留下你的看法吧!
Email:
验证码:
昵 称 :
评论列表
热门标签
今日倒计时
小时 分钟
年少不识曲中意,再听已是曲中人
加油吧骚年
文章分类
最新文章
浏览排行
分享

关于友情链接

友情链接申请请到留言板块留言。注明网站名称及网址。期待您的友链,欢迎留言。
最新留言
[2018/04/07]太难找了,找到了
[2018/03/20]Entry fileTemplates//Singleton.java.ft not found in C:/Dev/android-studio/lib/resources_en.jar 该错误对我们使用AS没有影响吗?为什么复制保存后重新创建一个新的之后这个错误又出现了?
[2018/01/23]815cce30b85eb6b7ee7930c09135fcf7好漂亮的博客空间啊
[2018/01/06]好漂亮的博客.......
[2017/12/26]试试水
[2017/12/20] 博主可以分享一下这个源码不, 很喜欢这个博客
[2017/11/19]你加我友链了????
[2017/11/19]你的alert 很不友好哈
[2017/11/19]友链已添加
[2017/11/19]路过帮踩。
Copyright © 2018 DevSONG . All rights reserved. 有疑问或者建议? 留言给我或者E-mail me
滇ICP备17002307号-3