二叉树的一个简单应用

    解决的问题很简单: 就是若干个数，判断各不相同！

    代码写的很烂,我只是验证一下.
    速度还可以,几十万个数也就是一眨眼的工夫
    因为用树的收敛速度很快, 当然这只是针对随机数列,对于不重复随机数列的复杂度平均为O(n*log2(n)) 空间占用小于4n
    最坏的情况下的复杂度就比较糟糕了,可以设想一下一个单调递增或递减的数列,其复杂度达到O(n^2),空间占用4n

    想验证的而内存少的同志请把MAXNUM改小点,没准会出错(偶没检查分配内存的返回值)
    想打印出结果来的请用重定向到一个文件比如 ./tree 2>lj.txt
    只想看看速度的./tree就可以了

    代码如果简单的扩展一下还可以用来统计数字重复出现的次数,效率也是跟上面一样的

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define MAXNUM 500000
    typedef struct tree {
        int a;
        struct tree *r;
        struct tree *l;
    };
    void detree(struct tree *node)
    {
       if( node==NULL)
               return;
       detree(node->r);
       detree(node->l);
       free(node);
    }
    int main(int argc,char *argv[])
    {
        int i;
        bool flag = true;
        int zhengshu[MAXNUM];
        struct tree *root;
        struct tree *temp;
        struct tree *rt;
        struct tree *lt;
        srand(time(NULL));
        for (i = 0; i < MAXNUM; i++) {
                zhengshu[i] = rand();
        }
        if(argc==2)
        {
                int ktemp=rand()%MAXNUM;
                int itemp=rand()%MAXNUM;
                zhengshu[ktemp]=zhengshu[itemp];
                printf("[%d]=[%d]=%d\n",ktemp,itemp,zhengshu[itemp]);
                for (i = 0; i < MAXNUM; i++) {
                        printf("[%d]=%d\n", i,zhengshu[i]);
                }
        }

        root=(tree *)malloc(sizeof(tree));
        root->a = zhengshu[0];
        root->r = NULL;
        root->l = NULL;
        for (i = 1; i < MAXNUM; i++) {
            temp = root;
            do {
                if ((zhengshu[i] != temp->a)) {
                    if (zhengshu[i] > temp->a) {
                        if (NULL != temp->r) {
                            temp = temp->r;
                            if (zhengshu[i] == temp->a) {
                                flag = false;
                                printf("\t[%d]=%d have a same one\n",i,zhengshu[i]);
                                break;
                            }
                        } else {
                            rt = (tree *) malloc(sizeof(tree));
                            temp->r = rt;
                            rt->a = zhengshu[i];
                            rt->r = NULL;
                            rt->l = NULL;
                            break;
                        }
                    } else {
                        if (NULL != temp->l) {
                            temp = temp->l;
                            if (zhengshu[i] == temp->a) {
                                flag = false;
                                printf("\t[%d]=%d have a same one\n",i,zhengshu[i]);
                                break;
                            }
                        } else {
                            lt = (tree *) malloc(sizeof(tree));
                            temp->l = lt;
                            lt->a = zhengshu[i];
                            lt->r = NULL;
                            lt->l = NULL;
                            break;
                        }
                    }
                } else {
                    flag = false;
                    break;
                }
            }while (flag == true);
            if (flag == false)
                break;
        }
        if(flag)
            printf("true\n");
        else
            printf("false\n");
        detree(root);
        return 0;
    }