数据结构例程——二叉树遍历的非递归算法

简介: 本文是数据结构基础系列(6):树和二叉树中第11课时二叉树遍历非递归算法的例程。【二叉树遍历的非递归算法】 实现二叉树的先序、中序、后序遍历的非递归算法,并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。 请利用二叉树算法库。[参考解答](btreee.h见算法库)#include <stdio.h

本文是数据结构基础系列(6):树和二叉树中第11课时二叉树遍历非递归算法的例程。

【二叉树遍历的非递归算法】
实现二叉树的先序、中序、后序遍历的非递归算法,并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。
请利用二叉树算法库

[参考解答](btreee.h见算法库

#include <stdio.h>
#include "btree.h"

void PreOrder1(BTNode *b)
{
    BTNode *St[MaxSize],*p;
    int top=-1;
    if (b!=NULL)
    {
        top++;                      //根节点入栈
        St[top]=b;
        while (top>-1)              //栈不为空时循环
        {
            p=St[top];              //退栈并访问该节点
            top--;
            printf("%c ",p->data);
            if (p->rchild!=NULL)    //右孩子入栈
            {
                top++;
                St[top]=p->rchild;
            }
            if (p->lchild!=NULL)    //左孩子入栈
            {
                top++;
                St[top]=p->lchild;
            }
        }
        printf("\n");
    }
}

void InOrder1(BTNode *b)
{
    BTNode *St[MaxSize],*p;
    int top=-1;
    if (b!=NULL)
    {
        p=b;
        while (top>-1 || p!=NULL)
        {
            while (p!=NULL)
            {
                top++;
                St[top]=p;
                p=p->lchild;
            }
            if (top>-1)
            {
                p=St[top];
                top--;
                printf("%c ",p->data);
                p=p->rchild;
            }
        }
        printf("\n");
    }
}

void PostOrder1(BTNode *b)
{
    BTNode *St[MaxSize];
    BTNode *p;
    int flag,top=-1;                        //栈指针置初值
    if (b!=NULL)
    {
        do
        {
            while (b!=NULL)                 //将t的所有左节点入栈
            {
                top++;
                St[top]=b;
                b=b->lchild;
            }
            p=NULL;                         //p指向当前节点的前一个已访问的节点
            flag=1;
            while (top!=-1 && flag)
            {
                b=St[top];                  //取出当前的栈顶元素
                if (b->rchild==p)           //右子树不存在或已被访问,访问之
                {
                    printf("%c ",b->data);  //访问*b节点
                    top--;
                    p=b;                    //p指向则被访问的节点
                }
                else
                {
                    b=b->rchild;            //t指向右子树
                    flag=0;
                }
            }
        }
        while (top!=-1);
        printf("\n");
    }
}

int main()
{
    BTNode *b;
    CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("二叉树b: ");
    DispBTNode(b);
    printf("\n");
    printf("先序遍历序列:\n");
    PreOrder1(b);
    printf("中序遍历序列:\n");
    InOrder1(b);
    printf("后序遍历序列:\n");
    PostOrder1(b);
    DestroyBTNode(b);
    return 0;
}

注:在main函数中,创建的用于测试的二叉树如下——
这里写图片描述

目录
相关文章
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
77 1
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
90 0
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
198 10
 算法系列之数据结构-二叉树
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
160 3
 算法系列之数据结构-Huffman树
|
7月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
214 22
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
204 30
|
11天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
14天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
100 1
|
12天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
|
11天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
102 14

热门文章

最新文章