木の同階層にノードを追加する

今回作成する木の構造

同じ階層にすべてのノードを埋めてから次の階層にノードを追加します。

コードのイメージ図

キューに木のノードの情報を保持させて、キューに新しいノードを追加することにより、木に同じノードが追加させます。

コード

insertbt.c

# include <stdio.h>
# include <stdlib.h>

//declare struct for queue
struct list{
  struct node *data;
  struct list *link;
};

//declare struct for tree
struct node{
  int data;
  struct node *left;
  struct node *right;
};

//initialized queue
struct list *lst = NULL;

//function declaration
void push(struct node *);
void pop();
void insert(struct node **, int);
void inorder(struct node *);

void main(){
  //initialized tree
  struct node *bt = NULL;

  //insert node to tree
  insert(&bt,1);
  insert(&bt,2);
  insert(&bt,3);
  insert(&bt,4);
  insert(&bt,5);
  insert(&bt,6);

  //display tree in inorder traversal
  inorder(bt);

}

//display tree in inorder traversal
void inorder(struct node *s){
  //if node is not empty
  if(s!=NULL){
    //call inorder function recursively for left child of node
    inorder(s->left);
    //print data of node
    printf("%d\n",s->data);
    //call inorder function recursively for right child of node
    inorder(s->right);
  }
}

//insert node at available position on the same level of tree
void insert(struct node **bt, int num){
  //if tree is empty
  if(*bt == NULL){
    //create root node
    *bt = malloc(sizeof(struct node));
    //set data of node
    (*bt)->data = num;
    //set left child of node to null
    (*bt)->left = NULL;
    //set right child of node to null
    (*bt)->right = NULL;
    
    //push root node to queue
    push(*bt);
  }else{
    //initialized locator pointer to queue
    struct list *temp = lst;
    
    //loop through queue
    while(temp!=NULL){
      //if both child of node is full, remove node from queue
      if((temp->data)->left !=NULL && (temp->data)->right != NULL){
        pop();
      }else{
        //if left child of node is empty
        if((temp->data)->left == NULL){
          //initialized pointer to left child of node
          struct node **p = &((temp->data)->left);
          //create new node at left child
          *p = malloc(sizeof(struct node));
          //set data of new node
          (*p)->data = num;
          //set left child of new node to null
          (*p)->left = NULL;
          //set right child of new node to null
          (*p)->right = NULL;

          //push new node to queue
          push(*p);
          //go back to main
          return;
        }

        //if right child of node is empty
        if((temp->data)->right == NULL){
          //initialized pointer to right child of node
          struct node **p = &((temp->data)->right);
          //create new node at right child
          *p = malloc(sizeof(struct node));
          //set data of new node
          (*p)->data = num;
          //set left child of new node to null
          (*p)->left = NULL;
          //set right child of new node to null
          (*p)->right = NULL;
          
          //push new node to queue
          push(*p);
          
          return;
        }
      }
      //go to next node in queue
      temp = temp->link;
    }
  }
}

//add node to queue
void push(struct node *t){
  //if queue is empty
  if(lst==NULL){
    //create new node in queue
    lst = malloc(sizeof(struct list));
    //set address of tree's node
    lst->data = t;
    //set link of new node to null
    lst->link = NULL;

  }else{//if queue is not empty
  
    //declare locator pointer
    struct list *temp;

    //set pointer to queue
    temp = lst;

    //loop until the last node of queue
    while(temp->link != NULL){
      //go to next node in queue
      temp = temp->link;
    }

    //set link of last node to new node
    temp->link = malloc(sizeof(struct list));
    //set address of tree's node
    (temp->link)->data = t;
    //set link of new node to null
    (temp->link)->link = NULL;
  }

  return;
}

//remove node from queue
void pop(){

  //if queue is empty
  if(lst == NULL){
    return;
    
  }else{//if queue is not empty
    
    //initialized locator pointer to queue
    struct list *temp = lst;

     //if next node in queue is not empty
    if(temp->link!=NULL){
      //set queue's pointer to next node in queue
      lst = temp->link;
      
    }else{//if last node in queue
      //set queue's pointer to null
      lst = NULL;
    }
    //free node in queue
    free(temp);
  }

  return;
}

コードの実行結果

木のノードを通りがけ順に表示します。