学步园

这两天一直在敲堆排，快排。。。这俩各敲了10遍左右了。。。初步计时，堆排3.5分钟，算导写法。

在算导上看了BST，感觉差不都了，开始写，开始写的非递归，死活不对，后来知道了，自己的非递归写法，节点和它的子节点建立不起来联系 = =最后改为递归写法。没有用malloc，不喜欢它 = =。。

这题我做完后再看题才看懂 = =。。。给你拆树的过程。。。去掉叶子节点的树，再去掉叶子节点。。。最后去掉根。所以做法就是倒着建立一棵二叉查找树。最后一个是根节点，然后写BST的插入函数，倒着插入即可。最后前序遍历。

#include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <string.h><br /> using namespace std;<br /> typedef struct BST{<br /> int data;<br /> BST *r,*l;<br /> }BST;<br /> BST *head,node[100];<br /> int cou;<br /> char str[15][15];<br /> void init() // As the name of the function. Init = =...<br /> {<br /> cou = 0;<br /> memset( node,'/0',sizeof(node) );<br /> head = NULL;<br /> }<br /> void Insert( BST *&head, int x ) //Insert nodes.<br /> {<br /> if( head == NULL )<br /> {<br /> node[cou].data = x;<br /> head = &node[cou++];<br /> return ;<br /> }<br /> if( x > head->data )<br /> Insert( head->r , x ); //Recursion is magic. > < .<br /> else<br /> Insert( head->l , x );<br /> }<br /> void Pretravers( BST *head ) // Preorder traversal.<br /> {<br /> if( head != NULL )<br /> {<br /> printf("%c",head->data+'A');<br /> Pretravers( head->l );<br /> Pretravers( head->r );<br /> }<br /> }<br /> int main(void)<br /> {<br /> while( scanf("%s",&str[0])!=EOF && strcmp(str[0],"$")!=0 && strcmp(str[0],"*")!=0 )<br /> {<br /> int i = 1;<br /> init();<br /> while( scanf("%s",&str[i]) && strcmp(str[i],"*")!= 0 && strcmp(str[i],"$")!=0 )<br /> {<br /> i++;<br /> }<br /> for(int j=i-1; j>=0; j--)<br /> {<br /> int len = strlen(str[j]);<br /> for(int k=0; k<len; k++)<br /> Insert( head , str[j][k] - 'A' );<br /> }<br /> Pretravers(head);<br /> if( strcmp(str[i],"$") == 0 )<br /> break;<br /> printf("/n");<br /> }<br /> return 0;<br /> }<br />