はじめに
Leetcodeでの学習中に初めて二分木表現に遭遇したので、情報を簡潔にまとめます。
TreeNodeクラスについて学習する際の参考になれば幸いです。
二分木（Binary Tree）とは？
二分木とは、各ノードが最大２つの子を持つデータ構造です。
例：
3
/ \
9 20
/ \
15 7
このような構造をPythonで表現するために、クラスを使用します。
TreeNodeクラスの定義
TreeNodeとは二分木のひとつのノードを表すクラスです。
Pythonでは次のように定義します。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
各要素の意味
| 属性 | 型 | 説明 |
|---|---|---|
val |
任意の値（例：int） | ノードの値を保持 |
left |
TreeNode または None
|
左の子ノード |
right |
TreeNode または None
|
右の子ノード |
つまり、木構造の中で
- 値(val)を持ち、
- 左のノード(left)
- 右のノード(right)
を参照できるようにしたデータ型オブジェクトです。
この点自分は勘違いしていて理解が遅くなりました...
TreeNodeはPythonが最初から持っているデータ型ではなく、人が定義したユーザー定義型です。
TreeNodeを使って木を作る
例えば以下のような木を考えます。
3
/ \
9 20
/ \
15 7
これをPyhonで表現すると以下のようになります：
node15 = TreeNode(15)
node7 = TreeNode(7)
node9 = TreeNode(9)
node20 = TreeNode(20, node15, node7)
root = TreeNode(3, node9, node20)
まとめ
本記事では、二分木の基本構造と、それをPythonで表現するためのTreeNodeについて解説しました。
- 二分木は、各ノードが最大で２つの子ノードを持つ階層構造のデータ型である。
-
TreeNodeは Python標準のデータ型ではなく、自分で定義するクラス（ユーザー定義型） である - 各ノードは
val、left、rightという３つの属性を持つ - 複数の
TreeNodeを組み合わせて参照させることで木全体を表現できる
TreeNodeの理解は今後のアルゴリズム学習で避けて通れない基礎だと思うので、この記事を参考に理解が深まれば幸いです。