I'm building a C programme to generate a threaded binary tree and then discover the INORDER SUCCESSOR of a specific node. For this, I'm presenting the TBT's inorder sequence and then asking the user to select which node's successor should be displayed. I've built a function to accomplish this. However, I am not receiving a replacement for the FIRST NODE. Here is the whole schedule:
Code:
#include<stdio.h>#include <stdlib.h>
struct tbtnode {
int data;
struct tbtnode *left, *right;
int lbit, rbit, flag;
int child;
} *root = NULL;
typedef struct tbtnode TBT;
TBT *insuc(TBT * t);
void inorder(TBT *);
void create(TBT *);
void create(TBT * root)
{
int x, op, flag, y;
flag = 0;
char ch;
TBT *curr = root;
TBT *q, *p;
do {
printf("\nCurrent node %d \n\n 1.Left Direction.\n\n2.Right Direction",
curr->data);
printf("\nEnter ur choice :");
scanf("%d", &op);
switch (op) {
case 1:
if (curr->lbit == 1) {
printf("Enter left child of %d : ", curr->data);
scanf("%d", &x);
q = (TBT *) malloc(sizeof(TBT));
q->data = x;
q->lbit = q->rbit = 1;
q->left = curr->left;
q->right = curr;
curr->left = q;
curr->lbit = 0;
q->child = 0;
flag = 1;
} else
curr = curr->left;
break;
case 2:
if (curr->rbit == 1) {
printf("Enter right child of %d :", curr->data);
scanf("%d", &x);
q = (TBT *) malloc(sizeof(TBT));
q->data = x;
q->lbit = q->rbit = 1;
q->left = curr;
q->right = curr->right;
curr->right = q;
curr->rbit = 0;
q->child = 1;
flag = 1;
} else
curr = curr->right;
break;
}
} while (flag == 0);
}
void inorder(TBT * head)
{
TBT *t;
t = head->left;
printf("\n");
while (t->lbit == 0)
t = t->left;
while (t != head) {
printf(" %d", t->data);
t = insuc(t);
}
}
TBT *insuc(TBT * t)
{
if (t->rbit == 0) {
t = t->right;
while (t->lbit == 0)
t = t->left;
return (t);
} else
return (t->right);
}
void inorder_successor(TBT * head, int x)
{
TBT *t;
t = head->left;
printf("\n");
while (t->lbit == 0)
t = t->left;
while (t != head) {
t = insuc(t);
if (t->data == x) {
t = insuc(t);
printf(" %d", t->data);
}
}
}
int main()
{
int op, x, n, i = 0, item;
char ch;
TBT *head, *root, *succ; //here head indicates dummy variable
head = (TBT *) malloc(sizeof(TBT));
head->left = head;
head->right = head;
head->lbit = 1;
head->rbit = 1;
do {
printf("\n****Threaded binary tree operations****");
printf("\n1)create\n2)inorder\n3)Successor\n4)exit");
printf("\nEnter ur choice: ");
scanf("%d", &op);
switch (op) {
case 1:
printf("\nEnter Number Of Nodes :");
scanf("%d", &n);
printf("\nEnter root data: ");
scanf("%d", &x);
root = (TBT *) malloc(sizeof(TBT));
root->data = x;
root->lbit = root->rbit = 1;
root->child = 0;
root->left = head->left;
head->left = root;
head->lbit = 0;
root->right = head->right;
for (i = 0; i < n - 1; i++)
create(root);
break;
case 2:
printf("\nInorder Traversal Is:\n");
inorder(head);
break;
case 3:
printf("Enter the node to which successor is to be found\n");
scanf("%d", &item);
inorder_successor(head, item);
break;
case 4:
return (0);
break;
}
} while (op <= 4);
return 0;
}
The successor of the last node is 0, yet everything is good. I read this <<snipped>>, they are trying to explain it but I didn't understand. Can somebody assist me in resolving this?