# C言語/C++入門＞ポインタ

ツリー

リンクリストの場合、要素を検索したり追加する際に、目的とする要素を1つずつ確認する必要があるため時間がかかります。
ツリーというデータ型を使用すると、比較の回数を減らせ速度アップとなります。

ツリーはノードから構成され、先頭のノードがルートノード、ルートノード（根）から枝分かれしていくノードをリーフノード（葉）と言います。
バイナリツリー（2分木）のデータ構造は、ルートノードから左方向と右方向へと枝が２つに分岐する構造です。

各ノードは、左方向の枝をポイントする左ポインタと、右方向の枝をポイントする右ポインタという2つのポインタを持ちます。

class tree {
private:
    // ツリーの基本ノード
    class node {
    private:
        node *right;    // 右方向の枝
        node *left;        // 左方向の枝
    public:
        std::string word;    // このノードの単語
 
        friend class tree;
    };
 
    // ツリーの先頭
    node *root;
 
    // コンストラクタ
    tree() {root = NULL;}
    
    // その他のメンバ
};

バイナリツリーのデータ構造は、上記のようなクラスで表せます。
右方向には、ノードの数字や文字列と比較して、大きいものを格納していく。
左方向には、小さいものを格納していく。
扱う要素とノードに格納されたものの大小を比べることで、検索範囲を大幅に減らせるので、スピードが早いデータ構造となります。

ツリーは、2分岐のバイナリーツリーでなければならないわけではありません。
分岐する枝は何本でも良いですが、複雑なデータ構造となっていきます。
裏を返せば、複雑な構造のデータを扱うことができると言えます。

<< 前の記事 : 二重リンクリスト