二元樹

　
用 C 語言的 struct 建立二元樹，一般作法是用兩個
link list node 不斷去連結子樹。 用 array 建也是可行的，
特別是超大型、且要求高速存取的二元樹，
一般會用 hash 來分配節點。

底下是簡單範例，使用 C 建立一個 binary tree 形式的
container，並附上相關操作。

//--------------- BTree definition --------------------

typedef struct Node
{
    void *data;                     //資料項
    Node *L, *R;                    //指向左右子樹
} 
Node;
                                    //建樹            
void add (Node** p, void* data, 
          int (*comp)(void*,void*), int size)    
{
    void* obj;

    if (!*p) {
        obj = malloc (size);        //建立存放物件的空間
        memcpy (obj, data, size);
        *p = (Node*) malloc (sizeof(Node));
        (*p)->data = obj;
        (*p)->L = (*p)->R = 0;
    }
    else if (comp((*p)->data, data)) 
        add (&(*p)->L, data, comp, size);    //建左子樹  
    else 
        add (&(*p)->R, data, comp, size);    //建右子樹
}

void release (Node* p)              //砍樹
{
    if (!p) return;
    release (p->L);
    release (p->R);
    free (p->data);
    free (p); p = 0;
}


typedef enum {PRE, IN, POST} Order;    //指定節點拜訪順序
void show (Node* p, Order o, void (*print)(void*))  //秀樹
{
    if (!p) return;
    if (PRE == o) print (p->data);  show (p->L, o, print);
    if (IN  == o) print (p->data);  show (p->R, o, print);
    if (POST== o) print (p->data);    
}


//---------------------- Instance ------------------------

typedef struct { char* name; int IQ; } Grade;

void print_int(void* i)          { printf(" %d", *(int*)i);     }
int  comp_int (void* a, void* b) { return *(int*)a > *(int*)b;  }
void print_ch (void* i)          { printf("%c", *(char*)i);     }
int  comp_ch  (void* a, void* b) { return *(char*)a > *(char*)b;}
void print_iq (void* i)          { printf(" %s", ((Grade*)i)->name); }
int  comp_iq  (void* a, void* b) { return ((Grade*)a)->IQ > ((Grade*)b)->IQ;}

int main (void)   
{   
    int   i, j;
    char  exp[] = "hello word";
    Grade grade[] = 
    {
        "羅開",  120,
        "木蘭花",130,
        "高達",  113,
        "白素",  145,
        "衛斯理",115, 
    };
    Node* root = 0;
    srand (time (0));

    //TEST1
    for (i=0; i<10; i++) {        
        j = rand()%100;
        add (&root, &j, comp_int, sizeof(int));        
    }
    show (root, IN, print_int);
    release (root);
    puts("\n");
    root=0;

    //TEST2
    for (i=0; i<sizeof exp; i++)         
        add (&root, exp+i, comp_ch, sizeof(char));            
    show (root, IN, print_ch);
    release (root);
    puts("\n");
    root=0;

    //TEST3
    for (i=0; i<5; i++)         
        add (&root, grade+i, comp_iq, sizeof(Grade));            
    show (root, IN, print_iq);
    release (root);

    getch();
    return 0;
}

用 Haskell 寫，流程架構更為清晰：

data Tree  a = Leaf | Node(a, Tree a, Tree a)
add n Nil = Node n Nil Nil
add n p @ (Node v L R)
        | n < v = Node x (add n L) R
        | n > v = Node x L (add n R)
        | otherwise = p
preodr  Leaf=[] preodr (Node x,L,R) = [x] ++ preodr L ++ preodr R
postodr Leaf=[] postodr(Node x,L,R) = postodr L ++ postodr R ++ [x]
inodr   Leaf=[] inodr  (Node x,L,R) = inodr L ++ [x] ++ inodr R