//二叉树的建立、存储与遍历
#include <iostream.h>
struct BintrNode
{
    char value;
    BintrNode* lf;
    BintrNode* rt;
};

 void init(BintrNode* &p)
{
    char ch;
    cin>>ch;
    if(ch!='!')
    {
    p=new BintrNode;
    p->value=ch;
    init(p->lf);
    init(p->rt);
    }
    else 
    {
        p=NULL;
    }
}
 void pre(BintrNode* p)
 {
     if(p)
     {
            cout<<p->value;
            pre(p->lf);
            pre(p->rt);
     }
 }
 void ino(BintrNode* p)
 {
    if(p)
    {
     ino(p->lf);
     cout<<p->value;
     ino(p->rt);
    }
 }
  void pro(BintrNode* p)
 {
     if(p)
     {
     pro(p->lf);
     pro(p->rt);
     cout<<p->value;
     }
 }
 void main()
 {
BintrNode* bt;
init(bt);
pre(bt);
cout<<endl;
ino(bt);
cout<<endl;
pro(bt);
cout<<endl;

 }


#include<stdio.h>
#include<stdlib.h>
struct node
{
	int data;
	struct node *lh,*rh;
	int ltag,rtag;
}*pr,*t,*s[30];

struct node* creat()
{
	struct node *t,*q;
	int i,x,j;
	printf("i,x=");
	scanf("%d%d",&i,&x);
	while((i!=0)&&(x!=0))
	{
		q=(struct node *)malloc(sizeof(struct node));
		q->data=x;
		q->lh=NULL;
		q->rh=NULL;
		s[i ]=q;
		if(i==1)
			t=q;
		else
		{
			j=i/2;
			if((i%2)==0)
				s[j]->lh=q;
			else
				s[j]->rh=q;
		}
		printf("i,x=");
		scanf("%d%d",&i,&x);
	}
	return(t);
}

/*void inthread(struct node *p) //递归算法
{
	if(p!=NULL)
	{
		inthread(p->lh);
		printf("%6d\t",p->data);
		if(p->lh!=NULL)
			p->ltag=0;
		else
		{
			p->ltag=1;
			p->lh=pr;
		} //建立P节点的左线索，指向前趋节点PR
		if(pr!=NULL)
		{
			if(pr->rh!=NULL)
				pr->rtag=0;
			else
			{
				pr->rtag=1;
				pr->rh=p;
			}//前趋节点PR建立左线索，指向节点P
		}
		pr=p;//pr跟上p,以便p向后移动
		inthread(p->rh);
	}
}*/

void inthread(struct node *t)//非递归算法
{
	int top,bools;
	struct node *p;
	pr=NULL;p=t;top=0;bools=1;
	do{
		while(p!=NULL)
		{
			top++;
			s[top]=p;
			p=p->lh;
		}
		if(top==0)bools=0;
		else
		{
			p=s[top];
			top--;
			printf("%6d",p->data);
			if(p->lh!=NULL)
				p->ltag=0;
			else
			{
				p->ltag=1;
				p->lh=pr;
			} //建立P节点的左线索，指向前趋节点PR
			if(pr!=NULL)
			{
				if(pr->rh!=NULL)
					pr->rtag=0;
				else
				{
					pr->rtag=1;
					pr->rh=p;
				}//前趋节点PR建立左线索，指向节点P
			}
			pr=p;//pr跟上p,以便p向后移动
			p=p->rh;
		}//END else
	}while(bools);
	pr->rh=NULL;
}

main()
{
	pr=NULL;
	t=creat();
	inthread(t);
	pr->rh=NULL;
}


#include<stdio.h>
#include<malloc.h>
#include<iostream>

//定义节点 
typedef struct BiNode{
        char data;
        struct BiNode *lch;
        struct BiNode *rch;
}BiNode,*BiTree;

//先序拓展序列建立二叉树 
void Create(BiTree &T)
{
        T =(BiNode*) malloc (sizeof(BiNode));
        
        printf("Enter the data \n");
        scanf(" %c",&T->data);
        if(T->data=='#') T = NULL;
        if(T){
                printf("");
                Create(T->lch);
                Create(T->rch);
        }
}

//先序遍历 (递归)
void Preorder (BiTree T)
{                    
   if (T) {
      printf(" %c",T->data);             // 访问根结点
      
      Preorder(T->lch); // 遍历左子树
      Preorder(T->rch);// 遍历右子树
   }
}

//中序遍历 （递归）
void Inorder (BiTree T)
{
     if(T) {
       Inorder(T->lch);
       
       printf(" %c",T->data);
       
       Inorder(T->rch);    
       }
} 

//后序遍历 （递归）
void Postorder (BiTree T)
{
     if(T) {
       Postorder(T->lch);
       Postorder(T->rch);
       
       printf(" %c",T->data); 
     }
} 

int main()
{
    //建树 
    printf("The fuction Create() is called.\n");
    BiTree T;
    Create(T);
    
    //三种遍历递归算法 
    printf("\n");    
    printf("The fuction Preorder() is called.\n");
    Preorder(T);
    
    printf("\n");
    printf("The fuction Inorder() is called.\n");
    Inorder(T);
    
    printf("\n");
    printf("The fuction Postorder() is called.\n");
    Postorder(T);
    
    
    printf("\n");
    system("pause");
    
}