Data-Structures/binary_tree.c at master · harikeshbg/Data-Structures · 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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<stdio.h>
#include<stdlib.h>
struct tree
{
    int info;
    struct tree *lchild,*rchild;
};
typedef struct tree *TREE;
TREE root;
void insert()
{
    int e;
    TREE newn,cur=NULL,parent=NULL;
    printf("Enter the element to bw inserted:");
    scanf("%d",&e);
    newn=(TREE)malloc(sizeof(struct tree));
    newn->info=e;
    newn->lchild=newn->rchild=NULL;
    if(root==NULL)
        root=newn;
    else
    {
        cur=root;
        while(cur!=NULL)
        {
            parent=cur;
            if(e>cur->info)
                cur=cur->rchild;
            else
                if(e<cur->info)
                    cur=cur->lchild;
                else
                {
                    printf("Element is already present in the tree ");
                    return;
                }
        }
        if(e>parent->info)
            parent->rchild=newn;
        else
            parent->lchild=newn;
    }
    return;
}
void inorder(TREE root)
{
    TREE temp=root;
    if(temp!=NULL)
    {
        inorder(temp->lchild);
        printf("%d\n",temp->info);
        inorder(temp->rchild);
    }

}
void preorder(TREE root)
{
    TREE temp=root;
    if(temp!=NULL)
    {
        printf("%d\n",temp->info);
        preorder(temp->lchild);
        preorder(temp->rchild);
    }

}
void postorder(TREE root)
{
    TREE temp=root;
    if(temp!=NULL)
    {
        postorder(temp->lchild);
        postorder(temp->rchild);
        printf("%d\n",temp->info);
    }

}
void del()
{
    int key;
    TREE cur,parent,q,successor;
    printf("Enter the key element:");
    scanf("%d",&key);
    if(root==NULL)
    {
        printf("Tree is empty\n");
        return;
    }
    cur=root;parent=NULL;
    while(cur!=NULL)
    {
        if(cur->info==key)
           break;
        parent=cur;
        cur=(key>cur->info)?cur->rchild:cur->lchild;

    }
    if(cur==NULL)
    {
        printf("Key element not found\n");
        return;
    }
    if(cur->lchild==NULL)
        q=cur->rchild;
    else
        if(cur->rchild==NULL)
            q=cur->lchild;
        else
        {
            q=successor=cur->rchild;
            while(successor->lchild!=NULL)
                successor=successor->lchild;
            successor->lchild=cur->lchild;
        }
        if(parent==NULL)
            root=q;
        if(parent->rchild==cur)
           parent->rchild=q;
        else
           parent->lchild=q;
    printf("%d deleted",cur->info);
    free(cur);
    return;
}
main()
{
    int choice;
    do
    {
        printf("\n1.insert\n2.preorder\n3.postorder\n4.inorder\n5.delete\n6.exit\nEnter your choice:");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:insert();break;
            case 2:preorder(root);break;
            case 3:postorder(root);break;
            case 4:inorder(root);break;
            case 5:del();break;
            case 6:exit(0);break;
            default:printf("Invalid choice\n");break;
        }
    }while(1);
}