Sách "A simple bijection between binary trees and colored ternary trees"

T with p internal vertices such that the sum of all the color numbers of T is nư 2p. Define
Tn =
S
[n/2]
p=0
Tn,p. Let Bn denote the set of complete binary trees with n internal vertices.
For any B ∈ Bn, let P = v1v2 · · · vk be a path of length k of B (viewed from the root of
B). P is called a R-path, if (1) vi
is the right child of viư 1 for 2 6 i 6 k and (2) the left
child of vi is a leaf for 1 6 i 6 k. In addition, P is called a maximal R-path if there exists
no vertex u such that uP or P u forms a R-path. P is called an L-path, if k > 2 and vi is
the left child of viư 1 for 2 6 i 6 k. P is called a maximal L-path if there exists no vertex
u such that uP or P u forms an L-path. Clearly, a leaf can never be R-path or L-path.
Note that the definition of L-path is different from that of R-path. Hence, if P is a
maximal R-path, then (1) the right child u of vk must either be a leaf or the left child of
u is not a leaf; (2) v1 must either be a left child of its father (if exists) or the father of v1
has a left child which is not a leaf. If P is a maximal L-path, then (1) vk must be a leaf
which is also a left child of vkư 1; (2) v1 must be the right child of its father (if exists).