# 10069. Build a Binary Search Tree (Simple Object System Ver.)

## 題目描述

• 若任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
• 任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
• 任意節點的左、右子樹也分別為二元搜尋樹。
• 沒有鍵值相等的節點（no duplicate nodes）。
1234567void insert(Node*& root, int data) {       if (!root)      root = new Node(data);    else if (data < root->data)             insert(root->left, data);       else if (data > root->data)             insert(root->right, data); }


## 範例輸入

50 1 2 4 350 2 4 1 353 1 4 2 051 4 2 0 350 4 3 2 1


## 範例輸出

0 1 2 4 3 0 2 1 4 3 3 1 0 2 4 1 0 4 2 3 0 4 3 2 1


## 編譯參數

gcc main.c basic_node.c bst_node.c object.c -std=c99


### main.c

12345678910111213141516171819202122232425262728293031323334353637383940#include <stdio.h>#include <stdlib.h> #include "node.h" void dfsPrint(bstNode *u) {    if (u == NULL)    return;    u->print(u);    dfsPrint(u->getLson(u));    dfsPrint(u->getRson(u));    FREE(bstNode, u);}void demo(bNode *u)  {    if (u == NULL)    return;    u->print(u);    demo(u->getLson(u));    demo(u->getRson(u));        FREE(bNode, u);}int main() {/*    bNode *t, *u;    t = NEW(bNode);    u = NEW(bNode);    t->setLson(t, u);    u->setRson(u, NEW(bNode));    demo(t);    */    int N;    while (scanf("%d", &N) == 1 && N) {        int *A = (int *) malloc(sizeof(int)*N);        for(int i = 0; i < N; i++)            scanf("%d", &A[i]);        bstNode *root = buildBST(A, N);        dfsPrint(root);        puts("");        free(A);    }    return 0;}


### node.c

123456789101112131415161718192021222324252627282930#ifndef _NODE_H#define _NODE_H #include "object.h" #define NodeMembers(TYPE) \    Object proto; \    int (*init)(struct TYPE*); \    void (*destroy)(struct TYPE*); \    struct TYPE* (*getLson)(struct TYPE*); \    struct TYPE* (*getRson)(struct TYPE*); \    void (*setLson)(struct TYPE*, struct TYPE*); \    void (*setRson)(struct TYPE*, struct TYPE*); \    struct TYPE *lson, *rson; \    void (*print)(struct TYPE*) typedef struct bNode {    NodeMembers(bNode);} bNode; typedef struct bstNode {    NodeMembers(bstNode);    void *extra;} bstNode; bstNode* buildBST(int A[], int n); extern Object bNodeProto;extern Object bstNodeProto;#endif


### basic_node.c

1234567891011121314151617181920212223242526272829303132333435#include "node.h"#include <stdio.h> bNode* bNode_getLson(bNode *self) {    return self->lson;} bNode* bNode_getRson(bNode *self) {    return self->rson;} void bNode_print(bNode *self) {    printf("%p L %p R %p\n", self, self->lson, self->rson);}void bNode_setLson(bNode *self, bNode *u) {    self->lson = u;}void bNode_setRson(bNode *self, bNode *u) {    self->rson = u;}  int bNode_init(bNode *self) {    self->getLson = bNode_getLson;    self->getRson = bNode_getRson;    self->setLson = bNode_setLson;    self->setRson = bNode_setRson;    self->print = bNode_print;    self->lson = NULL, self->rson = NULL;    return 1;}void bNode_destroy(bNode *obj) {} Object bNodeProto = {    .init = bNode_init,    .destroy = bNode_destroy};


### bst_node.c

123456789101112131415161718192021222324252627282930313233343536373839404142#include <stdio.h>#include <stdlib.h>#include <string.h>#include "node.h" bstNode* bstNode_getLson(bstNode *self) {    return self->lson;} bstNode* bstNode_getRson(bstNode *self) {    return self->rson;}void bstNode_setLson(bstNode *self, bstNode *u) {    self->lson = u;} void bstNode_setRson(bstNode *self, bstNode *u) {    self->rson = u;}void bstNode_print(bstNode *self) {    printf("%d ", *(int *)(self->extra));} int bstNode_init(bstNode *obj) {    obj->getLson = bstNode_getLson;    obj->getRson = bstNode_getRson;    obj->setLson = bstNode_setLson;    obj->setRson = bstNode_setRson;    obj->print = bstNode_print;    obj->extra = (void *) malloc(sizeof(int));    return 1;}void bstNode_destroy(bstNode *obj) {    free(obj->extra);} Object bstNodeProto = {    .init = bstNode_init,    .destroy = bstNode_destroy}; bstNode* buildBST(int A[], int n) {    /* add your code */}


### object.h

12345678910111213141516#ifndef _object_h#define _object_h typedef struct {    int (*init)(void *self);    void (*destroy)(void *self);} Object; int Object_init(void *self);void Object_destroy(void *self, Object proto);void *Object_new(int size, Object proto); #define NEW(T) Object_new(sizeof(T), T##Proto)#define FREE(T, t) Object_destroy(t, T##Proto) #endif


### object.c

1234567891011121314151617181920212223242526272829303132#include <stdio.h>#include <string.h>#include <stdlib.h>#include "object.h"#include <assert.h> void Object_destroy(void *self, Object proto) {    Object *obj = self;    if (proto.destroy != NULL)        proto.destroy(self);    if (obj)        free(obj);}int Object_init(void *self) {    return 1;}void *Object_new(int size, Object proto) {    if (!proto.init)         proto.init = Object_init;    if (!proto.destroy)         proto.destroy = Object_destroy;     Object *el = calloc(1, size);    *el = proto;     if(!el->init(el)) {        el->destroy(el);        return NULL;    } else {        return el;    }}