組み込み開発のためのPython · レッスン 153 / 220
二分木をたどる
二分木では各ノードが最大二つの子を持ちます。前順・中順・後順の走査順を理解し、深い木では再帰深度の上限も考慮します。
二分木では各ノードが最大二つの子を持ちます。前順・中順・後順の走査順を理解し、深い木では再帰深度の上限も考慮します。 仕組みだけでなく、検証方法と運用上の注意も具体例で確認します。
基本の考え方
二分木では各ノードが最大二つの子を持ちます。前順・中順・後順の走査順を理解し、深い木では再帰深度の上限も考慮します。
安全に試すための確認
計算量だけでなく入力条件、重複値、空データ、最悪ケースを確かめます。組み込み用途ではメモリ上限と実行時間を実測し、標準ライブラリの利用も検討してください。
コード例
手元のPython環境に貼り付ける前に、使用しているPythonの版と対象ライブラリの対応を確認してください。
tree = (2, (1, None, None), (3, None, None))
def inorder(node):
if node is None:
return []
value, left, right = node
return inorder(left) + [value] + inorder(right)
print(inorder(tree))手を動かす課題
空の子を含む二分木を作り、中順走査の結果が期待どおりかテストしてください。