이분 나무 구조

아래 그림과 같이 노드 관계는 부모 하나에 대해 두 개의 자식을가집니다.

이진 트리에 노드를 추가하는 단계 설명

코드로 생성되는 이진 트리의 예

코드로 작성하는 이분목은 아래와 같이 됩니다.

코드

btree.c

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

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

//declare functions
void insert(struct tree **, int);
void preorder(struct tree *);
void inorder(struct tree *);
void postorder(struct tree *);

void main(){
  //declare variable for getting user input
  int i=1, req, num;
  //declare pointer to point to tree structure
  struct tree *bt;

  //set pointer to empty tree
  bt = NULL;

  //get number of nodes to be insert to tree
  printf("Specify the number of data items to be inserted:\n");
  scanf("%d",&req);

  //get user input
  while(i++<=req){
    printf("Enter the data:");
    scanf("%d",&num);
    insert(&bt,num);
  }

  //display inorder traversal
  printf("Inorder Traversal:\n");
  inorder(bt);

  //display preorder traversal
  printf("Preorder Traversal:\n");
  preorder(bt);

  //display postorder traversal
  printf("Postorder Traversal:\n");
  postorder(bt);
}

//display preorder traversal
void preorder(struct tree *q){
  if(q!=NULL){
    printf("%d\n",q->data);
    preorder(q->left);
    preorder(q->right);
  }

  return;
}

//display inorder traversal
void inorder(struct tree *q){
  if(q!=NULL){
    inorder(q->left);
    printf("%d\n",q->data);
    inorder(q->right);
  }

  return;
}

//display postorder traversal
void postorder(struct tree *q){
  if(q!=NULL){
    postorder(q->left);
    postorder(q->right);
    printf("%d\n",q->data);
  }

  return;
}

//insert node to tree using recursive method
void insert(struct tree **q, int num){
  //if node is not created
  if(*q==NULL){
    //create new node
    *q = malloc(sizeof(struct tree));
    //set data
    (*q)->data = num;
    //set left child to null
    (*q)->left = NULL;
    //set right child to null
    (*q)->right = NULL;

    return;
  }else{
    //check if given number is less than node's data
    if((*q)->data >= num){
      //insert at left child
      insert(&((*q)->left), num);
    }else{
      //if given number is bigger than node's data, insert at right child
      insert(&((*q)->right),num);
    }
  }

  return;
}

코드 실행 결과

이분 나무의 표시 설명

1) 가는 순서(preorder)
부모 → 왼쪽 아이 → 오른쪽 아이 순서로 표시합니다.
코드 실행 결과를 보면 아래와 같은 순서로 표시됩니다.
6→1→0→5→3→2→4→8→7→9
※부모로부터 조사하고 싶을 때, 이쪽의 순서를 사용합니다.

2) 지나가는 순서(inorder)
왼쪽 아이 → 부모 → 오른쪽 아이 순서로 표시합니다.
코드 실행 결과를 보면 아래와 같은 순서로 표시됩니다.
0→1→2→3→4→5→6→7→8→9

3) 돌아가는 순서(postorder)
왼쪽 아이 → 오른쪽 아이 → 부모 순서로 표시합니다.
코드 실행 결과를 보면 아래와 같은 순서로 표시됩니다.
0→2→4→3→5→1→7→9→8→6
※아이로부터 조사하고 싶을 때, 이쪽의 순서를 사용합니다.