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

简介: 本文是数据结构基础系列(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函数中,创建的用于测试的二叉树如下——
这里写图片描述

目录
相关文章
|
9天前
|
机器学习/深度学习 算法 Java
[算法与数据结构] 谈谈线性查找法~
该文章详细介绍了线性查找法的基本概念与实现方法,通过Java代码示例解释了如何在一个数组中查找特定元素,并分析了该算法的时间复杂度。
|
28天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
2月前
|
算法
【初阶数据结构】复杂度算法题篇
该方法基于如下的事实:当我们将数组的元素向右移动 k 次后,尾部 kmodn 个元素会移动至数组头部,其余元素向后移动 kmodn 个位置。
|
2月前
|
机器学习/深度学习 人工智能 算法
【人工智能】线性回归模型:数据结构、算法详解与人工智能应用,附代码实现
线性回归是一种预测性建模技术,它研究的是因变量(目标)和自变量(特征)之间的关系。这种关系可以表示为一个线性方程,其中因变量是自变量的线性组合。
53 2
|
2月前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称,即左右子树是否对称.
|
2月前
|
算法 索引
【初阶数据结构篇】单链表算法题进阶
深拷贝应该正好由 n 个全新节点组成,其中每个新节点的值都设为其对应的原节点的值。
|
2月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。
|
2月前
|
存储 缓存 算法
深入解析B树:数据结构、存储结构与算法优势
深入解析B树:数据结构、存储结构与算法优势
|
7天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
下一篇
无影云桌面