顺序栈遍历二叉树

在做这道题之前，需要用到顺序栈，那么还是老规矩，把之前的做的顺序栈做成一个动态库，这样方便使用，不会顺序栈和制作动态库的同学可以去看我另外的文章。

先去到存放库的文件夹里面看看，有没有动态库

上面很明显有这样的动态库libseqstack.so，因此可以直接来使用

先来上一个二叉树：

分析一下遍历过程：

 下面我们打印像下面这棵树：

直接上代码：

这里面引入了顺序栈1.0的动态库，可以去看我的文章

non_recursion.c

#include <stdio.h>
#include <stdlib.h>
#include "seqstack1.0.h"


//定义每一个结点的数据结
typedef struct _binary_node binary_node;

struct _binary_node {
	char ch;
	binary_node *lchild;
	binary_node *rchild;
	int flag;
}; 

//栈递归
void stack_print(binary_node *node)
{
	//先来初始化一个栈
	t_seq_stack* t_stack = create_stack();
	if(t_stack == NULL) {
		return;
	}
	//直接把根结点先入栈
	push_stack(t_stack,node);
	//然后进行循环
	while(!is_empty(t_stack)) {
		//先把根结点拿出来，左右结点好入栈
		//这里采用先序遍历，DLR，那么R肯定先入栈，最后打出来
		binary_node* node = (binary_node*)top_stack(t_stack);
		//然后出栈
		pop_stack(t_stack);
		//判断一下flag是否等于1，等于打印
		if(node->flag == 1) {
			printf("%c\n",node->ch);
			continue;
		}
		node->flag = 1;//弹出来之后的标识，肯定要从0变成1
		//否则，把右，左,和上面的根接连入栈
		if(node->rchild != NULL) {
			push_stack(t_stack,node->rchild);
		}
		if(node->lchild != NULL) {
			push_stack(t_stack,node->lchild);
		}
		//插入弹出的结点
		push_stack(t_stack,node);
	}
	destroy_stack(t_stack);
}

int main()
{
	//这里把结点创建好
	binary_node node_a = {'A',NULL,NULL,0};
	binary_node node_b = {'B',NULL,NULL,0};
	binary_node node_c = {'C',NULL,NULL,0};
	binary_node node_d = {'D',NULL,NULL,0};
	binary_node node_e = {'E',NULL,NULL,0};
	binary_node node_f = {'F',NULL,NULL,0};

	//把结点相互连接上
	node_a.lchild = &node_b;
	node_a.rchild = &node_c;

	node_b.lchild = &node_d;
	node_b.rchild = &node_e;
	
	node_c.rchild = &node_f;

	stack_print(&node_a);
	//穿件	
	return 0;
}

 结果：