LECTURE 講義・技術関連情報｜谷口忠大Home Page（たにちゅー・どっと・こむ）

課題 12-1

——————————————–

1. １．まず，レジュメの通り　struct node の宣言をする．
2. ２．次に new_node 関数を作る．
• 関数内でメモリ確保(malloc)をする．
• 要素の値はkey を入れる．
• そのメモリ領域を指すポインタをreturnで返す．
3. ３．必要な数の構造体ポインタを宣言し，それぞれにnew_nodeで値を割り当てて，その後に，parent, right, leftなどのポインタに代入することで，繋げていく．
4. ４．最後にprint_treeする．

———————————————

まず，書かれている通りの宣言を書いてしまおう．

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

//nodeの構造体を宣言する（レジュメの通り）
struct node {
    int key;
    struct node *parent, *left, *right;
};

// 問題は↓を作れと言われている．ことと殆ど同義
struct node *new_node(int key)
{

  //関数内で新たなノードに相当するメモリ領域を確保する．
  struct node *p = malloc(sizeof(struct node));　　//mallocで

  /* あとこの関数の中でやることは   

  node *p の値 key に 引数の値 key を代入して

　parent, left, right にをリセットすること．　

　つまり，NULL値を放り込むことだ．

　最終的に関数の戻り値の型は struct node *  (node構造体型のポインタ)　なので

　p を返してあげればいいのです． */

}

main()
{
    struct node *root, *n[10];

    n[0] = new_node(4);
   //という感じで10個のnodeを作って

   /*

    ここにいろいろコードを書く

   */

   //まず　root の値を何かに設定．たとえば，　root = n[5]; のように．

　　//下のように，ノードをつないで行けばできあがり．

    n[0]->left = new_node(0);
    n[0]->right = n[1];
    n[0]->parent = n[2];

    /*

続きをいろいろ書く．

    */   

  // 最後に全体を出力．
  print_tree(root);
}

課題12-2

この問題は木構造というか二分探索木の問題です．

insert関数を作りましょうと言う問題です．

以下，データ構造とアルゴリズムの資料より

insertでは，ノードの値と比較していき，ノードの値より大きければ右，小さければ左というふうに，動いていく．

——————————————-

実装

int insert(int x, struct node *p)
{
    /* 引数のnode *p から始めて，そのノードの値と x の値を比べて

　　大きければ p を p->ritght に進め，

　　小さければ p を p->left に進めます．

　　もし同じ値があれば， return 0 で，同じ値があったので挿入しなかったと返し，

　　key が 0　のノード（外点）を見つけたら，そこに値 x を入れましょう．

    新たなノードには外点が無くなるので，　その左右には new_node(0) をしておきます．

　　挿入に成功したら， return 1; をしておきましょう．

    /*

}

main()

の中はよしなにつくってください．