大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp 二分木 データ構造とプログラミング（１０） 大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp

二分木とは 挿入も探索も早い 順序配列は挿入が遅い 連結リストは探索が遅い 木とは複数の節(nodes、円で表わす)が辺(edge、線で表わす)で接続されたもので、根(root)と呼ばれる親の節から複数の子の節が辺で接続され、子の節からまた複数の子の節が辺で接続されるもの 子の数が２つ以下に限られるものを二分木と言う

木の用語 パス(path) 根(root) 親(parent) 子(children) 葉(leaf) 部分木(subtree) 訪問(visiting) 走査(traversing) 段(level) キー(key) 二分木(binary tree)

Nodeクラスの表現 class Node{ class Node{ Person p1; //Personオブジェクトへの参照 int Idata;　　　　　 //キーとなるデータ float fData; 　　　 //その他のデータ node leftChild;　 //左の子 node rightChild;　//右の子 public void display() { …. } } class Node{ 　Person p1; //Personオブジェクトへの参照 　node leftChild;　 //左の子 node rightChild;　//右の子 class Person{ int iData; float fData; public void display() { …. } }

Treeクラスの表現 class Tree[ private Node root; public void find(int key){ … } public void insert(int id; float fd){ … } public void delete(int id){ … } ….. }

TreeAppクラスの表現 class TreeApp{ public static void main(String[] args){ Tree theTree = new Tree; theTree.insert(50, 1.5); theTree.insert(25, 1.7); theTree.insert(75, 1.9); node found = theGree.find(25); if (found != NULL) System.out.println(“Found the node with key 25); else Wystem.out.println(“Could not find node with key 25”); }

節（ノード）の探索

節（ノード）探索のプログラム public Node find (int key) { Node current = root; //根（ルート）から出発 while (current.iData != key) { if (key < current.iData) current = current.leftChild; else current = current.rightChild; if ( current == null) return null; //見つからなかった } return current; //見つかった

節（ノード）の挿入

節（ノード）の挿入プログラム public void insert(int id, float fd){ Node newNode = new Node();//新節生成 newnode.idata = id; newNode.data = fd; if (rood == null) root = newNode; else { //根に節がない Node current = root;　　　　　//根から出発 Node parent; while (true) { parent = current; if (id < current.iData) { current = current.leftChild; if (current == null) { parent.leftChild = newNode; return; } else { current = current.rightChild; if (current == null) { parent.rightChild = newNode; return; }

木の走査(間順） private void inOrder(node localRoot) { if (localRoot != NULL) { inOrder( localRoot.leftChild ); localRoot.displayNode); inOrder( localRoot.rightChild); }

間順走査の実例 private void inOrder(node localRoot) { if (localRoot != NULL) { inOrder( localRoot.leftChild ); localRoot.displayNode); inOrder( localRoot.rightChild); }

数式の表現と木の走査 Inorder traverse Preorder traverse Postorder traverse

探索木の最小値探索 public Node minimum() { Node current, last; current = root; while (current != null) { last = current; current = current.leftChild; } return last;