C++で学ぶ式ツリー（Expression Tree）の基本と具体例
式ツリーとは何か
式ツリー（Expression Tree）とは、二分木の一種であり、木の各ノードが「演算子」または「オペランド（被演算子）」のいずれかで構成される特殊なデータ構造です。数式を木構造として表現することで、コンパイラや電卓アプリなどが数式を効率的に解析・評価できるようになります。
ノードの役割
式ツリーにおける各ノードは、次のように役割が分かれています。
- 葉ノード（リーフノード）：オペランド（数値や変数）を表します。
- 非葉ノード（内部ノード）：演算子（+、-、*、/ など）を表します。
つまり、計算の対象となる値は必ず葉に配置され、それらをどのように処理するかを示す演算子が親ノードとして上に積み重なる構造になります。
式ツリーの例
以下は、式ツリーの構造を示した図の例です。
中間記法（ infix 記法）への変換
式ツリーから人間にとって理解しやすい中間記法（infix 表記）の数式を取得するには、中順走査（inorder traversal）を用いて木を巡回します。中順走査では、「左の子ノード → 現在のノード → 右の子ノード」の順に訪問するため、演算子がオペランドの間に正しく配置された数式が得られます。
なお、走査方法によって異なる記法の数式を得られる点も覚えておくと便利です。
- 中順走査（inorder）：中間記法（例：A + B）
- 後順走査（postorder）：後置記法・逆ポーランド記法（例：A B +）
- 前順走査（preorder）：前置記法・ポーランド記法（例：+ A B）
このように、式ツリーは一つの木構造から複数の記法へ柔軟に変換できるため、構文解析や式の評価を実装する際に非常に有用なデータ構造です。
-
C++で二分木を剪定する：1を含まない部分木を削除する再帰アルゴリズム
問題概要二分木のルートノード root が与えられ、すべてのノードの値は 0 または 1 のいずれかであるとします。この木から、1 を含まないすべての部分木を削除した結果の木を求めるのが目的です。たとえば、次のような木が与えられた場合 −解決のためのアプローチこの問題は、再帰的な手法を用いて以下の手順で解決できます −ノードを引数として受け取る再帰メソッド solve() を定義します。処理の流れは次のとおりです −ノードが null の場合は、null を返しますノードの左の子に対して solve(左の子) を実行し、その結果を左の子に代入しますノードの右の子に対して solve(右の子)
-
C++で配列を実装した二分木
二分木は、ツリーの各ノードが最大2つの子ノードを持つことができる特殊なタイプのツリーです。これらの子ノードは、右子および左子と呼ばれます。 単純な二分木は-です 木を表現するには、2つの方法があります。 リンクリストを使用する動的ノード表現 配列を使用する順次表現。 ここでは、二分木の配列表現について説明します。このために、BTのノードに番号を付ける必要があります。この番号付けは、0から（n-1）または1からnまで開始できます。 配列内のノードとその親ノードおよび子ノードの位置を導き出します。 0インデックスベースのシーケンスを使用する場合 親ノードがインデックスpであ