CHAP. 10] BINARY TREES 251
EXAMPLE 10.13 Consider again the eight data itemsA,B,C,D,E,F,G,Hin Example 10-12. Suppose
the weights represent the percentage probabilities that the items will occur. Assigning, as above, bit labels to the
edges in the Huffman tree in Fig. 10-18(b), that is, assigned 0 or 1 according as the edge points to a left child or
to a right child, we obtain the following code for the data:
A: 00 ,B: 11011 ,C: 011 ,D: 111 ,
E: 11010 ,F: 010 ,G: 10 ,H: 1100.For example, to get toEfrom the root, the path consists of a right edge, right edge, left edge, right edge, and left
edge, yielding the code 11010 forE.10.9General (Ordered Rooted) Trees Revisited
LetTbe an ordered rooted tree (Section 9.4), which is also called ageneral tree.Tmay be formally defined
as a nonempty set of elements, called nodes, such that:(1) Tcontains a distinguished elementR, called therootofT.
(2) The remaining elements ofTform an ordered collection of zero or more disjoint trees,T 1 ,T 2 ,...,Tn.
The treesT 1 ,T 2 ,...,Tnare calledsubtreesof the rootR, and the roots ofT 1 ,T 2 ,...,Tnare calledsuccessorsofR.
Terminology from family relationships, graph theory, and horticulture is used for general trees in the same
way as for binary trees. In particular, ifNis a node with successorsS 1 ,S 2 ,...,SnthenNis called theparentof
theSi, theSiare called children ofN, and theSiare called siblings of each other.
EXAMPLE 10.14 Figure 10-20(a) is a picture of a general treeTwith 13 nodes,
A, B, C, D, E, F, G, H, J, K, L, M, NUnless otherwise stated, the root of a rooted treeTis the node at the top of the diagram, and the children of a
node are ordered from left to right. Accordingly,Ais the root ofT, andAhas three children; the first childB, the
second childC, and the third childD. Observe that:
(a)Chas three children. (c) Each ofDandHhas only one child.
(b) Each ofBandKhas two children. (d) Each ofE,F,G,L,J,MandNhas no children.
The last group of nodes, those with no children, are calledterminal nodes.
Fig. 10-20