POJ 1577--Falling Leaves

Figure 1

#include <stdio.h>#include <string.h>#include <malloc.h>typedef struct BiTree{ /*自定义二叉树*/ char ch; struct BiTree *lchild; struct BiTree *rchild;}BiTree;BiTree *createBiTree(char ch){ /*创建一个叶子节点*/ BiTree *leaf = (BiTree *)malloc(sizeof(BiTree)); leaf->ch = ch; leaf->lchild = NULL; leaf->rchild = NULL; return leaf;}BiTree *insertBiTree(BiTree *root, char ch){ BiTree *leaf = root; if(root == NULL) { root = createBiTree(ch); return root; } while(leaf) { if((leaf->ch) > ch) { if(leaf->lchild == NULL) //如果ch比该节点小且该节点的左子树为空 { //就将ch放在该节点的左子树上 leaf->lchild = createBiTree(ch); break; } else //否则继续遍历直到找到合适的位置位置 { leaf = leaf->lchild; } } else if((leaf->ch) < ch) { if(leaf->rchild == NULL) //如果ch比该节点大且该节点的右子树为空 { //就将ch放在该节点的右子树上 leaf->rchild = createBiTree(ch); break; } else //否则继续遍历直到找到合适的位置位置 { leaf = leaf->rchild; } } } return root;}void preOrderTraver(BiTree *root){ /*前序遍历二叉树，并且输出结果*/ BiTree *p, *stack[100]; int top = 0; p = root; while(!(p == NULL && top == 0)) { while(p != NULL) { stack[top] = p; //将当前指针压入栈中 top++; printf("%c", p->ch); p = p->lchild; } if(top <= 0) return; //栈空时结束 else { top--; p = stack[top]; p = p->rchild; } }}int main(){ char str[50], p[10000]; int length; int i; BiTree *root = NULL; while(1) { scanf("%s", str); if(strcmp(str, "*") == 0 || strcmp(str, "$") == 0) { length = strlen(p); for(i = length-1; i >= 0; i--) { root = insertBiTree(root, p[i]); } preOrderTraver(root); printf("\n"); if(strcmp(str, "$") == 0) break; root = NULL; memset(p, '\0', sizeof(p)); } else { strcat(p, str); } } return 0;}?

?