エンジニア実践的基礎: バイナリツリー

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

バイナリツリーとは？

単方向リストを理解できれば、バイナリツリーは簡単です。単方向リストは一方向にノードをつなげるデータでした。バイナリツリーは各ノードが最大で二つの子ノードを持つことができるツリー構造です。単方向リストとは異なり、バイナリツリーは木構造を形成し、ルートノードから始まり、各ノードが左右の子ノードに分岐します。

バイナリツリーはいくつか用語が定められています。バイナリツリーに関する記事や問題を解いていく中で自然と覚えていくはずなので、一気に覚える必要はありません。

まず、一番最初のノードをルートノードと呼びます。そして、他のノードが下に接続されていないノードをリーフノードと呼びます。

ノードを親子関係で表現することもあります。他のノードに接続されたノードを親ノード、接続されたノードを左子ノード、右子ノードと呼びます。

バイナリツリーには高さと深さという測り方があります。高さはツリーの一番下のリーフノードからルートノードまでの最大の距離を指し、深さはルートノードから特定のノードまでの距離を指します。どちらも0から始まります。

あるノードより上のノードをまとめて先祖ノード、下のノードを子孫ノードとも呼びます。

実装

class TreeNode:
    def __init__(self, val):
        self.val = val # ノードの値
        self.left = None # 左子ノード
        self.right = None # 右子ノード