二叉排序树 先序遍历 中序遍历 后序遍历(非递归).doc

#include <>
#include <>
typedef struct Tree
{
int data;
struct Tree *left;
struct Tree *right;
}*tree;
void InsertTree(tree p,int num)
{
tree T; T = p; int i; int sign; //sign标记“现在要插入的”结点是父结点的“左还是右结点”
i=0;
tree q,tmp;
q =(tree ) malloc( sizeof(struct Tree) );
q->data = num; q->left =NULL; q->right =NULL;
while(T)
{
if(num > T->data ) { tmp = T; T= T->right;sign =1;}
//是父结点的右结点,则标记为1
else { tmp = T; T= T->left; sign =0;}
if(T ==NULL && sign == 1) { tmp ->right = q;}
if(T ==NULL && sign == 0) { tmp ->left = q;}
}

}
void PreOrder(tree p)
{
if(p)
{
printf("%d,",p->data);
PreOrder(p->left);
PreOrder(p->right);
}
}
void InOrder(tree p)
{
if(p)
{
InOrder(p->left);
printf("%d,",p->data);
InOrder(p->right);
}
}
void PostOrder(tree p)
{
if(p)
{

PostOrder(p->left);
PostOrder(p->right);
printf("%d,",p->data);
}
}
//先序遍历,中序遍历,后序遍历思想基本一致:
//(1)最左结点(且是尚未访问)依次进栈,
//(2)右结点(左结点为空或左结点已访问且是尚未访问)依次进栈
//(3)叶子结点(或已访问的(左或右)+ 空子树) 出栈
//先序遍历,中序遍历,后序遍历输出原则:
//(1) 先序遍历进栈的均输出
//(2) 中序遍历“无左子树”输出
//(3) 后序遍历
void PreOrder1(tree p)
{
tree T = p; int i; tree q[100]; i =1; q[0]= T;int k ; k = 0;
int rs[100];int ls[100]; //rs[],ls[]数组存放的是“当前结点”的左、右结点是否访问.
int j;
for(j=0; j<100 ;j++)
{
rs[j] =0;ls[j] =0;
}
while( i != 0)
{
if(i==1 && k == 0)
{
q[i] = T;
printf("%d\n",q[