트리의 동일한 계층에 노드 추가

19576 단어 C

이번에 만드는 나무의 구조



동일한 계층구조에 모든 노드를 채우고 다음 계층구조에 노드를 추가합니다.



코드 이미지 다이어그램



큐에 트리의 노드의 정보를 보관 유지해, 큐에 새로운 노드를 추가하는 것으로, 트리에 같은 노드가 추가시킵니다.


코드



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


코드 실행 결과



트리의 노드를 통과 순서로 표시합니다.

좋은 웹페이지 즐겨찾기