読者です 読者をやめる 読者になる 読者になる

ALDS1_7_B Binary Treeを解く話

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

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).

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

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