240 BINARY TREES [CHAP. 10
Fig. 10-6Furthermore, the nodeNat TREE[K] contains an empty left subtree or an empty right subtree according as 2K
or 2K+1 exceeds END or according as TREE[2*K] or TREE[ 2 ∗K+ 1 ]contains the NULL value.
The sequential representation of the binary treeTin Fig. 10-6(a) appears in Fig. 10-6(b). Observe that we
require 14 locations in the array TREE even thoughT has only 9 nodes. Generally speaking, the sequential
representation of a tree with depthdwill require an array with approximately 2delements. Accordingly, this
sequential representation is usually inefficient unless, as stated above, the binary treeT is complete or nearly
complete. For example, the treeTin Fig. 10-1(a) has 11 nodes and depth 5, which means it would require an
array with approximately 2^5 =32 elements.
10.5Traversing Binary Trees
There are three standard ways of traversing a binary treeT with rootR. These three algorithms, called
preorder,inorder, andpostorder, are as follows:
Preorder:(1) Process the rootR.
(2) Traverse the left subtree ofRin preorder.
(3) Traverse the right subtree ofRin preorder.
Inorder: (1) Traverse the left subtree ofRin inorder.
(2) Process the rootR.
(3) Traverse the right subtree ofRin inorder.
Postorder:(1) Traverse the left subtree ofRin postorder.
(2) Traverse the right subtree ofRin postorder.
(3) Process the rootR.
Observe that each algorithm contains the same three steps, and that the left subtree ofRis always traversed before
the right subtree. The difference between the algorithms is the time at which the rootRis processed. Specifically,
in the “pre” algorithm, the rootRis processed before the subtrees are traversed; in the “in” algorithm, the rootR
is processed between the traversals of the subtrees; and in the “post” algorithm, the rootRis processed after the
subtrees are traversed.
Thethreealgorithmsaresometimescalled,respectively,thenode-left-right(NLR)traversal,theleft-node-right
(LNR) traversal, and the left-right-node (LRN) traversal.