sortie incorrecte de l'arbre de recherche binaire

Question

J'ai déjà débogué le code et n'ai trouvé aucune erreur. Le code ci-dessous n'imprime pas toutes les données de l'arbre de recherche binaire (BST). Seul le nœud racine et les deux derniers nœuds sont affichés dans la traversée d'ordre.

struct node{ 
    int key; 
    node *left; 
    node *right; 
}; 

node* newNode(int data){ 
    node *ptr=new node; 
    ptr->key=data; 
    ptr->left=ptr->right=NULL; 

    return ptr; 
} 

node* insert_node(node* root,int data){ 
    if(root==NULL){ 
     root=newNode(data); 
    }else if(data<=root->key){ 
     root->left=newNode(data); 
    }else{ 
     root->right=newNode(data); 
    } 

    return root; 
} 

void inorder(node* root){ 
    if(root==NULL) 
     return; 
    inorder(root->left); 
    cout<<root->key<<" "; 
    inorder(root->right); 
} 

int main(){ 
    node *root=NULL; 

    root=insert_node(root,10); 
    root=insert_node(root,12); 
    root=insert_node(root,15); 
    root=insert_node(root,1); 
    root=insert_node(root,20); 

    inorder(root); 

    return 0; 
} 

Answer 1

La fonction insert n'a aucune implémentation récursive ou itérative qui trouvera le noeud feuille. Ainsi, le nouveau nœud remplacera les nœuds enfants du nœud racine. Et je pense que c'est très bien mis en évidence dans la section des commentaires.

Voici un bloc de code dans lequel le nœud feuille est localisé à l'aide de l'itération, puis le nouveau nœud est inséré.

node *insert_node(node *root, int data){ 
struct node *ptr, *nodeptr, *parentptr; 
ptr = (struct node*)malloc(sizeof(struct node)); 
ptr->data = data; 
ptr->left = NULL; 
ptr->right = NULL; 
if(root==NULL) //tree is empty 
{ 
    root=ptr; 
    root->left=NULL; 
    root->right=NULL; 
} 
else 
{ 
    parentptr=NULL; // keep the address of parent node 
    nodeptr=root; 
    while(nodeptr!=NULL) 
    { 
     parentptr=nodeptr; 
     if(data<nodeptr->data) 
      nodeptr=nodeptr->left; 
     else 
      nodeptr = nodeptr->right; 
    } 
    // now the parentptr contains address of the leaf node 
    if(data<parentptr->data) 
     parentptr->left = ptr; 
    else 
     parentptr->right = ptr; 
} 
return root; 
} 

Vous pouvez également vous référer à d'autres sources pour une implémentation récursive de celles-ci.