cpp3.cpp

1） 以二叉链表或三叉链表作为二叉树的存储结构； 2） 以某一种遍历的次序录入二叉树的元素

#include<malloc.h>
#include<stdlib.h>
#include<stdio.h>
#define OK 1
#define ERROR 0
typedef int status;
typedef struct BiTNode{
	 char data;
	 struct BiTNode	*lchild, *rchild,*next;
}BiTNode, *BiTree;


status PreCreateBitree(BiTree &T)
 {
	 char ch;
	 ch=getchar();
	 if(ch=='*')T=NULL;
	 else
	 {
		 T=(BiTree)malloc(sizeof(BiTNode));
		 T->data=ch;
		 PreCreateBitree(T->lchild);
    	 PreCreateBitree(T->rchild);
	 }
	 return(OK);
 }

status Visit(char c)
{
	
	printf("%c",c);
	return(OK);

}

status PreOrderTraverse(BiTree T, status ( *Visit ) (char c) )//先序遍历
{
     if ( T!= NULL )
	 {

         if ( Visit(T->data) )
             if ( PreOrderTraverse( T->lchild, Visit ) )
              if ( PreOrderTraverse( T->rchild, Visit ) )
                 return(OK);
             return(ERROR);
	 } 
     else return(OK);
}

status PostOrderTraverse_Thr(BiTree T,BiTree &pre)  //后序线索化，增加一个链域表示后继，所以无须判断左右标志
{
	if(T!=NULL)
	{
		if(PostOrderTraverse_Thr(T->lchild,pre))
			if(PostOrderTraverse_Thr(T->rchild,pre))
			{
				pre->next=T;
				pre=T;
				return(OK);
			}
			return(ERROR);
	}
	else return(OK);
}


		            
	 		
status PostOrderThreading(BiTree &Thrt,BiTree T)
{
    BiTree p;     
	if(!(Thrt=(BiTree)malloc(sizeof(BiTNode))))exit(0);
    if(!T)Thrt->next=Thrt;      //找到最左下的结点
	else
	{
		Thrt->lchild=NULL;    
		p=Thrt;                
    	PostOrderTraverse_Thr(T,p);
		p->next=NULL;
	}
	return(OK);
}

void PostThreading(BiTree Thrt,status (*Visit)(char c))
{
	BiTree p;
	p=Thrt->next;
    while(p!=NULL)
	{	
		
        Visit(p->data);
	    p=p->next;
	
	}
}




void main()
 {
	 BiTree T,Thrt;
	 PreCreateBitree(T);
     PreOrderTraverse(T,Visit);
	 printf("\n");
	 PostOrderThreading(Thrt,T);
     PostThreading(Thrt,Visit);
	 printf("\n");


 }