首页 > 其他分享 >二叉树的非递归遍历

二叉树的非递归遍历

时间:2023-08-14 10:35:18浏览次数:32  
标签:遍历 return 递归 top Tree 二叉树 TreeNode data Stack

//非递归操作

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

#define MaxSize 200 

typedef struct TreeNode{
    int data;
    struct TreeNode *lchild,*rchild;
}TreeNode,*Tree;

typedef struct{
    Tree data[MaxSize];
    int top;
}Stack;

void InitStack(Stack &S)
{
    S.top=-1;
}

bool isEmpty(Stack S)
{
    if(S.top==-1)
    {
        return true;
    }
    return false;
}

int Push(Stack &S,Tree x)
{
    if(S.top==MaxSize-1)
    {
        return -1;
    }
    S.data[++S.top]=x;
    return 0;
}

int Pop(Stack &S,Tree &x)
{
    if(S.top==-1)
    {
        return -1;
    }
    x=S.data[S.top--];
    return 0;
}

void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;
    }
    else
    {
        T=(Tree)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild);
    }
}

//先序遍历非递归操作
void PreOrderTree(Tree T)
{
    Stack S;
    InitStack(S);
    TreeNode *p=T;
    while(p || !isEmpty(S))
    {
        if(p)
        {
            printf("%d ",p->data);
            Push(S,p);
            p=p->lchild;
        }
        else
        {
            Pop(S,p);
            p=p->rchild;
        }
    }    
} 

//中序遍历非递归操作
void MidOrderTree(Tree T)
{
    Stack S;
    InitStack(S);
    TreeNode *p=T;
    while(p || !isEmpty(S))
    {
        if(p)
        {
            Push(S,p);
            p=p->lchild;
        }
        else
        {
            Pop(S,p);
            printf("%d ",p->data);
            p=p->rchild;
        }
    }
}  
/*
//后序遍历非递归操作
void LatOrderTree(Tree T)
{
    Stack S;
    InitStack(S);
    TreeNode *p=T;
    while(p || !isEmpty)
    {
        if(p)
        {
            Push(S,p);
            p=p->lchild;    
        }    
        else
        {
            
            Pop(S,p);
            p=p->rchild;
        }
    }    
} 
*/

int main()
{
    Tree T;
    CreateTree(T);
    PreOrderTree(T);
    
    return 0;
    
}

 

标签:遍历,return,递归,top,Tree,二叉树,TreeNode,data,Stack
From: https://www.cnblogs.com/simpleset/p/17627961.html

相关文章

  • 二叉树的递归遍历
    #include<stdio.h>#include<stdlib.h>typedefstructTNode{intdata;structTNode*lchild,*rchild;}TreeNode,*Tree;/*在这段代码中,递归函数`CreateTree`在执行`return`语句后,会立即返回到调用它的上一层递归调用。但是,整个递归过程并没有结束,仍然会......
  • 利用C语言递归函数解决求5的方法是什么
    利用C语言递归函数解决求5的方法是什么在C语言编程中,递归是一种非常有用的技术,它能够简化问题的解决过程并提高代码的复用性。本文将以求解数字5为例,介绍如何利用C语言递归函数来实现这一任务。9利用C语言递归函数解决求5的方法是什么首先,让我们明确问题的定义。求解数字5的方......
  • P9534 [YsOI2023] 广度优先遍历
    好题。首先考虑到对于任意的边的输入顺序,分层图是不会变的,即所有点到根的最短距离不变。那么分为两种边,分别为不同层的边相连,相同层的边相连。显然第二种边是无用的,我们将其放到最后输出即可。由于下层的决策会影响上层的决策而且不同层之间的边的顺序不会影响答案,所以我们按......
  • import.meta.globEager('./src/components/**/*.vue'); 遍历文件
    main.jsconstimportAll=(modules)=>{Object.keys(modules).forEach((key)=>{constcomponent=key.replace('/src/','@/').replace('.vue','');constcomponentName=key.split('/').slice......
  • 二叉树的层序遍历
    intfindBottomLeftValue(TreeNode*root){queue<TreeNode*>qu;if(root!=nullptr)qu.push(root);intsize=0;intresult=0;while(!qu.empty()){TreeNode*temp;size=qu.size();......
  • 数据结构与算法 --- 递归(二)
    引言上文数据结构与算法---递归(一)讲述了什么是递归算法,如何编写递归算法及如何写好递归算法,本文着重讲述一下如何避免递归过深导致的堆栈溢出问题。探究产生堆栈溢出的原因函数调用采用函数调用栈来保存当前“快照”(局部变量,返回地址等)。函数调用栈是内存中开辟的一块存储空......
  • 数据结构与算法 --- 递归(一)
    什么是递归?递归(Recursion)是一种解决问题的方法,它将问题分解为更小的子问题,并逐层解决这些子问题。递归算法的核心思想是:一个函数可以直接或间接地调用自身。通过这种自我调用,我们可以用简洁的代码来解决复杂问题。满足递归的条件一般来说,满足下面三个条件就可以使用递归:待......
  • 归并排序(递归)(NB)
    博客地址:https://www.cnblogs.com/zylyehuo/递归思路#_*_coding:utf-8_*_importrandomdefmerge(li,low,mid,high):i=lowj=mid+1ltmp=[]whilei<=midandj<=high:#只要左右两边都有数ifli[i]<li[j]:......
  • [代码随想录]Day16-二叉树part05
    题目:513.找树左下角的值思路:层序遍历是最好的选择了,先放右节点,再放左节点最后一个元素就是最左侧的节点。说白了层序遍历就是广度优先搜索BFS。代码:funcfindBottomLeftValue(root*TreeNode)int{node:=rootq:=[]*TreeNode{root}forlen(q)>0{......
  • p5两链表相交问题和二叉树
    (本文大多从杀戒之声处来,就想着自己方便看)两链表相交问题所谓相交,是指两链表有某一内存地址相同,则为相交,判断有环无环,哈希表(set),第一次相同(单向链表)快慢指针,快走2,慢走1,快慢指针第一次相遇后,将快指针返回头节点,慢指针不动,快改为走1,看快慢节点是否能相遇,有环则一定会在入环节......