学步园

同上文法一方法类似实现：

原理：中序遍历-左根右

循环每次把左孩子入栈，直到叶节点；沿着栈里弹出的顺序一次访问右孩子。

#include <iostream>
#include "stack"
using namespace std;

struct TNode
{
	TNode *left;
	TNode *right;
	int data;
};

TNode *Root;
void Visit(TNode *cur)
{
	cout<<cur->data<<endl;
}

stack<TNode*> ST2;
void midOrder(TNode* root)
{
	while (!ST2.empty()||root!=NULL)
	{
		if(root!=NULL)
		{
			ST2.push(root);
			root=root->left;
		}
		else
		{
			root=ST2.top();
			ST2.pop();
			Visit(root);
			root=root->right;
		}
	}
}

void InitTree(TNode *root)
{
	root->data=1;
	TNode* tree[10];

	for (int i=0;i<7;i++)
	{
		tree[i]=(TNode*) malloc(sizeof(TNode*));
		tree[i]->data=i;
		tree[i]->left=tree[i]->right=NULL;
	}

	tree[4]->right=tree[6];
	tree[1]->left=tree[3];
	tree[1]->right=tree[4];
	tree[2]->left=tree[5];
	tree[0]->left=tree[1];
	tree[0]->right=tree[2];

	Root=tree[0];
}

void main()
{
	Root=(TNode*) malloc(sizeof(TNode*));
	InitTree(Root);
	//preOrder1(Root);
	midOrder(Root);
}