ÈçºÎ½«Ò»°ã¶þ²æÊ÷±äΪ¶þ²æÅÅÐòÊ÷ cÓïÑÔ

#include 
#include 
#include /* ¶¨Òå½á¹¹Ìå */
typedef  int TypeData;
typedef struct stBiTreeNode 
{
    TypeData data;
    struct stBiTreeNode *lchild, *rchild;
}BITREENODE;/* 
* º¯Êý¹¦ÄÜ£ºÅжÏÒª²åÈëµÄÊý¾ÝÊÇ·ñ´æÔÚ 
* º¯Êý²ÎÊý£ºroot ¸ù½Úµã
            data Ҫ²éѯµÄÊý¾Ý
            lastNode Èç¹ûûÓÐÕÒµ½£¬Ôò·µ»Ø²éÕÒ×îºóÒ»¸ö½Úµã
* ·µ»ØÖµ£ºÂ 0 ´æÔÚ 1 ²»´æÔÚ 2 Ê÷ÊÇ¿ÕÊ÷
*/int isDataAlreadyExist(BITREENODE* root, TypeData data,BITREENODE** lastNode)
{
    BITREENODE* temp = root;

    /* Èç¹û¸ù½ÚµãÊǿյģ¬ÔòÖ±½Ó·µ»Ø */
    if(!temp)
    {
        return 2;
    }

    while(1)
    {
        /* Èç¹û´æÔÚÖ±½Ó·µ»Ø */
        if(temp->data == data)
        {
            return 0;
        }

        if(temp->data rchild == NULL)
            {
                /* °Ñ×îºóÒ»¸ö½ÚµãµÄµØÖ··µ»Ø³öȥ */
                (*lastNode) = temp;
                return 1;
            }
            temp = temp->rchild;
        }
        else
        {
            if(temp->lchild == NULL)
            {
                /* °Ñ×îºóÒ»¸ö½ÚµãµÄµØÖ··µ»Ø³öȥ */
                (*lastNode) = temp;
                return 1;
            }
            temp = temp->lchild;
        }

    }
}/* ÔÚ¶þ²æÅÅÐòÊ÷ÖвåÈëÊý¾Ý */BITREENODE* createSortBiTree(BITREENODE* root,TypeData data)
{
    int ret = 0;
    BITREENODE* pLastNode = NULL;

    /* ÅжÏÒª²åÈëµÄÊý¾ÝÊÇ·ñ´æÔÚ */
    ret = isDataAlreadyExist(root,data,&pLastNode);

    /* Èç¹ûÒѾ­´æÔÚÁË */
    if(ret == 0)
    {
        return root;
    }

    /* Èç¹ûûÓÐÕÒµ½£¬¾Í°ÑÕâ¸ö²åÈë */
    if(ret == 1)
    {
        BITREENODE* pNewNode = (BITREENODE*)malloc(sizeof(BITREENODE));
        pNewNode->data = data;
        pNewNode->lchild = pNewNode->rchild = NULL;

        /* ²åÈëµ½ÓÒº¢×Ó */
        if(pLastNode->data rchild = pNewNode;
        }
        /* ²åÈëµ½×óº¢×Ó */
        else if(pLastNode->data > data)
        {
            pLastNode->lchild = pNewNode;
        }

    }

    /* ¸ù½ÚµãÊÇ¿ÕµÄ,Ôòн¨Ò»¸ö¸ù½Úµã*/
    if(ret == 2)
    {
        BITREENODE* pNewNode = (BITREENODE*)malloc(sizeof(BITREENODE));
        pNewNode->data = data;
        pNewNode->lchild = pNewNode->rchild = NULL;

        root = pNewNode;
    }
    return root;
}/* ÖÐÐò±éÀú¸Ã¶þ²æÅÅÐòÊ÷ */int inOrderBiTree(BITREENODE* root)
{
    if(root)
    {       
        inOrderBiTree(root->lchild);
        printf("%d ",root->data);
        inOrderBiTree(root->rchild);
    }
    return 0;
}

int main()
{
    BITREENODE* root = NULL;

    /* ÔÚ¶þ²æÅÅÐòÊ÷ÖÖ²åÈëÊý¾Ý */
    root = createSortBiTree(root,20);
    root = createSortBiTree(root,30);
    root = createSortBiTree(root,10);
    root = createSortBiTree(root,25);

    inOrderBiTree(root);

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