BST/main.cpp at master · amit231/BST · GitHub

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;
#define quickie                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define div2(a) (!(a & 1))
#define deb(x) cout << "\n" \
                    << (#x) << " : " << (x) << "\n";
#define newl cout << "\n"

struct node
{
    int val;
    node *rchild;
    node *lchild;
    node(int key) : val(key), rchild(0), lchild(0) {}
};
node *root = 0;


node *succ(node *key)
{
    if (key->rchild)
    {
        node *l = key->rchild;
        if (l->lchild)
        {
            while (l->lchild)
            {
                l = l->lchild;
            }
            return l;
        }
        return 0;
    }
    return 0;
}

node *pred(node *key)
{
    if (key->lchild)
    {
        node *r = key->lchild;
        if (r->rchild)
        {
            while (r->rchild)
            {
                r = r->rchild;
            }
            return r;
        }
        return 0;
    }
    return 0;
}


void insert(node *p, int key)
{
    if (p)
        if (p->val < key)
        {
            if (!p->rchild)
                p->rchild = new node(key);
            else
                insert(p->rchild, key);
        }
        else if (p->val > key)
        {
            if (!p->lchild)
                p->lchild = new node(key);
            else
                insert(p->lchild, key);
        }
        else
        {
            cout << " error!\nkey " << key << " exists already";
            newl;
        }
}

void insert(int key)
{
    if (!root)
    {
        root = new node(key);
    }
    else
    {
        insert(root, key);
    }
}


void print(node *temp)
{
    if (temp)
    {
        cout << temp->val << " ";
        print(temp->rchild);
        print(temp->lchild);
    }
}


int main()
{
    quickie;
    insert(30);
    insert(40);
    insert(35);
    insert(33);
    insert(34);
    print(root);
    node *s = pred(root->rchild->lchild->lchild);

    if (s){
        deb(s->val);
    }else
        cout << "\nthere is no predesser\n";
    return 0;
}