数据结构-二叉树的非递归遍历

Myth丶恋晨 2022-05-12 13:24 229阅读 0赞

前面的章节我们实现了二叉树最基本的遍历方式：递归遍历，代码是如此的简洁；辣么我们为什么还要去学习二叉树的非递归遍历方式呢？众所周知，递归优点是将可以将复杂的问题简单化即大问题拆分成一个个小问题，那么它的缺点是什么呢？缺点就是效率低。对于一个算法来说，其中最重要的一个点就是效率，如果一个算法效率低下，辣么它被使用的概率就很低，因为我们每时每刻都在追求最优解~

对于二叉树的非递归遍历我们可以借助栈来实现，下面我们给出先序遍历和中序遍历非递归算法的其中一种：

//
    // Created by Administrator on 2018/6/5.
    //
    /**
     * 二叉树的非递归遍历：先序遍历、中序遍历
     */
    #include "stdio.h"
    #include "stdlib.h"
    
    /**
     * 定义一棵树
     */
    typedef struct {
        char data;
        struct BitTreeNode *lchild, *rchild;
    } BitTreeNode, *BitTree;
    
    
    /**
     * 定义一个栈
     */
    #define MaxSize 100
    typedef struct {
        BitTree data[MaxSize];//数据域，树节点指针
        int top;//下标索引
        int currentSize;//栈当前大小
    } Stack2;
    
    /**
     * 初始化栈
     * @param stack2
     */
    void initStack2(Stack2 *stack2) {
        stack2->top = -1;
        stack2->currentSize = 0;
    }
    
    /**
     * 入栈操作
     * @param stack2
     * @param node
     */
    void push2(Stack2 *stack2, BitTree node) {
        if (stack2->currentSize == MaxSize) {
            //栈已满
            printf("很遗憾告诉你：栈已满~\n");
            return;
        }
        stack2->top++;
        stack2->data[stack2->top] = node;
        stack2->currentSize++;
    }
    
    /**
     * 出栈操作
     * @param stack2
     * @return
     */
    BitTree pop2(Stack2 *stack2) {
        if (stack2->currentSize == 0) {
            printf("很遗憾告诉你：栈已空~\n");
            return NULL;
        }
        BitTree node = stack2->data[stack2->top];
        stack2->top--;
        stack2->currentSize--;
        return node;
    }
    
    
    /**
     * 前序法创建树
     * @param tree
     * @return
     */
    BitTree createTree(BitTree tree) {
        char c;
        scanf("%c", &c);
        if (c == '#') {
            return NULL;
        } else {
            tree = (BitTree) malloc(sizeof(BitTreeNode));
            tree->data = c;
            tree->lchild = createTree(tree->lchild);
            tree->rchild = createTree(tree->rchild);
        }
        return tree;
    }
    
    /**
     * 前序法遍历树
     * @param tree
     * @param s
     */
    void preOrder2(BitTree tree, Stack2 *s) {
        if (tree) {
            printf("%c", tree->data);
            preOrder2(tree->lchild, s);
            preOrder2(tree->rchild, s);
        }
    }
    
    void visit(int data) {
        printf("%c", data);
    }
    
    /**
     *中序遍历非递归算法
     * @param tree
     * @param s
     */
    void inOrderNoRec(BitTree tree, Stack2 *s) {
        BitTree p = tree;
        while (p || s->currentSize > 0) {
            if (p) {
                push2(s, p);
                p = p->lchild;
            } else {
                p = pop2(s);
                visit(p->data);
                p = p->rchild;
            }
        }
    }
    
    /**
     * 先序非递归遍历
     * @param tree
     * @param s
     */
    void preOrderNoRec(BitTree tree, Stack2 *s) {
        BitTree p = tree;
        while (p || s->currentSize > 0) {
            if (p) {
                push2(s, p);
                visit(p->data);
                p = p->lchild;
            } else {
                p = pop2(s);
                p = p->rchild;
            }
        }
    }
    
    
    int main() {
        Stack2 stack2;
        initStack2(&stack2);
        BitTree tree;
        tree = createTree(tree);
        printf("前序递归遍历结果：\n");
        preOrder2(tree, &stack2);
        printf("\n先序非递归遍历结果：\n");
        preOrderNoRec(tree, &stack2);
        printf("\n中序非递归遍历结果：\n");
        inOrderNoRec(tree, &stack2);
    }

![70][]

[70]: /images/20220504/1b0f1208fc734697b82bb251ab0173e8.png