Microsoft Word - NonGenTree.doc

Transcription

1 ジェネリクスとコンパレータを使用しない 2 分探索木のプログラム例 BinTreeNG.java: 2 分探索木のクラス BinTreeNG BinTreeTesterNG.java: BinTreeNG を利用するプログラム例 === BinTreeNG.java ========================================================================= // ジェネリクスを使用しない2 分探索木の例 // List.10-1 (pp ) をジェネリクスおよびコンパレータを使用しない形に修正 // 主な修正点 // (1) BinTree<K,V> -> BinTreeNG // (2) Node の key を廃止 (Data 内のフィールド int no をキーとするため ) // メソッドの引数から K key を削除 // K -> int // (2) Node の data を Data クラスに固定 // class Data を簡略化して定義 (scandata, コンパレータを削除 ) // Node<K,V> -> Node // V -> Data // (3) メソッド search をキー毎に分離しコンパレータ不使用に // search() -> searchno(), searchname() // public class BinTreeNG { //--- データ ( 会員番号 + 氏名 ) ---// public static class Data { private Integer no; // 会員番号 private String name; // 氏名 Data(Integer no, String name) { // コンストラクタ this.no = no; this.name = name; //--- 文字列表現を返す ---// public String tostring() { return "(" + no + ") " + name; //--- キー値を返す ---// int getkey() { return no; //--- ノード ---// static class Node { private Data data; // データ private Node left; // 左子ノード private Node right; // 右子ノード //--- コンストラクタ ---//

