非递归遍历

柔光的暖阳◎ 2022-04-10 13:39 334阅读 0赞

## 原理 ##

1. 先将A初始化为 FALSE（标志位），放入栈中

![20190111112343800.png][]

2. 从栈中弹出 一个元素，如果是FASLE，将标志改为TRUE，再将 左右节点B F 初始化为FALSE，

![20190111111807152.png][]

3. 按顺序Push到栈中，顺序不同意味着（先、中、后序遍历）

![20190111111942940.png][]

4. 再弹出一个元素，判断标准位，是 TRUE直接输出

![20190111112124763.png][]

5. 再弹出元素（如果是NULL，直接continue，继续下次循环），判断标志位，重复2操作

![20190111111600550.png][]

6. 直到弹出元素，结束

--------------------

## 代码 ##

*  基于栈的顺序存储

stack.h

#ifndef __STACK_H
    #define __STACK_H
    
    #define MAX_SIZE 1024
    
    
    
    typedef struct STACK
    { 
    	void* Stack_Sqe[MAX_SIZE];
    	int size;	
    }Stack;
    
    
    
    Stack* Init_Stack(void);
    
    void Push_Stack(Stack* stack, void* data);
    void Pop_Stack(Stack* stack);
    
    void* Top_Stack(Stack* stack);
    
    void Clear_Stack(Stack* stack);
    void Free_Stack(Stack* stack);
    
    int Size_Stack(Stack* stack);
    
    
    #endif

stack.c

#include "../include/stack.h"
    #include <stdlib.h>
    
    
    Stack* Init_Stack(void)
    { 
    	Stack* stack = (Stack*)malloc(sizeof(Stack));
    	stack->size =0;		
    	
    	for(int i=0; i<MAX_SIZE; i++)
    	{ 
    		stack->Stack_Sqe[i]=NULL;
    	}
    
    return stack;	
    }
    
    
    void Push_Stack(Stack* stack, void* data)
    { 
    	if(stack == NULL) return;
    	if(data == NULL) return;
    
    	stack->Stack_Sqe[stack->size++] = data;
    
    }
    
    
    
    void Pop_Stack(Stack* stack)
    { 
    
    	if(stack == NULL) return;
    	stack->Stack_Sqe[stack->size-1]=NULL;
    	stack->size--;
    
    }
    
    
    void* Top_Stack(Stack* stack)
    { 
    	if(stack == NULL)return NULL;
    	return stack->Stack_Sqe[stack->size-1];
    }
    
    
    void Clear_Stack(Stack* stack)
    { 
    
    	if(stack == NULL)return;
    
    	for(int i=0; i<stack->size; i++)
    	{ 
    		stack->Stack_Sqe[i]=NULL;
    	}
    
    }
    
    
    
    void Free_Stack(Stack* stack)
    { 
    	if(stack == NULL)
    		return;
    
    	free(stack);
    }
    
    
    
    int Size_Stack(Stack* stack)
    { 
    	return stack->size;
    }

main.c

#include "../include/stack.h"
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    
    #define FALSE 0
    #define TRUE 1
    
    typedef struct BINARYNODE
    { 
    	char ch;
    	struct BINARYNODE* left;
    	struct BINARYNODE* right;
    
    }BinaryNode;
    
    typedef struct NODEPACKAGE //将节点添加一个标志位，
    { 
    	BinaryNode* node;
    	int flag;	
    }NodePackage;
    
    
    int main(void)
    { 
        BinaryNode b1,b2,b3,b4,b5,b6,b7,b8;
    
    	b1.ch = 'A'; b1.left = &b2; b1.right = &b3;
    	b2.ch = 'B'; b2.left = NULL;b2.right = &b4;
    	b3.ch = 'F'; b3.left = NULL;b3.right = &b5;
    	b4.ch = 'C'; b4.left = &b6; b4.right = &b7;
    	b5.ch = 'G'; b5.left = &b8; b5.right = NULL;
    	b6.ch = 'D'; b6.left = NULL; b6.right = NULL;
    	b7.ch = 'E'; b7.left = NULL; b7.right = NULL;
    	b8.ch = 'H'; b8.left = NULL; b8.right = NULL;
    
    	Stack* stack = Init_Stack();
    
    	NodePackage p1={ &b1,FALSE};   //将A初始化成 FALSE ，Push到栈中
    	Push_Stack(stack,&p1);
    
    	while(stack->size) 
    	{ 
    		NodePackage* tmp = (NodePackage*)Top_Stack(stack); 
    		Pop_Stack(stack);
    
    		if(tmp->node == NULL) continue;  
    		else
    		{ 
    			if(tmp->flag) //是 TRUE 直接输出
    			{ 
    				printf("%c",tmp->node->ch);
    			}
    			else //是FALSE, 将标志改 TRUE,再将左子树，右子树封装好，按顺序Push到栈中
    			{ 
    			    tmp->flag = TRUE; 
    			    
    				NodePackage* RightPack = (NodePackage*) malloc(sizeof(NodePackage));
    				RightPack->flag = FALSE;
    				RightPack->node = tmp->node->right;
    
    				NodePackage* LeftPack = (NodePackage*) malloc(sizeof(NodePackage));
    				LeftPack->flag = FALSE;
    				LeftPack->node = tmp->node->left;
    				                   
    				Push_Stack(stack, tmp);  　 //当前根　　最先放，后取出，后续遍历，
    				Push_Stack(stack,RightPack);  //右子树
    				Push_Stack(stack,LeftPack);  //左子树
    			
    			}
    		}
    	}
    
    	return 0;
    }

结果：　DECBHGFA

[20190111112343800.png]: /images/20220328/b789525e42bd4091b25a43670ccf018f.png
[20190111111807152.png]: /images/20220328/9eb422388a00407b840f3a53d61edfdb.png
[20190111111942940.png]: /images/20220328/beacb8e452fd4cb39274314591a5d1aa.png
[20190111112124763.png]: /images/20220328/a367fb33d52944579c12b1d07d371d76.png
[20190111111600550.png]: /images/20220328/ab02fefcaf2a4324871ea884d5aa1011.png