(六)数据结构之二叉树的简单实现_typedef struct treenode *bintree; struct treenode{

1、基本数据结构

/* 二叉树的基本数据结构的定义 */
typedef char ElementType;
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode{
	ElementType Data;
	BinTree Left;
	BinTree Right;
};

采用链式存储方式来存储二叉树，每个二叉树结点包括一个数据域和两个指针域，其中数据域用来存放二叉树对应结点的数据，指针域分别用来指向其左右孩子结点。

2、二叉树的递归遍历

2.1 先序遍历

/* 先序递归遍历 */
void PreOrderTraversal( BinTree BT )
{
	if( BT ) 
	{
		printf("%c ", BT->Data);
		PreOrderTraversal( BT->Left );
		PreOrderTraversal( BT->Right );
	}
}

2.2 中序遍历

/* 中序递归遍历 */
void InOrderTraversal( BinTree BT )
{
	if( BT ) 
	{
		InOrderTraversal( BT->Left );
		printf("%c ", BT->Data);
		InOrderTraversal( BT->Right );
	}
}

2.3 后序遍历

/* 后序递归遍历 */
void PostOrderTraversal( BinTree BT )
{
	if( BT )
	{
		PostOrderTraversal( BT->Left );
		PostOrderTraversal( BT->Right);
		printf("%c ", BT->Data);
	}
}

3、二叉树的非递归遍历

考虑到算法的复杂度问题常常为了提高效率而采用非递归的二叉树遍历方法，为了实现非递归遍历需要借助一种基本的数据结构堆栈，堆栈的具体实现可以参考这篇文章http://blog.csdn.net/tech_pro/article/details/78011998。

3.1 先序遍历

/* 先序非递归遍历 */
void PreOrderTraversalWithStack( BinTree BT )
{ 
	BinTree T = BT;
	Stack *S = CreateStack(); 	/*创建并初始化堆栈S*/
	while( T || !IsEmpty(S) )
	{
		while(T)
		{ 
			/*一直向左并将沿途结点压入堆栈*/
			printf("%c ", T->Data); 	/*（访问）打印结点*/
			Push(S,T);
			T = T->Left;
		}
		if(!IsEmpty(S))
		{
			T = Pop(S); 				/*结点弹出堆栈*/
			T = T->Right; 				/*转向右子树*/
		}
	}
	DestroyStack(S);
}

3.2 中序遍历

/* 中序非递归遍历 */
void InOrderTraversalWithStack( BinTree BT )
{ 
	BinTree T = BT;
	Stack *S = CreateStack(); 	/*创建并初始化堆栈S*/
	while( T || !IsEmpty(S) )
	{
		while(T)
		{ 
			/*一直向左并将沿途结点压入堆栈*/
			Push(S,T);
			T = T->Left;
		}
		if(!IsEmpty(S))
		{
			T = Pop(S); 				/*结点弹出堆栈*/
			printf("%c ", T->Data); 	/*&#x