POJ 1577 BST的基础题 GCC可以AC - c++编程基础

ty lines in the input.

Output

For each input data set, there is a unique binary search tree that would produce the sequence of leaves. The output is a line containing only the preorder traversal of that tree, with no blanks.

Sample Input

BDHPY
CM
GQ
K
*
AC
B
$

Sample Output

KGCBDHQMPY
BAC

完整C代码：

#include 
  
   
#include 
   
     #include 
    
      typedef char Elemtype; typedef struct BiTnode { Elemtype data; struct BiTnode *lchild, *rchild; }BiTNode, *BiTree; //BST插入函数 void Insert( BiTree *t, Elemtype e ) { if( NULL == *t ) { (*t) = (BiTree)malloc(sizeof(BiTNode)); (*t)->data = e; (*t)->lchild = (*t)->rchild = NULL; } else if( e < (*t)->data ) Insert( &(*t)->lchild, e ); else if( e > (*t)->data ) Insert( &(*t)->rchild, e ); } //BST创建函数 void CreateBST( BiTree *t, Elemtype *a ) { (*t) = NULL; int len = strlen( a ); for( int i=0; i
     
      data); PreOrderBST( t->lchild ); PreOrderBST( t->rchild ); } } int main() { char a[50], b[50]; int i = 0; int j = 0; BiTree t; char ch; while( EOF != scanf("%c",&ch) ) { if( '*' != ch && '$' != ch) a[i++] = ch; else { for( ; i>0; i-- ) { //可以优化 if( '\n' != a[i-1] ) b[j++]=a[i-1]; } b[j] = '\0'; CreateBST( &t, b ); PreOrderBST( t ); printf("\n"); if( '$' == ch ) break; i = 0; j = 0; } } return 0; }

测试数据以及测试结果

POJ 1577 BST的基础题 GCC可以AC(二)