【数据结构】【王道】【树与二叉树】二叉树非递归遍历的实现（可直接运行）

发布时间：2024-01-01 16:56:35

总目录：https://blog.csdn.net/treesorshining/article/details/125726400

文章目录

1.说明
2.算法实现
3.完整代码
4.运行结果

1.说明

相比于递归实现的遍历算法，非递归算法增加了一个辅助栈，根据栈后进先出的特点，来实现非递归遍历。

2.算法实现

2.1 先序遍历（非递归）

如果结点不为空就先访问结点，然后将结点压入栈中；然后进行遍历，直至存在左孩子为NULL的结点为止；此时，由于是先访问，此左节点之上的双亲节点，双亲结点的双亲节点（如果有）以及访问完毕了，即是运用了传统先序遍历的根左右思想。之后弹出栈顶结点，若其右孩子不为NULL则进入其右子树进行上述操作，直至某个结点有孩子为NULL为止，若其右孩子为NULL则继续弹出栈顶结点，然后继续上述操作，直至退出循环为止。

// 先序遍历（非递归）
void PreOrder(BiTree T) {
    LinkStack S;
    // 初始化栈
    InitStack(S);
    // 遍历指针
    BiTree p = T;
    // 树和链表有一者不为空则循环继续进行
    while(p || !IsEmpty(S)) {
        // 如果结点不为空就先访问结点，然后将结点压入栈中
        // 然后进行遍历，直至存在左孩子为NULL的结点为止
        // 此时，由于是先访问，此左节点之上的双亲节点，双亲结点的双亲节点（如果有）以及访问完毕了
        // 即是运用了传统先序遍历的根左右思想
        // 之后弹出栈顶结点
        // 若其右孩子不为NULL则进入其右子树进行上述操作，直至某个结点有孩子为NULL为止
        // 若其右孩子为NULL则继续弹出栈顶结点，然后继续上述操作，直至退出循环为止
        if(p) {
            visit(p);
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, p);
            p = p->rchild;
        }
    }
}

2.2 中序遍历（非递归）

如果结点不为空，则先将结点压入栈中，然后先遍历此结点下所有左孩子，直至某一个左孩子为NULL，然后弹出栈顶结点并访问，若其右孩子不为NULL则进入其右子树进行上述操作，直至某个结点有孩子为NULL为止，若其右孩子为NULL则继续弹出栈顶结点进行访问，然后继续上述操作，直至退出循环为止。思路即是中序遍历传统思路，先访问左节点，再访问根节点，最后访问右节点。

// 中序遍历（非递归）
void InOrder(BiTree T) {
    LinkStack S;
    // 初始化栈
    InitStack(S);
    // 遍历指针
    BiTree p = T;
    // 树和链表有一者不为空则循环继续进行
    while(p || !IsEmpty(S)) {
        // 如果结点不为空，则先将结点压入栈中
        // 然后先遍历此结点下所有左孩子，直至某一个左孩子为NULL
        // 然后弹出栈顶结点并访问
        // 若其右孩子不为NULL则进入其右子树进行上述操作，直至某个结点有孩子为NULL为止
        // 若其右孩子为NULL则继续弹出栈顶结点进行访问，然后继续上述操作，直至退出循环为止
        // 思路即是中序遍历传统思路，先访问左节点，再访问根节点，最后访问右节点
        if(p) {
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, p);
            visit(p);
            p = p->rchild;
        }
    }
}

2.3 后序遍历（非递归）

