void createBT(struct bt ** root)
{
? ? char c;
? ? c=getchar();
? ? if(c == ' ')*root=NULL;
? ? else
? ? {
? ? ? ? *root=(struct bt *)malloc(sizeof(struct bt));
? ? ? ? (*root)->data=c;
? ? ? ? createBT(&((*root)->left));
? ? ? ? createBT(&((*root)->right));
? ? }
}
?
void preOrder(struct bt * root)
{
? ? if(root == NULL)return;
? ? else
? ? {
? ? ? ? putchar(root->data);
? ? ? ? preOrder(root->left);
? ? ? ? preOrder(root->right);
? ? }
}
?
void inOrder(struct bt * root)
{
? ? if(root == NULL)return;
? ? else
? ? {
? ? ? ? inOrder(root->left);
? ? ? ? putchar(root->data);
? ? ? ? inOrder(root->right);
? ? }
}
?
void printLeaves(struct bt* root)
{
? ? if(root == NULL)return;
? ? else
? ? {
? ? ? ? if(root->left == NULL&&root->right == NULL)putchar(root->data);
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? printLeaves(root->left);
? ? ? ? ? ? printLeaves(root->right);
? ? ? ? }
? ? }
}
?
int btDepth(struct bt* root)
{
? ? int rd,ld;
? ? if(root==NULL)return 0;
? ? else
? ? {
? ? ? ? ld=1+btDepth(root->left);
? ? ? ? rd=1+btDepth(root->right);
? ? ? ? return ld > rd ? ld : rd;
? ? }
}
?
void btOutput(struct bt* root,int depth)
{
? ? int k;
? ? if(root==NULL)return;
? ? else
? ? {
? ? ? ? btOutput(root->right,depth+1);
? ? ? ? for(k=0;k
? ? ? ? ? ? printf(" ");
? ? ? ? putchar(root->data);printf("\n");
? ? ? ? btOutput(root->left,depth+1);
? ? }
}
?
void postOrder(struct st* root)
{
? ? struct st* stack[100];
? ? int top=-1;
? ? struct bt* p=root;
? ? struct bt* q=NULL;
? ? while(p!=NULL||top!=-1)
? ? {
? ? ? ? for(;p!=NULL;p=p->left)stack[++top]=p;
? ? ? ? if(top!=-1)
? ? ? ? {
? ? ? ? ? ? p=stack[top];
? ? ? ? ? ? if(p->right==NULL||p->right==q)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? putchar(p->data);
? ? ? ? ? ? ? ? q=p;
? ? ? ? ? ? ? ? p=stack[top];
? ? ? ? ? ? ? ? top--;
? ? ? ? ? ? ? ? p=NULL;
? ? ? ? ? ? }
? ? ? ? ? ? else p=p->right;
? ? ? ? }
? ? }
}
?
void printPath(struct bt* root,char c)
{
? ? struct st* stack[100];
? ? int top=-1;
? ? int i;
? ? struct bt* p=root;
? ? struct bt* q=NULL;
? ? while(p!=NULL||top!=-1)
? ? {
? ? ? ? for(;p!=NULL;p=p->left)stack[++top]=p;
? ? ? ? if(top!=-1)
? ? ? ? {
? ? ? ? ? ? p=stack[top];
? ? ? ? ? ? if(p->right==NULL||p->right==q)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(p->data==c)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? for(i=0;i<=top;i++)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? p=stack[i];
? ? ? ? ? ? ? ? ? ? ? ? putchar(p->data);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? printf("\n");
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? q=p;
? ? ? ? ? ? ? ? p=stack[top];
? ? ? ? ? ? ? ? top--;
? ? ? ? ? ? ? ? p=NULL;
? ? ? ? ? ? }
? ? ? ? ? ? else p=p->right;
? ? ? ? }
? ? }
}
?
void layerPrint(struct bt* root)
{
? ? struct bt* queue[100];
? ? struct bt* p;
? ? int amount=0,head,tail,j,k;
? ? queue[0]=root;
? ? head=0;
? ? tail=1;
? ? amount++;
? ? while(1)
? ? {
? ? ? ? j=0;
? ? ? ? for(k=0;k
? ? ? ? {
? ? ? ? ? ? p=queue[head++];
? ? ? ? ? ? if(p->left!=NULL)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? queue[tail++]=p->left;
? ? ? ? ? ? ? ? j++;
? ? ? ? ? ? }
? ? ? ? ? ? if(p->right!=NULL)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? queue[tail++]=p->right;
? ? ? ? ? ? ? ? j++;
? ? ? ? ? ? }
? ? ? ? ? ? putchar(p->data);
? ? ? ? }
? ? ? ? amount=j;
? ? ? ? if(amount==0)break;
? ? }
}
?
void indOutput(struct bt* root,int k)
{
? ? int i;
? ? if(root!=NULL)
? ? {
? ? ? ? for(i=1;i<=k;i++)
? ? ? ? ? ? putcha