二叉树的先序和中序遍历的非递归实现

标签（空格分隔）：数据结构与算法

学习一种数据结构,重点是学习两点:1.这种数据结构的存储结构的实现,2.这种数据结构上的操作.

对于二叉树这种数据结构,它与线性表不同,他是一种非线性的数据结构,单纯的向二叉树中添加``插入,删除没有意义的,因为数据间的逻辑关系是未知的,我们一般根据不同的业务需求,选择特定的二叉树,如二叉搜索树,B+树,红黑树.这些树中各个结点间的数据元素存在着一定的逻辑关系,因此对数据修改时,总是遵循着这棵树的定义.

但是,假设有了一个树,这时你不用修改树,只需要遍历,这时,就很通用了,一般我们知道树的遍历有四中先序遍历,中序遍历,后序遍历,和层序遍历.

今天我们就来看看先序遍历和中序遍历.这两个是最简单的.

中序遍历

从定义上看,中序遍历:先访问左子树,再访问根节点,最后访问右子树.这样我们就很容易写出其递归实现

下面我们给出这可树的定义和其中序的递归实现:

typedef int ElementType;
struct TNode {
    ElementType data;
    TNode *left;
    TNode *right;

};
typedef TNode *PTNode;
typedef PTNode BinTree;
/**
* 中序遍历的递归实现
*/
void InOrderTraverse(BinTree T, Status(*visit)(ElementType e)) {
    if(T == nullptr) return;
    //先访问左子树
    InOrderTraverse(T->left,visit);
    //访问该结点
    visit(T->data);
    //最后访问右子树
    InOrderTraverse(T->right,visit);
}

上面的代码很容易理解,但是我们知道,递归实现实际上是函数的入栈,栈空间比较宝贵,下面我们就来用非递归实现,
思路:根据中序遍历的定义,我们得出以下信息:第一次进过该结点时,不访问,回来的时候,第二次进过才访问该结点.因此我们需要保存途径的节点,而且是按着一定的顺序保存,而这个来回进过,正好和我们的线性表的栈一样,因此我们可以准备一个栈的数据结构来保存.下面看代码:

#include <iostream>

//返回值的状态
typedef enum Status {
    OK = 0, ERROR = 1
};

//二叉树数据域的类型定义
typedef int ElementType;
struct TNode {
    ElementType data;
    TNode *left;
    TNode *right;

};
typedef TNode *PTNode;
typedef PTNode BinTree;

//******定义堆栈*********//
struct SNode {
    PTNode data;
    SNode *next;
};
typedef SNode *PSNode, Stack;

void initStack(Stack &s);

void push(Stack &stack, PTNode e);

void pop(Stack &stack, PTNode &node);

bool emptyStack(const Stack &stack);


/**
 * 二叉树的中序遍历,非递归实现
 * @param T
 * @param visit
 * @return
 */
Status InOrderTraverse(BinTree T, Status(*visit)(ElementType e)) {
    Stack s;
    //初始化一个栈
    initStack(s);
    PTNode p = T;
    while (p || !emptyStack(s)) {
        while (p) {
            push(s, p);    //循环结束时,栈顶一定是左子树的叶子结点
            p = p->left;
        }
        pop(s, p);
        if (visit(p->data) == ERROR) {
            return ERROR;
        }
        p = p->right;
    }
    return OK;
}

中序遍历完成了,先序遍历就很简单了,先序就是第一次遇到我们就访问.第一次遇到是什么时候呢?显然是入栈前,第二次遇到是出栈后.因此代码就出来了.

先序遍历

/**
 * 二叉树的先序遍历,非递归实现
 * @param T
 * @param visit
 * @return
 */
Status InOrderTraverse(BinTree T, Status(*visit)(ElementType e)) {
    Stack s;
    //初始化一个栈
    initStack(s);
    PTNode p = T;
    while (p || !emptyStack(s)) {
        while (p) {
            if (visit(p->data) == ERROR) {
                return ERROR;
            }
            push(s, p);    //循环结束时,栈顶一定是左子树的叶子结点
            p = p->left;
        }
        pop(s, p);
        p = p->right;
    }
    return OK;
}

最后编辑于：2018.05.01 12:05:07