// 后序遍历（非递归）
void PostOrder(BiTree T) {
    LinkStack S;
    // 初始化栈
    InitStack(S);
    // 遍历指针
    BiTree p = T;
    // 辅助指针，用于记录最近访问过的结点
    BiTree r = NULL;
    // 树和链表有一者不为空则循环继续进行
    while(p || !IsEmpty(S)) {
        // 如果结点不为空就先访问结点，然后将结点压入栈中
        // 然后进行遍历，直至存在左孩子为NULL的结点为止
        // 然后读取栈顶结点，如果其右孩子不为NULL且未被访问过，则以上述方法访问右子树
        // 否则栈顶结点出栈并进行访问
        // 此思路主要就是由于后序需要先访问完左右结点后才访问根结点
        // 所以不能类似于前序、中序一样，遍历到左子树最后一个左结点就可以开始出栈并访问
        // 访问完左子树后，不能直接出栈，而是要获取栈顶结点，对其右子树进行上述处理
        // 直至栈顶元素右子树为空或者右子树已经访问完毕，则可进行出栈访问
        if(p) {
            Push(S, p);
            p = p->lchild;
        } else {
            // 注意：此处是读取栈顶结点，而并非出栈
            GetTop(S, p);
            // 若右子树存在且未被访问过
            // 则以上述步骤开始访问其右子树
            // 否则，将栈顶结点出栈并访问
            if(p->rchild && p->rchild != r) {
                p = p->rchild;
            } else {
                Pop(S, p);
                visit(p);
                // 记录最近访问过的结点
                r = p;
                // 结点访问完成后，重置p指针
                // 由于每次出栈访问完一个结点就相当于遍历完以该结点为根的子树，所以需要将p重置
                p = NULL;
            }
        }
    }
}

2.4 后序遍历2（非递归）

可以以另一种较为巧妙的方式实现，可知后序遍历结果为左右根，先序遍历结果为根左右，可将先序遍历循环中左右全部互换，结果应为根右左，然后将结果全部取反，可得左右根，即后序遍历结果。但需要额外设立一个栈，增加了空间开销。

// 后序遍历（非递归）
// 可以以另一种较为巧妙的方式实现
// 可知后序遍历结果为左右根，先序遍历结果为根左右
// 可将先序遍历循环中左右全部互换，结果应为根右左
// 然后将结果全部取反，可得左右根，即后序遍历结果
// 但需要额外设立一个栈，增加了空间开销
void PostOrder1(BiTree T) {
    LinkStack S;
    // 额外设立一个辅助栈，用于存入将要输出结果的结点
    // 由于栈的特性，根右左输入，应有左右根的输出
    LinkStack temp;
    // 初始化栈
    InitStack(S);
    InitStack(temp);
    // 遍历指针
    BiTree p = T;
    // 树和链表有一者不为空则循环继续进行
    while(p || !IsEmpty(S)) {
        if(p) {
            Push(temp, p);
            Push(S, p);
            p = p->rchild;
        } else {
            Pop(S, p);
            p = p->lchild;
        }
    }
    // 输出后序结果
    while(!IsEmpty(temp)) {
        Pop(temp, p);
        visit(p);
    }
}

3.完整代码

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

