データ構造とアルゴリズム勉強会#5 2014/07/16 資料

BinaryTree.md

データ構造： 二分木(binary tree)

配列・線形リスト・スタック・キューなどと異なり，非線形なデータ構造のひとつ．木構造のうち，ノードが０個，１個，２個のいずれかの子を持っているものを二分木という．あるノードが３つ以上子を持っている場合，それは二分木とは呼ばない．

二分木はコンパイラや，集合（Set）の操作をO(log n)で行う二分探索木（BST），ハフマン符号化（データ圧縮に用いられる）などに応用されている．

二分木の分類

厳密二分木(strict binary tree)

各ノードが２つの子を持つか，子を持たないかのいずれかになっている木

全二分木(full binary tree)

各ノードがすべて２つの子を持ち，すべての葉が同じレベルにある木

完全二分木(complete binary tree)

全ての葉がhまたはh-1の深さを持ち、全ての葉をできるだけ左に寄せた木

二分木の基本演算

• 木に要素を加える
• 木から要素を取り除く
• 木の要素を探索する
• 木を横断する

二分木の構造

各ノードは次図のように，要素と左右の子ノードへのリンクを持つ．

class BinaryTree {
    class Node {
        int data;
        Node left;
        Node right;
    }
}