二叉树建立与递归

树的非递归建立，关键在于对每个节点设置一个flag。查看栈顶元素，如果flag==0,表示还没有添加过左子树，将当前节点添加入其左子树，否则添加入右子树同时栈顶元素出栈。

#include<stdio.h>
#include<stdlib.h>
typedef struct btree{
    struct btree *left;
    struct btree *right;
    char value;
    int flag;
}btree;
    btree *q[101];
    int top;
void push(btree *t){
    q[++top]=t;
}
btree *pop(){
    return q[top--];
}
btree *ttop(){
    return q[top];
}
void inOrder(btree *t){
    if(t!=NULL){
        inOrder(t->left);
        printf("%c ",t->value);
        inOrder(t->right);
    }
}
int main(){
    char a[101];
    top=-1;
    while(scanf("%s",a)!=EOF){
        btree *pt;
        btree *temp;
        btree *prev;
        if(a[0]=='#') continue;
        else{
            temp=(btree *)malloc(sizeof(btree));
            temp->left=temp->right=NULL;
            temp->flag=0;
            temp->value=a[0];
            pt=temp;
            push(pt);
        }
        for(int i=1;a[i]!='\0';i++){
            if(a[i]=='#')
                temp=NULL;
            else{
                temp=(btree *)malloc(sizeof(btree));
                temp->left=temp->right=NULL;
                temp->flag=0;
                temp->value=a[i];
            }
            prev=ttop();
            if(prev->flag==0){
                prev->left=temp;
                prev->flag=1;
            }else{
                prev->right=temp;
                pop();
            }
            if(temp!=NULL)
                push(temp);
        }
        inOrder(pt);
        printf("\n");
    }
}

递归方式

这里使用全局变量now记录当前添加的节点。

#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef struct node{
    char data;
    struct node *lchild,*rchild;
}node;
char s[100];
int now;
void InOrder(node *T)
{
    if(T)
    {
        InOrder(T->lchild);
        printf("%c ",T->data);
        InOrder(T->rchild);
    }
    return;
}
node *Insert(node *T)
{
    char c=s[now++];
    if(c=='#')T=NULL;
    else
    {
        T=(node *)malloc(sizeof(node));
        T->data=c;
        T->lchild=T->rchild=NULL;
        T->lchild=Insert(T->lchild);
        T->rchild=Insert(T->rchild);
    }
    return T;
}
int main()
{
    while(scanf("%s",s)!=EOF)
    {
        int len=strlen(s);
        node *T=NULL;
        now=0;
        T=Insert(T);
        InOrder(T);
        printf("\n");
    }
    return 0;
}