# Tree - Binary Trees

Ԑ : 1 sec, : 131072 KB
pł͂

# 񕪖

^ꂽt񕪖 $T$ ̊eߓ_ $u$ ɂāAȉ̏o͂vO쐬ĂB

• $u$ ̐ߓ_ԍ
• $u$ ̐e
• $u$ ̌Z
• $u$ ̎q̐
• $u$ ̐[
• $u$ ̍
• ߓ_̎ށiAߓ_܂͗tj

ł́A^񕪖؂ $n$ ̐ߓ_Aꂼ $0$ $n | 1$ ̔ԍ蓖ĂĂ̂Ƃ܂B

͂̍ŏ̍sɁAߓ_̌ $n$ ^܂B $n$ sڂɁAeߓ_̏񂪈ȉ̌łPsɗ^܂B

$id$ $left$ $right$

$id$ ͐ߓ_̔ԍA$left$ ͍̎q̔ԍA$right$ ͉E̎q̔ԍ\܂BqȂꍇ $left$ ($right$) -1 ŗ^܂B

## o

̌Őߓ_̏o͂ĂB

node $id$: parent = $p$ , sibling = $s$ , degree = $deg$, depth = $dep$, height = $h$, $type$

$p$ ͐e̔ԍ\܂BeȂꍇ -1 Ƃ܂B$s$ ͌Z̔ԍ\܂BZȂꍇ -1 Ƃ܂B

$deg$A$dep$A$h$ ͂ꂼߓ_̎q̐A[A\܂B

$type$ ͍Aߓ_Atꂼ\ rootAinternal nodeAleaf ̂̕ꂩłBAtߓ_̏ɊYꍇ root Ƃ܂B

o͗ɂāA󔒋؂蓙̏o͌`mFĂB

• $1 \leq n \leq 25$

9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

## o͗ 1

node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf

## Ql

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.