C言語で二分木を作る

二分木の構造体

下記の図のようにノードの関係は親一つに対して2つの子を持ちます。

二分木にノードを追加するステップの説明

コードで生成される二分木の例

コードで作成する二分木は下記のようになります。

コード

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
※子から調べたい時に、こちらの順序を使用します。