Inorder преемник Threaded Binary Tree

Question

Я пишу программу c для создания многопоточного двоичного дерева, а затем для поиска INORDER SUCCESSOR конкретного узла. Для этого я показываю последовательность порядка для TBT, а затем прошу пользователя ввести узел, на который должен отображаться преемник. Я написал функцию для этого. Но я не получаю преемника для FIRST NODE .. Преемник последнего узла - это все возможные способы его работы. Может ли кто-нибудь помочь мне исправить это? Вот вся программа:

#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; 
} 

пожалуйста исправить - функция inorder_successor() для меня .. Спасибо

Answer 1

У вас есть много проблем с вашим кодом. Для начала вы никогда не проверяете указатели NULL. Чтобы продолжить, у вас есть глобальная и локальная переменная в main под названием root.

Последнее означает, что при распределении памяти для root в main вы выделяете для локальной переменной, а глобальная переменная все равно будет NULL.

Есть и другие вещи, которые выглядят странно, например, вы назначаете left и right указатель head себе.

Я думаю, вам нужно сначала выложить все на бумаге, как у вас сейчас, так и как вы хотите. Это поможет вам лучше визуализировать дерево.