
- Height / depth = number of edges between root $\leftrightarrow$ current node
- $n$-ary tree: each internal vertex has $\le m$ children
- $n=2$: binary tree
- $n=3$: ternary tree
- full $n$-ary tree: every internal vertex has exactly $m$ children
Theorems
- A tree with $n$ vertices has $n-1$ edges
- A full $n$-ary tree with $i$ internal vertices has $n=mi+1$ vertices
Ordered Tree
- Every internal vertex’s children is ordered
Tree Traversal
- Preorder 根左右
- Postorder 左右根
- Inorder 左根右
Arithmetic Expression
- Infix form
- $(1+2)\div3$
- Construction: Apply inorder traversal
- Evaluation: 正常计算
- Prefix form
- $\div+1\ 2\ 3$
- Construction: Apply preorder traversal
- Evaluation: 从右到左入栈,遇符号pop最后两个数运算
- Postfix form
- $1\ 2+3\ \div$
- Construction: Apply postorder traversal
- Evaluation: 从左到右入栈, 遇符号pop最后两个数运算