C言語　バイナリーサーチツリー

学んだことのまとめのつもりなので間違えてるとこがありましたら、教えていただけると助かります！

バイナリーサーチツリー

バイナリーサーチツリーとは？

基本的なツリー構造のイメージ

nodeを追加する

• 親nodeよりも大きい場合はright、親よりも小さい場合はleft

10　を追加する場合

nodeを削除する

• nodeを削除したら、削除したnodeの右側から一番小さいデータをもつnodeを、削除したnodeの場所にもってくる。左側から一番大きいデータをもつnodeを、持ってきてもいい。

6 を削除する場合

簡単なコードの説明

• void* create_newnode() で新しく追加したいデータのノードを作成
• void* add_node() データをツリーに追加
• void* remove_node() データをツリーから消す

free()で確保していたメモリを解放（解放しないと、うまく動かない原因になるかも）

• void print_tree() でツリーのデータを確認
• int serch_min() で削除したいnodeのrightから一番小さいデータを持つnodeをさがす

実行結果

        *
    12
            *
        10
            *
8
        *
    4
        *

コード

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

typedef struct NODE{
  int data;
  struct NODE *left;
  struct NODE *right;
}node;

int serch_min(node *root);

void* create_newnode(int data){
  node *newnode;
  newnode=malloc(sizeof(node));
  newnode->data=data;
  newnode->left=NULL;
  newnode->right=NULL;
  return newnode;
}

void* add_node(node* head,int data){
  node *newnode=create_newnode(data);
  node *ptr=head;
  if(head==NULL){//headがNULLということはツリーに何もデータが入っていないということ
    head=newnode;
    return head;//headを返さないとmainのheadが変更されない
  }else{
    while(ptr!=NULL){
      if(ptr->data < newnode->data){//追加したいデータが大きい場合はrightに進む
        if(ptr->right==NULL){//NULLということは比べるデータが無いので、newnodeを追加できる
          ptr->right=newnode;
          return head;//headを返さないとmainのheadが変更されない
        }
        ptr=ptr->right;
      }else if(ptr->data > newnode->data){//追加したいデータが小さい場合はleftに進む
        if(ptr->left==NULL){//NULLということは比べるデータが無いので、newnodeを追加できる
          ptr->left=newnode;
          return head;//headを返さないとmainのheadが変更されない
        }
        ptr=ptr->left;
      }
    }
  }
}

void* remove_node(node* head,int data){
  if(head->data==data){//削除したいデータを見つけた
    if(head->left==NULL && head->right==NULL){//削除したいデータのleftとrightがNULLということは、その下には何もデータがないからそのまま削除する
      node* temp=head;
      free(temp);
      return NULL;
    }else if(head->left==NULL){//leftには何もないのでrightに上書きする
      node* temp=head;
      free(temp);
      return head->right;
    }else if(head->left!=NULL){
      int min=serch_min(head->right);//右側から一番小さいデータを探す
      head->right=remove_node(head->right,min);//持ってきたデータをもつnodeを削除する
      head->data=min;//削除したいデータを一番小さいデータに上書きする
    }
  }else if(head->data > data){//削除したいデータが小さい場合はleftに進む
    head->left=remove_node(head->left,data);
  }else if(head->data < data){//削除したいデータが大きい場合はrightに進む
    head->right=remove_node(head->right,data);
  }
  return head;//headを返さないとmainのheadが変更されない
}

int serch_min(node *root){
  if(root->left==NULL){//一番左側にあるのが一番小さいデータということ
    return root->data;
  }
  serch_min(root->left);
}

void print_tree(node *ptr,int h){
  if (ptr==NULL) {
        for(int i=0;i<h;i++){
          printf("\t");
        } 
        printf("*\n");
        return;
    }
    print_tree(ptr->right,h+1);
    for(int i=0;i<h;i++){
      printf("\t");
    } 
    printf("%d\n",ptr->data);
    print_tree(ptr->left,h+1);
}

int main(void) {
  static node *head=NULL;
  head=add_node(head,6);
  head=add_node(head,2);
  head=add_node(head,4);
  head=add_node(head,12);
  head=add_node(head,8);
  head=add_node(head,10);
  head=remove_node(head,2);
  head=remove_node(head,6);
  print_tree(head,0);
}