• 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最后两个数运算