ALDS1_7_B Binary Treeを解く話

AOJ

二分木を実装させる問題である．

tooshitaka.hatenablog.com

とほとんど同じだ．

まず用語の整理からする．

二分木

・ノードの子の数が最大でも2である木．

・子は左，右と区別される．

ノードuの高さ

・木の最下段からuへのパスを考えたとき，通る辺の数．

ノードuの高さ計算

・ノードの深さ計算と類似．

・根から葉に向かって全てのノードを巡回．

・「子の高さ + 1」は自分の高さ，として再帰で計算．

アルゴリズム

  1. int setHeight(u)
  2.     int h1 = h2 = 0
  3.     if Tree[u].left != NIL
  4.         h1 = setHeight(Tree[u].left) + 1
  5.     if Tree[u].right != NIL
  6.         h2 = setHeight(Tree[u].right) + 1
  7.     return Max(h1,h2)

実装

gistfff80805ef0fcf4b269770b8ba2acfd2

感想

Decision Trees — OpenCV 2.4.13.2 documentation

A decision tree is a binary tree (tree where each non-leaf node has two child nodes).

 とある．基本的なデータ構造を勉強していると，具体的な応用例までをなかなか考えない．

決定木は二分木だということを覚えておく．