/*有错误 再想对策*/ /* 创建二叉树 ----> 装入数据， ---->遍历---> 显示 --->销毁*/ #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; } 
|
本类阅读TOP10