ÉèÒѽ¨Á¢µÄ¶þ²æÊ÷µÄÈý²æÁ´±í´æ´¢½á¹¹ÖУ¬½áµãµÄÊý¾ÝÓòº¢×ÓÓòÒ»ÌîºÃÄÚÈÝ£¬ÏÖÒªÇó±àдËã·¨¸øË«Ç×ÓòÌîÉÏÖ¸Ïò

ÉèÒѽ¨Á¢µÄ¶þ²æÊ÷µÄÈý²æÁ´±í´æ´¢½á¹¹ÖУ¬½áµãµÄÊý¾ÝÓòº¢×ÓÓòÒ»ÌîºÃÄÚÈÝ£¬ÏÖÒªÇó±àдËã·¨¸øË«Ç×ÓòÌîÉÏÖ¸ÏòÆäË«Ç×µÄÖ¸Õë

// ´´½¨¶þ²æÊ÷,ÊäÈëÏÈÐòÀ©Õ¹ÐòÁÐ:
// ABC##DE#G##F###
// ÏÈÐò±éÀúÐòÁÐ: A B C D E G F
// ÖÐÐò±éÀúÐòÁÐ: C B E G D F A
// ºóÐò±éÀúÐòÁÐ: C G E F D B A
// ÏÈÐò±éÀú(ÏÔʾ˫Ç×):
// A(NUL) B(NUL) C(NUL) D(NUL) E(NUL) G(NUL) F(NUL)
//
// Ôö¼ÓË«Ç׺ó,ÏÈÐò±éÀú(ÏÔʾ˫Ç×):
// A(NUL) B(A) C(B) D(B) E(D) G(E) F(D)
//
//        A
//       /
//      B
//     /  \
//    C    D
//        /  \
//       E    F
//        \
//         G
//
#include
#include
typedef struct Node  //¶þ²æÊ÷µÄ"Èý²æÁ´±í"´æ´¢½á¹¹
{
    char data;
    struct Node *lchild; //×óº¢×ÓÖ¸Õë
    struct Node *rchild; //ÓÒº¢×ÓÖ¸Õë
    struct Node *parent; //Ë«Ç×Ö¸Õë
}Bitree;

//ÓàÏÈÐòÀ©Õ¹ÐòÁÐ+µÝ¹é ´´½¨¶þ²æÊ÷
void CreateBiTree(Bitree **bt)
{
    char ch;
    scanf("%c",&ch); //ÊäÈëÊý¾Ý
    if(ch=='#')      //'#'ÊÇ¿Õ½Úµã
    {
       *bt=NULL;
    }
    else
    {
        *bt=(Bitree *)malloc(sizeof(Bitree));
        (*bt)->data=ch;
        (*bt)->parent=NULL; //ÓÃÓÚ²âÊÔ
        CreateBiTree(&((*bt)->lchild));
        CreateBiTree(&((*bt)->rchild));
    }
}

//Ôö¼ÓË«Ç×Ö¸Õë(ÓÃÏÈÐò±éÀú,µÝ¹é·¨)
void createParent(Bitree *ptr,Bitree *parent)
{
    if(ptr!=NULL)
    {
        ptr->parent = parent;
        createParent(ptr->lchild,ptr);
        createParent(ptr->rchild,ptr);
    }
}

void preOrderWithParent(Bitree *ptr) //ÏÈÐò±éÀú(ÏÔʾ˫Ç×)
{
    if(ptr!=NULL)
    {
        if(ptr->parent == NULL)
        {
           printf("%c(NUL) ",ptr->data);
        }
        else
        {
           printf("%c(%c) ",ptr->data,ptr->parent->data);
        }

        preOrderWithParent(ptr->lchild);
        preOrderWithParent(ptr->rchild);
    }
}

void preOrder(Bitree *ptr) //ÏÈÐò±éÀú
{
    if(ptr!=NULL)
    {
        printf("%c ",ptr->data);
        preOrder(ptr->lchild);
        preOrder(ptr->rchild);
    }
}

void inOrder(Bitree *ptr) //ÖÐÐò±éÀú
{
    if(ptr!=NULL)
    {
        inOrder(ptr->lchild);
        printf("%c ",ptr->data);
        inOrder(ptr->rchild);
    }
}

void postOrder(Bitree *ptr) //ºóÐò±éÀú
{
    if(ptr!=NULL)
    {
        postOrder(ptr->lchild);
        postOrder(ptr->rchild);
        printf("%c ",ptr->data);
    }
}

int main()
{
    Bitree *root;

    //´´½¨¶þ²æÊ÷,ÊäÈëÏÈÐòÀ©Õ¹ÐòÁÐ
    CreateBiTree(&root);

    printf("ÏÈÐò±éÀúÐòÁÐ: ");
    preOrder(root);
    printf("\nÖÐÐò±éÀúÐòÁÐ: ");
    inOrder(root);
    printf("\nºóÐò±éÀúÐòÁÐ: ");
    postOrder(root);
    printf("\nÏÈÐò±éÀú(ÏÔʾ˫Ç×): ");
    preOrderWithParent(root);

    createParent(root,NULL);
    printf("\n\nÔö¼ÓË«Ç׺ó,ÏÈÐò±éÀú(ÏÔʾ˫Ç×): ");
    preOrderWithParent(root);

    printf("\n");
    return 0;
}