#include
#include
typedef int DataType;
typedef struct Node{
    DataType data;
    struct Node *leftChild;//左孩子指针 
    struct Node *rightChild;//右孩子指针 
}BiTreeNode;
void visit(DataType item)//访问函数 
{
    printf("%c  ",item);
}
void Initiate(BiTreeNode **root)//初始化 
{
    *root=(BiTreeNode *)malloc(sizeof(BiTreeNode));
    (*root)->leftChild=NULL;
    (*root)->rightChild=NULL;
}
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x)//左插入结点
{
    BiTreeNode *s,*t;
    if(curr==NULL)return NULL;
    t=curr->leftChild;//保存原curr的左孩子指针
    s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
    s->data=x ;
    s->leftChild=t;
    s->rightChild=NULL;
    curr->leftChild=s;
    return curr->leftChild;
}
BiTreeNode *InsertrightNode(BiTreeNode *curr,DataType x)//右插入结点 
{
    BiTreeNode *s,*t;
    if(curr==NULL)return NULL;
    t=curr->rightChild;//保存原curr的左孩子指针
    s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
    s->data=x ;
    s->rightChild=t;
    s->leftChild=NULL;
    curr->rightChild=s;
    return curr->rightChild;
}
void Destroy(BiTreeNode **root)//撤销 
{
    if((*root)!=NULL&&(*root)->leftChild!=NULL)
    Destroy(&(*root)->leftChild);
    if((*root)!=NULL&&(*root)->rightChild!=NULL)
    Destroy(&(*root)->rightChild);
    free(*root);
}
BiTreeNode *DeleteLeftTree(BiTreeNode *curr)//左删除子树 
{
    if(curr==NULL||curr->leftChild==NULL)return NULL;
    Destroy(&curr->leftChild);
    curr->leftChild=NULL;
    return curr;
}

BiTreeNode *DeleterightTree(BiTreeNode *curr)//右删除子树 
{
    if(curr==NULL||curr->rightChild==NULL)return NULL;
    Destroy(&curr->rightChild);
    curr->rightChild=NULL;
    return curr;
}
void PreOrder(BiTreeNode *root,void visit(DataType item))//前序遍历 
{
    if(root!=NULL)
    {
        visit(root->data);
        PreOrder(root->leftChild,visit);
        PreOrder(root->rightChild,visit);
    }
}
void InOrder(BiTreeNode *root,void visit(DataType item))//中序遍历
{
    if(root!=NULL)
    {
        InOrder(root->leftChild,visit);
        visit(root->data);        
        InOrder(root->rightChild,visit);
    }
}
void PostOrder(BiTreeNode *root,void visit(DataType item))//后序遍历
{
    if(root!=NULL)
    {
        PostOrder(root->leftChild,visit);        
        PostOrder(root->rightChild,visit);
        visit(root->data);                
    }
}
void PrintBiTree(BiTreeNode *root,int n)//打印二叉树 
{
    int i;
    if(root==NULL)
    return;
    PrintBiTree(root->rightChild,n+1);
    for(i=0;i     printf("  ");
    if(n>0)
    {
        printf("---");
        printf("%c\n",root->data);
    }
    PrintBiTree(root->leftChild,n+1);
}
BiTreeNode *Search(BiTreeNode *root,DataType x)
{
    BiTreeNode *find=NULL;
    if(root!=NULL)
    {
        if(root->data==x)
        find=root;
        else
        {
            find=Search(root->leftChild,x);
            if(find==NULL)
            find=Search(root->rightChild,x);
        }
    }
    return find;
}
int main()
{
    BiTreeNode *root,*p,*find;
    char x='E';
    Initiate(&root);
    p=InsertLeftNode(root,'A');
    p=InsertLeftNode(p,'B');
    p=InsertLeftNode(p,'D');
    p=InsertrightNode(p,'G');
    p=InsertrightNode(root->leftChild,'C');
    InsertLeftNode(p,'E');
    InsertrightNode(p,'F');
    PrintBiTree(root,0);
    printf("前序遍历:");
    PreOrder(root->leftChild,visit);
    printf("\n中序遍历:");
    InOrder(root->leftChild,visit);
    printf("\n后序遍历:");
    PostOrder(root->leftChild,visit);
}