木 き 構造 こうぞう 一般 いっぱん 構造 こうぞう 同様 どうよう 節点 せってん 頂点 ちょうてん 間 あいだ 結 むす 枝 えだ 辺 あたり 表 あらわ 木 き 構造 こうぞう 専用 せんよう 特 とく 有向 ゆうこう 根付 ねつ 木 き 表現 ひょうげん 使 つか 多 おお
データ構造 こうぞう 使 つか 木 き 場合 ばあい 根 ね 決 き 根付 ねつ 木 き 有向 ゆうこう 木 き 多 おお [注 ちゅう
ノード間 あいだ 関係 かんけい 家系 かけい 図 ず 見立 みた 用語 ようご 表現 ひょうげん 木 き 構造 こうぞう 内 ない 各 かく 個 こ 以上 いじょう 子 こ 英 えい child node ) を持 も 子 こ 木 き 構造 こうぞう 内 ない 下方 かほう 存在 そんざい 木 き 構造 こうぞう 成長 せいちょう 方向 ほうこう 下 した 一般 いっぱん 的 てき 子 こ 持 も 子 こ 見 み 親 しん 英 えい parent node ) である。あるノードから見 み 同 おな 親 おや 持 も 兄弟 きょうだい 英 えい sibling node ) という。あるノードから見 み 子 こ 先 さき 子 こ 全 すべ 子孫 しそん 英 えい descendant node ) と呼 よ 親 おや 先 さき 親 しん 全 すべ 先祖 せんぞ 英 えい ancestor node ) と呼 よ 高々 たかだか 1個 いっこ 親 しん 持 も
根 ね 英 えい root node ) とは、親 おや 持 も 根 ね 木 き 構造 こうぞう 最 さい 上位 じょうい 木 き 構造 こうぞう 高々 たかだか 存在 そんざい 根 ね 親 おや 子 こ 子 こ 辿 たど 必 かなら 到達 とうたつ 根 ね 特定 とくてい 経路 けいろ 常 つね 一意 いちい 図 ず 示 しめ 場合 ばあい 根 ね 一番 いちばん 上 じょう 描 えが 普通 ふつう 二分 にぶん 木 き 構造 こうぞう 根 ね 特別 とくべつ 属性 ぞくせい 持 も 木 き 構造 こうぞう 内 ない 全 すべ 頂点 ちょうてん 部分 ぶぶん 木 き 根 ね 見 み
葉 は 英 えい leaf node ) とは、子 こ 持 も 葉 は 木 き 構造 こうぞう 下位 かい 末端 まったん 木 き 複数 ふくすう 存在 そんざい
内部 ないぶ 英 えい internal node 、inner node ) とは、子 こ 持 も 葉 は 以外 いがい
高 たか 英 えい height ) とは、あるノードについて、そのノードからその子孫 しそん 葉 は 数 すう 最大 さいだい 値 ち 根 ね 高 たか 木 き 構造 こうぞう 高 たか
深 ふか 英 えい depth ) とは、逆 ぎゃく 根 ね 数 すう 根 ね 深 ふか
部分 ぶぶん 木 き 英 えい subtree ) は、木 き 構造 こうぞう 一部 いちぶ 自身 じしん 完全 かんぜん 木 き 構造 こうぞう 部分 ぶぶん 指 さ 木 き 構造 こうぞう T の任意 にんい 配下 はいか 全 ぜん 共 とも T の部分 ぶぶん 木 き 構成 こうせい 根 ね 頂点 ちょうてん 部分 ぶぶん 木 き 木 き 構造 こうぞう 全体 ぜんたい 等 ひと 根 ね 以外 いがい 頂点 ちょうてん 部分 ぶぶん 木 き 真部 まなべ 分木 ぶんき 英 えい proper subtree ) と呼 よ 部分 ぶぶん 集合 しゅうごう 真 ま 部分 ぶぶん 集合 しゅうごう
森 もり 英 えい forest ) とは、木 き 集合 しゅうごう 理論 りろん 森 もり 閉路 へいろ 連結 れんけつ 限 かぎ 森 もり 順序 じゅんじょ 木 き 順序 じゅんじょ 集合 しゅうごう 場合 ばあい 木 き 木 き 考 かんが 前 ぜん 順 じゅん 間 あいだ 順 じゅん 後 こう 順 じゅん 走査 そうさ 法 ほう 再帰 さいき 的 てき 定義 ていぎ
子 こ 順序 じゅんじょ 性 せい
編集 へんしゅう
あるノードの子 こ 群 ぐん 間 あいだ 順序 じゅんじょ 存在 そんざい 木 き 順序 じゅんじょ 存在 そんざい 木 き 順序 じゅんじょ 性 せい 木 き 実装 じっそう 子 こ リスト に入 い 各 かく 枝 えだ 異 こと 自然 しぜん 数 すう 付与 ふよ 子 こ 間 あいだ 順序 じゅんじょ 入 い 順序 じゅんじょ 付 つ 木 き 英 えい ordered tree ) である。順序 じゅんじょ 付 つ 木 き 応用 おうよう 2分 ふん 探索 たんさく 木 き などがある。コンピュータ中 ちゅう 構造 こうぞう 順序 じゅんじょ 存在 そんざい 構造 こうぞう セット型 がた のように存在 そんざい 一般 いっぱん 的 てき 普通 ふつう 実装 じっそう 自然 しぜん 順序 じゅんじょ 付 つ 木 き
コンピュータ で利用 りよう 場合 ばあい 実装 じっそう 方法 ほうほう 典型 てんけい 的 てき 実装 じっそう 動的 どうてき 確保 かくほ 表 あらわ 構造 こうぞう 体 たい 領域 りょういき 確保 かくほ ポインタ で親 しん 子 こ 参照 さんしょう
各 かく 子 こ 持 も 各 かく 親 しん 持 も 各 かく 親 しん 子 こ 持 も 各 かく 長男 ちょうなん 弟 おとうと 持 も 他 ほか 配列 はいれつ 使 つか 実装 じっそう 親子 おやこ 関係 かんけい 決定 けってい 例 たと 二分 にぶん
前 ぜん 順 じゅん 間 あいだ 順 じゅん 後 こう 順 じゅん レベル順 じゅん 木 き 構造 こうぞう 走査 そうさ 英 えい traverse ) とは、木 き 構造 こうぞう 全 ぜん 一 いち 回 かい 体系 たいけい 的 てき 調査 ちょうさ 処理 しょり 連結 れんけつ 次元 じげん 配列 はいれつ 線形 せんけい 性 せい 構造 こうぞう 走査 そうさ 普通 ふつう 前 まえ 順番 じゅんばん 行 おこな 後 うし 方法 ほうほう 木 き 構造 こうぞう 走査 そうさ 下記 かき 方法 ほうほう 以下 いか 二 に 分木 ぶんぎ 関 かん 多分 たぶん 木 き 応用 おうよう 可能 かのう
深 ふか 優先 ゆうせん 探索 たんさく
編集 へんしゅう
深 ふか 優先 ゆうせん 探索 たんさく 現在 げんざい 調査 ちょうさ 子 こ 対 たい 同 おな 繰 く 返 かえ 従 したが 再帰 さいき 呼 よ 出 だ 容易 ようい 表現 ひょうげん ループ でも実装 じっそう 可能 かのう 走査 そうさ 法 ほう 調査 ちょうさ 順序 じゅんじょ 以下 いか 分類 ぶんるい 方法 ほうほう 根 ね 探索 たんさく 開始 かいし
前 ぜん 順 じゅん 先行 せんこう 順 じゅん 前 ぜん 置 おけ 順 じゅん 行 い 順 じゅん 英 えい pre-order )
根 ね 調査 ちょうさ もしあれば、左 ひだり 部分 ぶぶん 木 き 前 まえ 順 じゅん 走査 そうさ
もしあれば、右 みぎ 部分 ぶぶん 木 き 前 まえ 順 じゅん 走査 そうさ
2分 ふん 探索 たんさく 木 き のコピーを作 つく 際 さい 利用 りよう 数式 すうしき 構文 こうぶん 木 き ポーランド記法 きほう の表現 ひょうげん 得 え 利用 りよう 間 あいだ 順 じゅん 中間 なかま 順 じゅん 通 とお 順 じゅん 英 えい in-order )
もしあれば、左 ひだり 部分 ぶぶん 木 き 間 あいだ 順 じゅん 走査 そうさ
根 ね 調査 ちょうさ もしあれば、右 みぎ 部分 ぶぶん 木 き 間 あいだ 順 じゅん 走査 そうさ
多分 たぶん 木 き 定義 ていぎ 2分 ふん 探索 たんさく 木 き では、間 あいだ 順 じゅん 走査 そうさ 走査 そうさ 順 じゅん 順序 じゅんじょ 使 つか 後 こう 順 じゅん 後 こう 行 くだり 順 じゅん 後 ご 置 おけ 順 じゅん 帰 かえ 順 じゅん 英 えい post-order )
もしあれば、左 ひだり 部分 ぶぶん 木 き 後 こう 順 じゅん 走査 そうさ
もしあれば、右 みぎ 部分 ぶぶん 木 き 後 こう 順 じゅん 走査 そうさ
根 ね 調査 ちょうさ 幅優先 はばゆうせん 探索 たんさく
編集 へんしゅう
レベル順 じゅん 英 えい level-order )
幅優先 はばゆうせん 探索 たんさく 深 ふか 同 おな 浅 あさ 方 ほう 順 じゅん 走査 そうさ
この2分 ふん 探索 たんさく 木 き において、
前 ぜん 順 じゅん 走査 そうさ 調査 ちょうさ 順 じゅん 間 あいだ 順 じゅん 走査 そうさ 調査 ちょうさ 順 じゅん 2分 ふん 探索 たんさく 木 き 間 あいだ 順 じゅん 走査 そうさ 順 じゅん 後 こう 順 じゅん 走査 そうさ 調査 ちょうさ 順 じゅん レベル順 じゅん 走査 そうさ 調査 ちょうさ 順 じゅん
前 ぜん 順 じゅん n )
n を処理 しょり 子 こ 前 ぜん 順 じゅん 間 あいだ 順 じゅん n )
if (n に左 ひだり 子 こ 間 あいだ 順 じゅん 左 ひだり 子 こ 処理 しょり 右 みぎ 子 こ 間 あいだ 順 じゅん 右 みぎ 子 こ 後 こう 順 じゅん n )
for each (n の子 こ 後 ご 順 じゅん 処理 しょり これらの実装 じっそう 木 き 構造 こうぞう 高 たか コールスタック 領域 りょういき 必要 ひつよう 平衡 へいこう 保 たも 木 き 深刻 しんこく 問題 もんだい 場合 ばあい 各 かく 親 しん 位置 いち 覚 おぼ 使 つか
下記 かき 順 じゅん 擬似 ぎじ
レベル順 じゅん n )
n をキューに追加 ついか 要素 ようそ 含 ふく 取 と 出 だ 処理 しょり 子 こ 追加 ついか
糸 いと 付 つ 分木 ぶんぎ また、糸 いと 付 つ 分木 ぶんぎ （英語 えいご 版 ばん 英 えい threaded binary tree ) を使 つか 方法 ほうほう 年 ねん 発表 はっぴょう [1] 糸 いと 付 つ 分木 ぶんぎ 子 こ 場合 ばあい 間 あいだ 順 じゅん 前 まえ 後 うし 左 ひだり 子 こ 右 みぎ 子 こ 設定 せってい 木 き 構造 こうぞう 場合 ばあい 子 こ 有無 うむ 以外 いがい 示 しめ 必要 ひつよう 使 つか 間 あいだ 順 じゅん 走査 そうさ 効率 こうりつ 非常 ひじょう 前 ぜん 順 じゅん 後 こう 順 じゅん 通常 つうじょう 使 つか 実装 じっそう 方 ほう
糸 いと 付 つ 分木 ぶんぎ 間 あいだ 順 じゅん 走査 そうさ 次 つぎ
アイテム（データを持 も 数 すう 数 かぞ 上 あ
あるアイテムを探索 たんさく
新 あら 木 き 構造 こうぞう 特定 とくてい 位置 いち 追加 ついか アイテムを削除 さくじょ
部分 ぶぶん 木 き 削除 さくじょ 枝 えだ 刈 が 部分 ぶぶん 木 き 追加 ついか 接 つ 木 き 任意 にんい 根 ね 探 さが 木 き 構造 こうぞう 種類 しゅるい
編集 へんしゅう
子 こ 数 すう 分類 ぶんるい 二 に 分木 ぶんぎ 各 かく 子 こ 最大 さいだい 木 き 多分 たぶん 木 き 子 こ 以上 いじょう 持 も 含 ふく 木 き 二 に 分木 ぶんぎ 木 き 平衡 へいこう 木 き 木 き 葉 は 深 ふか 等 ひと 木 き ヒープ
デジタル木 き - 主 おも 文字 もじ 列 れつ 格納 かくのう 木 き その他 た コンピュータにみる木 き 構造 こうぞう
編集 へんしゅう
木 き 構造 こうぞう 主 おも 以下 いか 用途 ようと 使 つか
^ 一般 いっぱん 無 む 向 こう 木 き 含 ふく 任意 にんい 根 ね 解釈 かいしゃく 可能 かのう 非 ひ 根付 ねつ 木 き 有向 ゆうこう 木 き 葉 は 根 ね 向 む 向 む 場合 ばあい 根 ね 葉 は 向 むか 向 む 場合 ばあい 根 ね 決 き 根付 ねつ 木 き
^ Morris, Joseph M. (December 1979). “Traversing binary trees simply and cheaply”. Information Processing Letters 9 (5): 197-200. doi :10.1016/0020-0190(79)90068-1 .
Donald Knuth . The Art of Computer Programming: Fundamental Algorithms , Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Section 2.3: Trees, pp.308–423.Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest , and Clifford Stein. Introduction to Algorithms , Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Section 10.4: Representing rooted trees, pp.214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp.253–320.
Dale, Nell. Lilly, Susan D. "Pascal Plus Data Structures". D. C. Heath and Company. Lexington, MA. 1995. Fourth Edition.
Drozdek, Adam. "Data Structures and Algorithms in C++". Brook/Cole. Pacific Grove, CA. 2001. Second edition. 
_01.png)
