二分木
データ構造とプログラミング（１０）
大岩 元
慶応大学環境情報学部
[email protected]
二分木とは
挿入も探索も早い
順序配列は挿入が遅い
連結リストは探索が遅い
木とは複数の節(nodes、円で表わす)が辺(edge、線
で表わす)で接続されたもので、根(root)と呼ばれる
親の節から複数の子の節が辺で接続され、子の節
からまた複数の子の節が辺で接続されるもの
子の数が２つ以下に限られるものを二分木と言う
木の用語
パス(path) 根(root) 親(parent) 子(children) 葉(leaf) 部分木(subtree)
訪問(visiting) 走査(traversing) 段(level) キー(key) 二分木(binary tree)
Nodeクラスの表現
class Node{
int Idata;
float fData;
node leftChild;
node rightChild;
//キーとなるデータ
//その他のデータ
//左の子
//右の子
class Node{
Person p1;
//Personオブジェクトへの参照
node leftChild; //左の子
node rightChild; //右の子
class Person{
int iData;
float fData;
public void display()
{ …. }
}
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;
else {
newNode.data = fd;
current = current.rightChild;
if (rood == null) root = newNode;
if (current == null) {
else {
//根に節がない
parent.rightChild = newNode;
Node current = root;
//根から出発
return;
Node parent;
}
while (true) {
}
parent = current;
}
if (id < current.iData) {
}
current = current.leftChild;
}
if (current == null) {
parent.leftChild = 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;
}

Document