PTA 数据结构二叉树的非递归遍历 pintia

迈不过友情╰ 2022-03-30 04:56 131阅读 0赞

### PTA 二叉树的非递归遍历 ###

这一题写的我快要吐了，讲述一下心酸历程。

> 6-3 二叉树的非递归遍历 （10 分）  
> 本题要求用非递归的方法实现对给定二叉树的 3 种遍历。
> 
> 函数接口定义：  
> void InorderTraversal( BinTree BT );  
> void PreorderTraversal( BinTree BT );  
> void PostorderTraversal( BinTree BT );  
> 其中BinTree结构定义如下：  
>   
>   
> typedef struct TNode *Position;  
> typedef Position BinTree;  
> struct TNode\{  
> ElementType Data;  
> BinTree Left;  
> BinTree Right;  
> int flag;  
> \};  
> 要求 3 个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。  
>   
>   
> 此外，裁判程序中给出了堆栈的全套操作，可以直接调用。  
>   
>   
> 裁判测试程序样例：  
> \#include <stdio.h>  
> \#include <stdlib.h>  
> typedef enum \{ false, true \} bool;  
>   
>   
> typedef char ElementType;  
> typedef struct TNode Position;  
> typedef Position BinTree;  
> struct TNode\{  
> ElementType Data;  
> BinTree Left;  
> BinTree Right;  
> int flag;  
> \};  
>   
>   
> /\------堆栈的定义-------*/  
> typedef Position SElementType;  
> typedef struct SNode *PtrToSNode;  
> struct SNode \{  
> SElementType Data;  
> PtrToSNode Next;  
> \};  
> typedef PtrToSNode Stack;  
>   
>   
> /* 裁判实现，细节不表 */  
> Stack CreateStack();  
> bool IsEmpty( Stack S );  
> bool Push( Stack S, SElementType X );  
> SElementType Pop( Stack S ); /* 删除并仅返回S的栈顶元素 */  
> SElementType Peek( Stack S );/* 仅返回S的栈顶元素 */  
> /*\----堆栈的定义结束-----*/  
>   
>   
> BinTree CreateBinTree(); /* 裁判实现，细节不表 */  
> void InorderTraversal( BinTree BT );  
> void PreorderTraversal( BinTree BT );  
> void PostorderTraversal( BinTree BT );  
>   
>   
> int main()  
> \{  
> BinTree BT = CreateBinTree();  
> printf(“Inorder:”); InorderTraversal(BT); printf("\\n");  
> printf(“Preorder:”); PreorderTraversal(BT); printf("\\n");  
> printf(“Postorder:”); PostorderTraversal(BT); printf("\\n");  
> return 0;  
> \}  
> /* 你的代码将被嵌在这里 \*/  
> 输入样例：  
> 如图  
> ![在这里插入图片描述][1cc65709-9782-4788-a882-0ff567d5ad8f.jpg]  
>   
>   
> 输出样例：  
> Inorder: D B E F A G H C I  
> Preorder: A B D F E C G H I  
> Postorder: D E F B H G I C A

这道题目简直是丧尽天良，惨绝人寰。  
  
  
一开始题目看错了，以为就是简单的递归（没看见“非”字）遍历，马上就莽。一波只过了2个案例，重新审题发现要非递归。  
既然是非递归，那无非就是栈，一看题目果然有栈。好的，再扫了一眼题目，节点有个int参数flag，突然想起老师上课说的按照相反顺序入栈，然后记一个bool，1代表visit过了，0代表没有，然后马上又打。打到一半发现这个flag走了一次之后肯定就不是0了，有可能初始化就不是0（恕我没学好，我也不知道，感觉没有初始化函数他就会随机，事实上我并不知道会怎么样）。那我还有两个要遍历的就走不了。  
  
  
遂重写。换了个思路，显然先序遍历是容易的，一个while就能搞定，剩下两个分别是 左右中 左中右，想到先一直找左，没有了再根据情况判断下一个是什么。  
上代码，细节不说，看码。

void InorderTraversal( BinTree BT ){
        
        Stack s=CreateStack();
        if(BT!=NULL)
            Push(s,BT);
        BinTree now;
        while(!IsEmpty(s)){
        
            while(Peek(s)->Left!=NULL)
                Push(s,Peek(s)->Left);
            while(!IsEmpty(s)){
        
                now=Peek(s);
                printf(" %c",now->Data);
                Pop(s);
                if(now->Right!=NULL){
        
                    Push(s,now->Right);
                    break;
                }
            }
        }
    }
    
    void PreorderTraversal( BinTree BT ){
        
    
        Stack s=CreateStack();
       //Push(s,BT);
        BinTree now=BT;
        if(now!=NULL)
            Push(s,now);
        while(!IsEmpty(s)){
        
            now=Pop(s);
            printf(" %c",now->Data);
            if(now->Right!=NULL)
                Push(s,now->Right);
            if(now->Left!=NULL)
                Push(s,now->Left);
        }
    }
    
    void PostorderTraversal( BinTree BT ){
        
        Stack s=CreateStack();
        if(BT!=NULL)
            Push(s,BT);
        BinTree now=BT,last=NULL;
        while(!IsEmpty(s)){
        
            while(Peek(s)->Left!=NULL)
                Push(s,Peek(s)->Left);
            while(!IsEmpty(s)){
        
                now=Peek(s);
                if(now->Right==last||now->Right==NULL){
        
                    printf(" %c",now->Data);
                    Pop(s);
                    last=now;
                }
                else{
        
                    Push(s,now->Right);
                    break;
                }
            }
        }
    }

还有最后一个坑点

##  最后一个测试点总是段错误，我仔细的看来看去都没看见野指针之类的，还以为自己遇到了指针漂移的玄学问题。。。。 ##

## 最后发现 ##

# 有个根节点是NULL的测试点。。。 #

## 一开始直接就push了根节点，没想太多。找了半天，加上之前的递归写法，最后一个测试点过了，但是时间迷之巨大。。以为是大数据，一直没往根节点为空那个方向去想，结果在自暴自弃的路上疯狂乱改。。。？？？？什么居然过了。。。。。。？？？？ ##

# 更新一下 #

### 我发现我的同学递归也过了。。。。然后仔细看了一下自己的。。。函数名直接复制了第一个函数的函数名，导致有两个函数是错的。。。下次一定好好检查 ###

void InorderTraversal( BinTree BT ){
        
    	if(BT==NULL)
    		return ;
    	InorderTraversal(BT->Left);
    	printf(" %c",BT->Data);
    	InorderTraversal(BT->Right);
    }
    void PreorderTraversal( BinTree BT ){
        
    	if(BT==NULL)
    		return ;
    	printf(" %c",BT->Data);
    	PreorderTraversal(BT->Left);
    	PreorderTraversal(BT->Right);
    }
    void PostorderTraversal( BinTree BT ){
        
    	
    	if(BT==NULL)
    		return ;
    	PostorderTraversal(BT->Left);
    	PostorderTraversal(BT->Right);
    	printf(" %c",BT->Data);
    }

这是常规递归写法 。。题目居然不卡递归层数。。。

[1cc65709-9782-4788-a882-0ff567d5ad8f.jpg]: /images/20220330/eefbde97491a4cb78b4995b8d64b9704.png