/* 创建二叉树 ----> 装入数据，---->遍历---> 显示 --->销毁*/
/*有错误 再想对策*/
/* 创建二叉树 ----> 装入数据，
---->遍历---> 显示 --->销毁*/
#include <stdio.h>
#include <malloc.h>
#define DEBUG
#ifdef DEBUG
/******************************************************************/
/*链栈， 判断 栈是否空，压栈，出栈*/
/*----------------------------------------------*/
typedef int DataType;
typedef DataType elementTypt;
typedef struct Node
{
DataType data;
struct Node *LChild;
struct Node *RChild;
struct Node *Root;
}Node;
/*树的数据结构*/
/*===========================================----*/
typedef struct stackNode
{
elementTypt data;
struct stackNode * next;
}stackNode;
/* 栈的数据结构*/
void TInitstack( stackNode * Top )/*初始化栈*/
{
Top = ( stackNode *) malloc ( sizeof ( stackNode ) );
Top -> next = NULL;
return;
}
int isEmpty( stackNode * Top )
/* 是否空*/
{
return ( Top -> next == NULL );
}
int TPush( stackNode * Top , elementTypt data )
/*将元素 data 压入栈Top中,出错返回 1*/
{
stackNode * Temp;
Temp = ( stackNode * ) malloc( sizeof( stackNode ) );
if( !Temp )
{
return 1;
}/*空间分配失败返回*/
Temp -> data = data ;
Temp -> next = Top -> next ;
Top -> next = Temp;
return 0;
}
int TPop( stackNode * Top , elementTypt * ptr )
{
stackNode * Temp;
Temp = Top -> next ;
if( !Temp )
{
return 1;
}/*栈空返回 1 */
Top -> next = Temp -> next ;
*ptr = Temp -> data ;
free( Temp );
return 0 ;
}
/* creat tree */
void Initiate( Node *root )
/*初始化为空树*/
{
root = ( Node * ) malloc( sizeof( Node ) );
root -> LChild = root -> RChild = NULL;
}
void Creat( Node *root , DataType data )
{
if( root )
{
root -> data = data ;
return ;
}
root = ( Node * ) malloc( sizeof( Node ) );
root -> data = data ;
root -> LChild = root -> RChild = NULL;
}
void Destory( Node *root )
/* 销毁二叉数 root */
{
stackNode *s ;
Node *pre = root;
TInitstack( s );
while( pre != NULL || !isEmpty(s) )
{
if( pre )
{
TPush( s , pre -> data );
pre = pre -> LChild;
}
else
{
TPop( s ,&( pre -> data) );
if( !pre -> RChild )
/* free 条件
!(pDel -> right && ! p->left) */
{
Node *pDel = pre ;
free ( pDel );
TPop( s , &( pre -> data ) );
}
else
{
pre = pre -> RChild;
}
}
}
}/*对称编码 防止 漏标识符 */
void Insert( Node *root , DataType data )
/* 降顺序二叉数装入数据，左子树<右子树*/
{
Node *p = root;
if( root != NULL )
{
Creat( root , data ) ;
return ;
}
while( p )
{
if( data < (p -> data) )
{
p = p -> LChild;
}
else
{
p = p -> RChild;
}
/*相等的 将装数据到右孩子 */
}
Creat( p , data );
}
void CreatTree( Node *root , DataType data ,
Node * LChild , Node *RChild )
/* 生成树结构：把节点连起来*/
{
root -> LChild = LChild ;
root -> RChild = RChild;
root -> data = data;
return;
}
void Visit( Node * p )
{
printf("%d :", p -> data );
return;
}
void InOrder( Node * root )
/*中序遍历二叉树*/
{
/* add code */
stackNode * S ;
Node *p = root ;
TInitstack( S );
while(( p != NULL )|| (! isEmpty( S )) )
{
if( p != NULL )/*根指针进栈*/
{
TPush( S , (p -> data) );
p = p -> LChild;
}
else
{
TPop( S , &( p -> data ) );
Visit ( p );
p = p -> RChild;
}
}
return;
}
#endif DEBUG
void main()
{
Node *Root ;
int a=0;
int ch=0;
int i= 0;
printf("InPut Root Data : ");
scanf("%d",&a);
getchar();
Creat( Root , a );
while( ch != '$' )
{
++i ;
printf("Input %d Data : ", i);
Insert( Root , ch );
ch = getchar() ;
}
getchar();
InOrder( Root );
Destory( Root );
return;
}