Một vài định nghĩa

• Root: unique node without a parent
• Internal node: node with at least one child (A, B, C, F)
• External (leaf) node: node without children (E, I, J, K, G, H, D)
• Ancestors of a node: parent, grandparent, great-grandparent, …
• Descendants of a node: child, grandchild, great-grandchild, etc.
• Level of a node: The level of the root is 1. If a father has level i then its children has level i+1.
• Height of a tree: là level tối đa của cây đó, nghĩa là một cây chỉ có 1 node thì height = 1, empty tree thì height = 0.
• Height of a node: là độ cao của sub-tree có root là node đó.

Cách hình thức để traversal (in ra cây ở dạng danh sách)

Pre-order (Center-Left-Right)

Node ở giữa sẽ được in trước, song đến sub-tree ở bên trái, song đến sub-tree ở bên phải.

Kết quả ở hình trên khi in ra thành danh sách sẽ là:

1, 2, 3, 4, 5, 6, 7, 8, 9

In-order (Left-Center-Right)

Kết quả ở hình trên khi in ra thành danh sách sẽ là:

3, 2, 4, 1, 6, 5, 7, 8, 9

Post-order (Left-Right-Center)