二分木の基礎理論

二分木は各ノードの子ノード数が最大2の木構造です。主要な形態として完全二分木と完全二分木が存在します。データ格納方式には配列を用いた順序格納とポインタを用いたリンク方式があります。走査方法は以下の通りです：

• 先行走査（深さ優先）
• 中間走査（深さ優先）
• 後行走査（深さ優先）
• 階層走査（幅優先）

class BinaryNode:
    def __init__(self, value, left_child=None, right_child=None):
        self.value = value
        self.left = left_child
        self.right = right_child

再帰的走査実装

先行順走査

def preorder(node):
    if not node:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)

中間順走査

def inorder(node):
    if not node:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

後行順走査

def postorder(node):
    if not node:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]

反復的走査実装

先行順（スタック方式）

def preorder_iterative(root):
    if not root:
        return []
    stack = [root]
    result = []
    while stack:
        current = stack.pop()
        result.append(current.value)
        if current.right:
            stack.append(current.right)
        if current.left:
            stack.append(current.left)
    return result

中間順（ポインタ追跡）

def inorder_iterative(root):
    stack = []
    output = []
    current = root
    while current or stack:
        if current:
            stack.append(current)
            current = current.left
        else:
            current = stack.pop()
            output.append(current.value)
            current = current.right
    return output

後行順（逆順出力）

def postorder_iterative(root):
    if not root:
        return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]

階層走査（キュー利用）

from collections import deque

def level_order(root):
    if not root:
        return []
    output = []
    nodes_queue = deque([root])
    while nodes_queue:
        level_values = []
        for _ in range(len(nodes_queue)):
            current = nodes_queue.popleft()
            level_values.append(current.value)
            if current.left:
                nodes_queue.append(current.left)
            if current.right:
                nodes_queue.append(current.right)
        output.append(level_values)
    return output

深さと高さの計算

ノードの深さは根からの距離、高さは葉からの距離です。最大深さ計算：

def max_depth(node):
    if not node:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

最小深さ計算：

def min_depth(node):
    if not node:
        return 0
    left_min = min_depth(node.left)
    right_min = min_depth(node.right)
    if not node.left or not node.right:
        return 1 + max(left_min, right_min)
    return 1 + min(left_min, right_min)

特殊二分木の操作

平衡二分木判定

def is_balanced(root):
    def check_height(node):
        if not node:
            return 0
        left_height = check_height(node.left)
        right_height = check_height(node.right)
        if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
            return -1
        return 1 + max(left_height, right_height)
    return check_height(root) != -1

二分探索木検証

def is_valid_bst(root):
    stack = []
    current = root
    prev_value = float('-inf')
    while current or stack:
        if current:
            stack.append(current)
            current = current.left
        else:
            current = stack.pop()
            if current.value <= prev_value:
                return False
            prev_value = current.value
            current = current.right
    return True

ノード削除処理

def delete_node(root, key):
    if not root:
        return None
    if key < root.value:
        root.left = delete_node(root.left, key)
    elif key > root.value:
        root.right = delete_node(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        successor = root.right
        while successor.left:
            successor = successor.left
        root.value = successor.value
        root.right = delete_node(root.right, successor.value)
    return root

構築と変換手法

配列から平衡二分探索木構築

def sorted_array_to_bst(nums):
    if not nums:
        return None
    mid_index = len(nums) // 2
    node = BinaryNode(nums[mid_index])
    node.left = sorted_array_to_bst(nums[:mid_index])
    node.right = sorted_array_to_bst(nums[mid_index+1:])
    return node

累積木への変換

def convert_bst(root):
    total = 0
    def traverse(node):
        nonlocal total
        if node:
            traverse(node.right)
            total += node.value
            node.value = total
            traverse(node.left)
    traverse(root)
    return root