p. 409 · PDF 419

1 - 4 Tree Structure

Tree structure is a data structure for representing a one-to-many hierarchical structure where there are multiple children under one parent.

p. 410 · PDF 420

Enlarge original visual

Original source text

[Constituent elements of tree structure] 
• Node 
: This is an individual element (i.e., data) that is shown as a circle. 
• Root 
: This is the highest-level node. A tree structure has only one root. 
• Leaf 
: This is the node that does not have any lower-level node. 
• Branch : This is a line that connects to each node (including root, leaf). 
• Level 
: This is the depth of hierarchy of a tree structure. 

Source visual description

Original Tree Structure source layout. Source labels: [Constituent elements of tree structure]; • Node; : This is an individual element (i.e., data) that is shown as a circle.; • Root; : This is the highest-level node. A tree structure has only one root..

For implementing a tree structure with an array, the relation between parent node and child node is represented with a pointer (i.e., index). For example, if the tree structure shown in the figure above is represented with an array by using a pointer to parent node (parent PT), the following table is obtained. Here, Parent PT of root is 0 (not connected).

Enlarge original visual

Original source text

1 
2 
3 
4 
5 
6 
Node value 
A 
B 
C 
D 
E 
F 
Parent PT 
0 
1 
1 
3 
3 
3 

Source visual description

Original Tree Structure source layout. Source labels: Node value; A; B; C; D.

On the other hand, when a relation is represented with child nodes, it is difficult to handle if the number of child nodes is not decided. Therefore, a binary tree is used where the number of child nodes is restricted to two nodes or less. In some cases, a tree structure that has n child nodes where the number of child nodes is more than two is distinguished as n-ary tree (also known as multi-way tree or multi-branch tree). For representing a binary tree by using an array, a left pointer (left TP) that connects to the left child node and a right pointer (right PT) that connects to the right child node are used.

p. 411 · PDF 421

Enlarge original visual

Original source text

[Array representation of binary tree] 
Left PT 
Node value 
Right PT 
1
2 
A 
3 
2
4 
B 
5 
3
0 
C 
6 
4
0 
D 
0 
5
0 
E 
0 
6
0 
F 
0 

Source visual description

Original Tree Structure source layout. Source labels: [Array representation of binary tree]; Left PT; Node value; Right PT; 1.

In a binary tree where all final level leaves are left aligned, if level from root up to all leaves is equal or different by one level at most, it is specifically called a complete binary tree.

Enlarge original visual

Original source text

Figure 7-8  Examples of complete binary tree and tree that is not a complete  
binary tree 

Source visual description

The original side-by-side trees compare a complete binary tree with a tree that is not complete. Node levels and leaf depths remain visible.

NOTE: There is another definition of a complete binary tree; in other words, a complete binary tree (sometimes called a perfect binary tree) is a full binary tree in which all leaves are at the same depth.

In addition, a method of extracting node values (i.e., data) from a tree structure is called tree traversal. There are the following types of tree traversals.

p. 412 · PDF 422

Enlarge original visual

Original source text

right subtree” (pre-order traversal). 
• In-order: This extracts node values in the sequence of “left subtree → node → 
right subtree” (in-order traversal). 
• Post-order: This extracts node values in the sequence of “left subtree → right 
subtree → node” (post-order traversal). 

Source visual description

Original Tree Structure source layout. Source labels: right subtree” (pre-order traversal).; • In-order: This extracts node values in the sequence of “left subtree → node →; right subtree” (in-order traversal).; • Post-order: This extracts node values in the sequence of “left subtree → right; subtree → node” (post-order traversal)..