c/dataStructure/树/btree.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#include "btree.h"

void InitTree(Tree * ptree)
{
    ptree->root = NULL;
    ptree->size = 0;
}

bool EmptyTree(const Tree * ptree)
{
    return !ptree->root?true:false;
}

int CountItem(const Tree * ptree)
{
    return ptree->size;
}


static bool ToLeft(ElemType e1, ElemType e2)
{
    return e1 < e2;
}
static bool ToRight(ElemType e1, ElemType e2)
{
    return e1 > e2;
}
static bool AddNode(Node * new, Node * root)
{
    if (ToLeft(new->e, root->e))
    {
        if (root->left == NULL)
            root->left = new;
        else
            AddNode(new,root->left);
    }
    else if (ToRight(new->e,root->e))
    {
        if (root->right == NULL)
            root->right = new;
        else
            AddNode(new,root->right);
    }
    else
        return false;
    return true;
}

bool AddItem(const ElemType e, Tree * ptree)
{
    Node * new = (Node *) calloc (1,sizeof(Node));
    if (!new)
        return false;
    new->e = e;
    
    ptree->size++;

    if (!ptree->root)
        ptree->root = new;
    else
        AddNode(new,ptree->root);

    return true;
}

bool ResTree(Node * root)
{
    Node * pnode = root;
    if (pnode->right)
    {
        ResTree(pnode->right);
        free(pnode);
    }
    else if (pnode->left)
    {
        ResTree(pnode->left);
        free(pnode);
    }
    else
        free(pnode);
    return true;
}

void PrintTree(const Node * root)
{
    printf("%c",root->e);
    if (root->left)
        PrintTree(root->left);
    if (root->right)
        PrintTree(root->right);
}