typedef struct BiTNode {
    // 数据域
    char data;
    // 左、右孩子指针
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 不带头结点
typedef struct LinkNode {
    BiTNode* data;   // 数据域
    struct LinkNode *next; // 指针域
} LSNode, *LinkStack;   // 栈类型定义

// 初始化
void InitTree(BiTree &T) {
    // 初始化可将根节点置空，空树
    T = NULL;
    // 插入根节点
    // 分配空间
    T = (BiTree)malloc(sizeof(BiTree));
    // 赋值
    T->data = 'A';
    // 初始无左右子树
    T->lchild = NULL;
    T->rchild = NULL;
}

// 左插入结点
bool InsertLeftTreeNode(BiTNode* &T, char x) {
    // 分配空间
    BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
    // 分配空间失败的情况
    if(p == NULL) {
        return false;
    }
    // 数据域赋值
    p->data = x;
    // 初始插入，无左右孩子，置空
    p->lchild = NULL;
    p->rchild = NULL;
    // 作为指定插入结点的左孩子
    T->lchild = p;
    return true;
}

// 右插入结点
bool InsertRightTreeNode(BiTNode* &T, char x) {
    // 分配空间
    BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
    // 分配空间失败的情况
    if(p == NULL) {
        return false;
    }
    // 数据域赋值
    p->data = x;
    // 初始插入，无左右孩子，置空
    p->lchild = NULL;
    p->rchild = NULL;
    // 作为指定插入结点的左孩子
    T->rchild = p;
    return true;
}

// 访问结点
void visit(BiTree T) {
    printf("%c   ", T->data);
}

// 树的深度
int treeDepth(BiTree T) {
    // 根结点为空，则深度为0
    if(T == NULL) {
        return 0;
    } else {
        // 递归遍历左子树，获得左子树深度
        int l = treeDepth(T->lchild);
        // 递归遍历右子树，获得右子树深度
        int r = treeDepth(T->rchild);
        // 树的深度=Max{左子树深度，右子树深度} + 1
        // 加1相当于访问根节点，包括根结点深度+1
        return l > r ? l + 1 : r + 1;
    }
}

// 初始化
void InitStack(LinkStack &S) {
    // 此为不带头结点的栈，与单链表相似，初始将栈顶指针指向NULL即可
    S = NULL;
}

// 判空
bool IsEmpty(LinkStack S) {
    // 栈为空的条件即栈顶指针指向NULL
    if(S == NULL) {
        return true;
    }
    return false;
}

// 入栈操作
// 由于栈只能从一端操作，所以每次都应该是从栈顶入栈
bool Push(LinkStack &S, BiTNode* e) {
    // 申请分配空间
    LSNode *s = (LSNode*)malloc(sizeof(LSNode));
    // 内存分配失败的情况
    if(s == NULL) {
        return false;
    }
    s->data = e;
    // 由于每次都是从栈顶指针处插入，所以无需特殊处理
    // 令s指向S之前指向的地址
    s->next = S;
    // 使头指针指向s
    S = s;
    return true;
}

// 出栈操作
// 类似于单链表的删除操作，不过只能在栈顶进行出栈
bool Pop(LinkStack &S, BiTNode* &e) {
    // 如果是空栈，则不可进行出栈操作
    if(S == NULL) {
        return false;
    }
    // 出栈结点即为栈顶指针指向的结点
    // 将出栈结点值赋给e
    e = S->data;
    // 临时结点，用于之后释放空间
    LSNode* p = S;
    // 使头指针指向下一个结点
    S = S->next;
    // 释放空间
    free(p);
    return true;
}

// 获取栈顶元素
bool GetTop(LinkStack S, BiTNode* &e) {
    // 栈为空的情况
    if(S == NULL) {
        return false;
    }
    e = S->data;
    return true;
}

// 先序遍历（非递归）
void PreOrder(BiTree T) {
    LinkStack S;
    // 初始化栈
    InitStack(S);
    // 遍历指针
    BiTree p = T;
    // 树和链表有一者不为空则循环继续进行
    while(p || !IsEmpty(S)) {
        // 如果结点不为空就先访问结点，然后将结点压入栈中
        // 然后进行遍历，直至存在左孩子为NULL的结点为止
        // 此时，由于是先访问，此左节点之上的双亲节点，双亲结点的双亲节点（如果有）以及访问完毕了
        // 即是运用了传统先序遍历的根左右思想
        // 之后弹出栈顶结点
        // 若其右孩子不为NULL则进入其右子树进行上述操作，直至某个结点有孩子为NULL为止
        // 若其右孩子为NULL则继续弹出栈顶结点，然后继续上述操作，直至退出循环为止
        if(p) {
            visit(p);
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, p);
            p = p->rchild;
        }
    }
}

// 中序遍历（非递归）
void InOrder(BiTree T) {
    LinkStack S;
    // 初始化栈
    InitStack(S);
    // 遍历指针
    BiTree p = T;
    // 树和链表有一者不为空则循环继续进行
    while(p || !IsEmpty(S)) {
        // 如果结点不为空，则先将结点压入栈中
        // 然后先遍历此结点下所有左孩子，直至某一个左孩子为NULL
        // 然后弹出栈顶结点并访问
        // 若其右孩子不为NULL则进入其右子树进行上述操作，直至某个结点有孩子为NULL为止
        // 若其右孩子为NULL则继续弹出栈顶结点进行访问，然后继续上述操作，直至退出循环为止
        // 思路即是中序遍历传统思路，先访问左节点，再访问根节点，最后访问右节点
        if(p) {
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, p);
            visit(p);
            p = p->rchild;
        }
    }
}

