二叉树中序遍历非递归算法实现

#include <iostream> //二叉树中序遍历非递归算法实现 
using namespace std;
#define MAXSIZE 100 

/*不让用递归，那就用栈！！*/

//树的结点结构体 
typedef struct BTnode  
{
	int data;  //本身数据 
	BTnode * Lchild;  //左孩子 
	BTnode * Rchild;  //右孩子  【不是线索树 不用考虑前后驱】 
	
}BTnode,* BTree;

/*BTree类型就是BTnode *  [为了看着更符合实际 故起不同名字]
BTree是结构体指针，即指向这个树的结点的指针(可取结构体内部元素)
BTnode是结构体，即树的结点 
*/


//树的非递归中序遍历 [左根右]
void mid_order(BTree T) //传入的是根结点[代表一个树];下面就代表的是结点了 
{
	int top=-1; //栈顶指针 初始化为-1
	BTnode * S[MAXSIZE]; //数组模拟栈[类型为指针[可以存放树的结点]]
	
	//当T==NULL且top==-1 就停止循环 
	while(T!=NULL||top!=-1){
		
		while(T!=NULL){  //若此结点存在 
			S[++top]=T;  //存放到栈里 
			
			T=T->Lchild; //找这个结点的左孩子！！ 【一直找左孩子】 
		}
		
		if(top!=-1){ //如果栈不为空[栈里有结点] 
			T=S[top--]; //栈顶赋给T
			cout<<T->data<<" "; //输出此结点的值【输出一次就行】 
			
			T=T->Rchild; //再找右孩子！！！！ 
		}
		
	}
}


int main()
{
	//创建树的结点 
	BTnode * l1=new BTnode;
	BTnode * l2=new BTnode;
	BTnode * l3=new BTnode;
	BTnode * l4=new BTnode;
	BTnode * l5=new BTnode;
	BTnode * l6=new BTnode;
	
	//给结点赋值 
	l1->data=5;
	l2->data=3;
	l3->data=9;
	l4->data=4;
	l5->data=8;
	l6->data=10;
	
	//创建结点关系
	l1->Lchild=l2;
	l1->Rchild=l3;
	l2->Lchild=NULL;
	l2->Rchild=l4;
	l3->Lchild=l5;
	l3->Rchild=l6;
	l4->Lchild=NULL;
	l4->Rchild=NULL;
	l5->Lchild=NULL;
	l5->Rchild=NULL;
	l6->Lchild=NULL;
	l6->Rchild=NULL;
	
	cout<<"中序遍历的结果为："<<endl;
	mid_order(l1); 
	
	
	
	return 0;
}

运行结果：