Download presentation
Presentation is loading. Please wait.
Published byしおり いさやま Modified 約 6 年前
1
大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp
二分木 データ構造とプログラミング(10) 大岩 元 慶応大学環境情報学部
2
二分木とは 挿入も探索も早い 順序配列は挿入が遅い 連結リストは探索が遅い 木とは複数の節(nodes、円で表わす)が辺(edge、線で表わす)で接続されたもので、根(root)と呼ばれる親の節から複数の子の節が辺で接続され、子の節からまた複数の子の節が辺で接続されるもの 子の数が2つ以下に限られるものを二分木と言う
3
木の用語 パス(path) 根(root) 親(parent) 子(children) 葉(leaf) 部分木(subtree)
訪問(visiting) 走査(traversing) 段(level) キー(key) 二分木(binary tree)
4
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() { …. } }
5
Treeクラスの表現 class Tree[ private Node root;
public void find(int key){ … } public void insert(int id; float fd){ … } public void delete(int id){ … } ….. }
6
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”); }
7
節(ノード)の探索
8
節(ノード)探索のプログラム 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; //見つかった
9
節(ノード)の挿入
10
節(ノード)の挿入プログラム 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; }
11
木の走査(間順) private void inOrder(node localRoot) {
if (localRoot != NULL) { inOrder( localRoot.leftChild ); localRoot.displayNode); inOrder( localRoot.rightChild); }
12
間順走査の実例 private void inOrder(node localRoot) {
if (localRoot != NULL) { inOrder( localRoot.leftChild ); localRoot.displayNode); inOrder( localRoot.rightChild); }
13
数式の表現と木の走査 Inorder traverse Preorder traverse Postorder traverse
14
探索木の最小値探索 public Node minimum() { Node current, last; current = root;
while (current != null) { last = current; current = current.leftChild; } return last;
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.