// 后序遍历（非递归）
void PostOrder(BiTree T) {
    LinkStack S;
    // 初始化栈
    InitStack(S);
    // 遍历指针
    BiTree p = T;
    // 辅助指针，用于记录最近访问过的结点
    BiTree r = NULL;
    // 树和链表有一者不为空则循环继续进行
    while(p || !IsEmpty(S)) {
        // 如果结点不为空就先访问结点，然后将结点压入栈中
        // 然后进行遍历，直至存在左孩子为NULL的结点为止
        // 然后读取栈顶结点，如果其右孩子不为NULL且未被访问过，则以上述方法访问右子树
        // 否则栈顶结点出栈并进行访问
        // 此思路主要就是由于后序需要先访问完左右结点后才访问根结点
        // 所以不能类似于前序、中序一样，遍历到左子树最后一个左结点就可以开始出栈并访问
        // 访问完左子树后，不能直接出栈，而是要获取栈顶结点，对其右子树进行上述处理
        // 直至栈顶元素右子树为空或者右子树已经访问完毕，则可进行出栈访问
        if(p) {
            Push(S, p);
            p = p->lchild;
        } else {
            // 注意：此处是读取栈顶结点，而并非出栈
            GetTop(S, p);
            // 若右子树存在且未被访问过
            // 则以上述步骤开始访问其右子树
            // 否则，将栈顶结点出栈并访问
            if(p->rchild && p->rchild != r) {
                p = p->rchild;
            } else {
                Pop(S, p);
                visit(p);
                // 记录最近访问过的结点
                r = p;
                // 结点访问完成后，重置p指针
                // 由于每次出栈访问完一个结点就相当于遍历完以该结点为根的子树，所以需要将p重置
                p = NULL;
            }
        }
    }
}

// 后序遍历（非递归）
// 可以以另一种较为巧妙的方式实现
// 可知后序遍历结果为左右根，先序遍历结果为根左右
// 可将先序遍历循环中左右全部互换，结果应为根右左
// 然后将结果全部取反，可得左右根，即后序遍历结果
// 但需要额外设立一个栈，增加了空间开销
void PostOrder1(BiTree T) {
    LinkStack S;
    // 额外设立一个辅助栈，用于存入将要输出结果的结点
    // 由于栈的特性，根右左输入，应有左右根的输出
    LinkStack temp;
    // 初始化栈
    InitStack(S);
    InitStack(temp);
    // 遍历指针
    BiTree p = T;
    // 树和链表有一者不为空则循环继续进行
    while(p || !IsEmpty(S)) {
        if(p) {
            Push(temp, p);
            Push(S, p);
            p = p->rchild;
        } else {
            Pop(S, p);
            p = p->lchild;
        }
    }
    // 输出后序结果
    while(!IsEmpty(temp)) {
        Pop(temp, p);
        visit(p);
    }
}

int main() {
    BiTree T;
    InitTree(T);
    InsertLeftTreeNode(T, 'B');
    InsertRightTreeNode(T, 'C');
    InsertLeftTreeNode(T->lchild, 'D');
    InsertRightTreeNode(T->lchild, 'E');
    InsertLeftTreeNode(T->rchild, 'F');
    InsertRightTreeNode(T->rchild, 'G');
    printf("PreOrder\n");
    PreOrder(T);
    printf("\nInOrder\n");
    InOrder(T);
    printf("\nPostOrder\n");
    PostOrder(T);
    printf("\ntreeDepth:%d\n", treeDepth(T));
}

4.运行结果

在这里插入图片描述

文章来源:https://blog.csdn.net/treesorshining/article/details/125943308
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！