二叉树的中序非递归遍历c语言版_中序非递归遍历二叉树 c语言完整代码

由于c语言没有c++的STL库，我们无法借助c++的stack库实现二叉树的非递归遍历，但是，我们完全可以自己打造一个c语言版的stack库。本篇博文就是借助我们之前在栈的链

式存储API http://blog.csdn.net/bbs375/article/details/52728358这篇博文实现的程序。当然，你也可以把它编译成动态库dll(可以参考如何封装自己的动态库应用案例http://blog.csdn.net/bbs375/article/details/52668322)放到自己的

工程项目中。

#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include<stdio.h>
#include <string.h>
#include "linklist.h"
#include "linkstack.h"
 
//第一种表示方法 ：二叉链表示法  
typedef struct BiTNode  
{  
	int data;  
	struct BiTNode *lchild,*rchild;  
} BiTNode,* BITree;  
 
//中序递归遍历  
void inOrder(BiTNode*root)  
{  
	if (root==NULL)  
	{  
		return;  
	}  
	inOrder(root->lchild);  
	printf("%d ",root->data);  
	inOrder(root->rchild);  
}  
/* 
中序遍历非递归算法： 
步骤1： 
如果结点有左子树，该结点入栈； 
如果结点没有左子树，访问该结点； 
步骤2： 
如果结点有右子树，重复步骤1； 
如果结点没有右子树（结点访问完毕），根据栈顶指示回退，访问栈顶元素，并访问右子树，重复步骤1 
如果栈为空，表示遍历结束。*/  
//辅助函数 找到中序遍历的起点   
BiTNode* goLeft(BiTNode*t,LinkStack *s)  
{  
	if (t==NULL)  
	{  
		return NULL;  
	}  
	//如果结点有左子树，该结点入栈；  
	while (t->lchild)  
	{  
	    LinkStack_Push(s,t);
		t = t->lchild;   
	}  
	return t;  
}  
//中序遍历非递归   
void inOrder2(BiTNode*root)  
{  
	BiTNode* t ;  
	LinkStack* s = LinkStack_Create();  
	if (s==NULL)
	{
		return ;
	}
	//1.找到中序遍历的起点 (没有左孩子)  
	t = goLeft(root,s);  
	while (t)  
	{  
		//访问该元素  
		printf("%d ",t->data);  
		//2.如果t有右子树 重复步骤1  
		if (t->rchild)  
		{  
			t = goLeft(t->rchild,s);//右子树中序遍历的起点  
		}  
		//2.如果没有右子树 根据栈顶指示回退  
		else if (LinkStack_Size(s)>0)      
		{  
			t = LinkStack_Pop(s);
		}  
		//3.如果没有右子树且栈为空  表示遍历结束  
		else   
		{  
			t = NULL;  
		}  
	}  
}  
int main()
{
	//创建节点
	BiTNode t1,t2,t3,t4,t5,t6;  
 
	memset(&t1,0,sizeof(BiTNode));  
	memset(&t2,0,sizeof(BiTNode));  
	memset(&t3,0,sizeof(BiTNode));  
	memset(&t4,0,sizeof(BiTNode));  
	memset(&t5,0,sizeof(BiTNode));  
	memset(&t6,0,sizeof(BiTNode));  
 
	t1.data = 1;  
	t2.data = 2;  
	t3.data = 3;  
	t4.data = 4;  
	t5.data = 5;  
	t6.data = 6;  
	//建立关系   
	t1.lchild = &t2;  
	t1.rchild = &t3;  
	t2.lchild = &t4;  
	t2.rchild = &t5;  
	t3.lchild = &t6;  
 
	printf("\n中序递归遍历\n");  
	inOrder(&t1);  
 
	printf("\n中序非递归遍历\n");  
	inOrder2(&t1);  
 
	system("pause");
	return 0;
}