2 Node(Data data, Node left, Node right) { this.data = data; this.left = left; this.right = right; //--- キー値を返す ---// int getkey() { return data.getkey(); //--- データを返す ---// Data getvalue() { return data; //--- データの表示 ---// void print() { System.out.println(data); private Node root; // 根 //--- コンストラクタ ---// public BinTreeNG() { root = null; //--- キーによる探索 ---// public Data searchno(int key) { Node p = root; // 根に着目 while (true) { if (p == null) // これ以上進めなければ return null; // 探索失敗 if(key == p.getkey()) // key とノード p のキーが等しければ return p.getvalue(); // 探索成功 if (key < p.getkey()) // key のほうが小さければ p = p.left; // 左部分木から探索 // key のほうが大きければ p = p.right; // 右部分木から探索 //--- node を根とする部分木にノード <K,V> を挿入 ---// private void addnode(node node, Data data) { if (data.getkey() == node.getkey()) return; // key は2 分探索木上に既に存在 if (data.getkey() < node.getkey()) { if (node.left == null) node.left = new Node(data, null, null);

3 addnode(node.left, data); // 左部分木に着目 { if (node.right == null) node.right = new Node(data, null, null); addnode(node.right, data); // 右部分木に着目 //--- ノードを挿入 ---// public void add(data data) { if (root == null) root = new Node(data, null, null); addnode(root, data); //--- キー値が key であるノードを削除 --// public boolean remove(int key) { Node p = root; // 走査中のノード Node parent = null; // 走査中のノードの親ノード boolean isleftchild = true; // p は parent の左子ノードか? while (true) { if (p == null) // これ以上進めなければ return false; // そのキー値は存在しない if (key == p.getkey()) // key とノード p のキー値を比較, 等しければ // 探索成功 { parent = p; // 枝をくだる前に親を設定 if (key < p.getkey()) { // key のほうが小さければ isleftchild = true; // これからくだるのは左の子 p = p.left; // 左部分木から探索 { // key のほうが大きければ isleftchild = false; // これからくだるのは右の子 p = p.right; // 右部分木から探索 if (p.left == null) { // p には左の子がない if (p == root) root = p.right; if (isleftchild) parent.left = p.right; // 親の左ポインタが右の子を指す parent.right = p.right; // 親の右ポインタが右の子を指す if (p.right == null) { // p には右の子がない if (p == root) root = p.left; if (isleftchild) parent.left = p.left; // 親の左ポインタが左の子を指す

4 parent.right = p.left; // 親の右ポインタが左の子を指す { parent = p; Node left = p.left; // 部分木の中の最大ノード isleftchild = true; while (left.right!= null) { // 最大ノード left を探索 parent = left; left = left.right; isleftchild = false; p.data = left.data; // left のデータを p に移動 if (isleftchild) parent.left = left.left; // left を削除 parent.right = left.left; // left を削除 return true; //--- node を根とする部分木のノードをキー値の昇順に表示 ---// private void printsubtree(node node) { if (node!= null) { printsubtree(node.left); // 左部分木をキー値の昇順に表示 System.out.println(node.data); // node を表示 printsubtree(node.right); // 右部分木をキー値の昇順に表示 //--- 全ノードをキー値の昇順に表示 ---// public void print() { printsubtree(root); ===========================================================================================

5 === BinTreeTesterNG.java =================================================================== // ジェネリクスを使用しない2 分探索木クラス BinTreeNG の利用例 // BinTreeTester.java からの変更点 // Data クラスの定義を BinTreeNG に移動 // Data -> BinTreeNG.Data // 追加 を scandata() を用いないように修正 // 探索 をコンパレータ不使用の形に修正 // メニューに木の初期化を追加 import java.util.scanner; class BinTreeTester { static Scanner stdin = new Scanner(System.in); //--- メニュー列挙型 ---// enum Menu { ADD( " ノード挿入 "), REMOVE( " ノード削除 "), SEARCH( " ノード探索 "), PRINT( " 全データ表示 "), // *** ここに追加項目を挿入 INIT_TREE( " 初期化 "), // *** ここまで追加項目 TERMINATE(" 終了 "); private final String message; static Menu MenuAt(int idx) { for (Menu m : Menu.values()) if (m.ordinal() == idx) return m; return null; // 木を作成 // 表示用文字列 // 序数が idx である列挙を返す Menu(String string) { message = string; String getmessage() { return message; // コンストラクタ // 表示用文字列を返す //--- メニュー選択 ---// static Menu SelectMenu() { int key; do { for (Menu m : Menu.values()) { System.out.printf("(%d) %s ", m.ordinal(), m.getmessage()); if ((m.ordinal() % 3) == 2 && m.ordinal()!= Menu.TERMINATE.ordinal()) System.out.println();

6 System.out.print(":"); key = stdin.nextint(); while (key < Menu.ADD.ordinal() key > Menu.TERMINATE.ordinal()); return Menu.MenuAt(key); public static void main(string[] args) { Menu menu; // メニュー BinTreeNG.Data data; // 追加用データ参照 BinTreeNG.Data ptr; // 探索用データ参照 Integer no; // 番号 ( 追加 検索用 ) String name; // 名前 ( 追加 検索用 ) BinTreeNG tree = new BinTreeNG(); do { switch (menu = SelectMenu()) { case ADD : // ノードの挿入 System.out.println(" 挿入するデータを入力して下さい."); System.out.print(" 番号 :"); no = stdin.nextint(); System.out.print(" 名前 :"); name = stdin.next(); data = new BinTreeNG.Data(no, name); tree.add(data); case REMOVE : // ノードの削除 System.out.println(" 削除するデータを入力して下さい."); System.out.print(" 番号 :"); no = stdin.nextint(); tree.remove(no); case SEARCH : // ノードの探索 System.out.println(" 探索するデータを入力して下さい."); System.out.print(" 番号 :"); no = stdin.nextint(); ptr = tree.searchno(no); if (ptr!= null) System.out.println(" その番号の氏名は " + ptr + " です "); System.out.println(" 該当データはありません "); case PRINT : tree.print(); // 全ノードをキー値の昇順に表示 case INIT_TREE: // 木を初期化 data = new BinTreeNG.Data(1, " 武田信玄 "); tree.add(data); data = new BinTreeNG.Data(2, " 上杉謙信 "); tree.add(data); data = new BinTreeNG.Data(3, " 織田信長 "); tree.add(data); data = new BinTreeNG.Data(4, " 豊臣秀吉 "); tree.add(data); data = new BinTreeNG.Data(5, " 徳川家康 "); tree.add(data);

7 while (menu!= Menu.TERMINATE); ===========================================================================================