C++ Programming for Kids (22) Binary Trees

1. Overview of Trees

Trees are a type of non-linear data structure consisting of a set of n (n ≥ 0) finite nodes. This data set effectively describes the branching and hierarchical characteristics of data.

C++ Programming for Kids (22) Binary Trees — Trees in real life

1. Characteristics of Trees

Tree structures are widely present in real life and represent a one-to-many data relationship. For example, organizational structures, family trees, data indexes, library catalogs, computer file systems, and food chains are all tree structures.

The specific characteristics of tree structures are as follows:

Each node can have zero or more child nodes
A node without a parent is called the root node
Each non-root node has exactly one parent node
Except for the root node, each child node can be divided into multiple disjoint subtrees

By observation, it can be found that tree structures can represent not only the pointing relationships of data but also the hierarchical relationships, possessing recursive properties.

2. Terminology of Trees

Node: The basic unit of a tree (node)
Root Node: A node without a parent (also called “tree root”,root)
Child Node: A direct successor of a node
Parent Node: A direct predecessor of a node
Sibling Nodes: Nodes that share the same parent
Leaf Node: A node without child nodes
Degree: The number of child nodes a node has
Depth: The path (number of edges) from the root node to that node
Height: The path from that node to the deepest leaf node (in contrast to depth)

Height of the tree = Height of the root node

* Observation and Reflection *

1. The depth and levels of a tree are counted from the root node downwards, but depthstarts counting from 0, while levelsstart counting from 1.

Depth of the root node is 0, Depth of node a is 1, Depth of node f is 2;

Root node is level 1, Node a is level 2, Node f is level 3.

2. The height of a tree is counted from the bottom upwards,starting from 0.

In the above diagram, the height of the root node is3, not4.

2. Overview of Binary Trees

In a tree, if each node has at most two child nodes, meaning the degree of each node does not exceed 2, this tree is called a Binary Tree, abbreviated as “B Tree”.

The left and right child nodes of a binary tree are usually referred to as the left child and right child, respectively, and the corresponding subtrees are called the left subtree and right subtree.

1. Basic Forms of Binary Trees

Empty binary tree (no nodes at all)
Only the root node (only one node)
The root node has only a left subtree
The root node has only a right subtree
The root node has both a left subtree and a right subtree

2. Special Binary Trees

1. Full Binary Tree: In a binary tree, if every node except the leaf nodes has both left and right child nodes, and all leaf nodes are at the lowest level, this tree is called a full binary tree. (Note: Some textbooks do not restrict all leaf nodes to the lowest level, which I consider an imprecise definition.)

Note: The full binary trees we will discuss later are all strictly defined full binary trees.

* Observation and Reflection *

If a full binary tree has n levels, how many nodes does this tree have?

2. Complete Binary Tree: In a binary tree, if all leaf nodes at the lowest level are consecutively distributed from left to right (with no gaps in between), and removing these leaf nodes leaves a full binary tree, this tree is called a complete binary tree.

* Observation and Reflection *

(1) Is a full binary tree a complete binary tree? What is the relationship between them?

(2) If a complete binary tree has n nodes, how many levels does this tree have? What is its depth?

3. Storage of Binary Trees

The storage methods for binary trees are mainly divided into two types: Sequential Storage and Linked Storage. Each has its advantages and disadvantages, suitable for different scenarios.

1. Sequential Storage

Sequential storage uses a contiguous block of memory (usually an array) to store binary tree nodes. When storing, it starts from the first level, sequentially storing each level’s node elements from left to right into the array. (For ease of observation, the root node is stored at index 1 of the array, and index 0 is not used.)

* Observation and Reflection *

(1) What is the index of the left child node of element 1? What is the index of the right child node?

(2) What is the index of the left child node of element 3? What is the index of the right child node?

(3) What is the index of the left child node of element 5? What is the index of the right child node?

To summarize: What is the relationship between the indices of parent and child nodes?

* Observation and Reflection *

It is observed that the position of nodes reflects the parent-child relationship through array indices (subscripts).

For any node k (k is the node index):

The index of the left child node is:2k 

The index of the right child node is:2k + 1

The index of the parent node is:k / 2

Notes:

(1) For complete binary trees, sequential storage can efficiently utilize space without waste. The speed of accessing parent and child nodes through calculated indices (subscripts) is very fast.

(2) It is not friendly for non-complete binary trees: it will waste a lot of storage space.

2. Linked Storage

Linked storage is a more general and common method of storing binary trees. Each node is an object (or structure) that contains three parts:

Data Field (data): Stores the data of the node.
Left Pointer Field (left): Points to the left child node of that node.
Right Pointer Field (right): Points to the right child node of that node.

Example Program for Linked Nodes

struct node {
    int data;   // data stores the data part of the node
    // The following three variables store the indices of the parent node, left, and right child nodes
    int parent, lchild, rchild;
};
node n[100];    // Declare an array for linked storage

Whether it is a complete binary tree or a non-complete binary tree, linked storage is applicable.

4. Traversal of Binary Trees

There are various ways to traverse binary trees, which is also the most frequently performed operation on tree structures.

1. Level Order Traversal

Similar to the sequential storage method, it starts from the first level and traverses down level by level, with each level traversed from left to right.

This traversal method is relatively simple; we will focus on the following three traversal methods.

2. Pre-order Traversal

Pre-order Traversal: First traverse the root node, then the left subtree, and finally the right subtree. (Also known as “pre-root order”)

Referring to the example diagram, starting from the top (root): (first middle, then both sides)

First, traverse the root node and write down A. The traversal result of the left subtree is written after A, and the traversal result of the right subtree is written after the left subtree.
The root node of the left subtree is B, write down B, then traverse the left and right subtrees of B, with the left subtree’s traversal result written after B and the right subtree’s traversal result written after the left subtree.
Following this recursive method, the traversal result of the left subtree of A is: B, D, H, E;
Using the same method, the traversal result of the right subtree of A is: C, F, G, I.
Combining all parts, the final pre-order traversal result of the example binary tree is: A, B, D, H, E, C, F, G, I.

3. In-order Traversal

In-order Traversal: First traverse the left subtree, then the root node, and finally the right subtree. (Also known as “in-root order”)

Referring to the example diagram, starting from the bottom (left subtree): (from left to right)

The leftmost non-leaf node at the bottom has no left subtree, only traverse the root node D and the right node H.
Continue recursively, traverse the root node of the upper tree B and the right subtree E.
Moving up one level, traverse the root node of the tree A.
At this point, the left subtree and the root node have been traversed, now traverse the right subtree of the root node.
Since node C has a left subtree, first traverse the left subtree F, then traverse node C.
Next, traverse the right subtree of C, which has only one left leaf node, resulting in the traversal: I, G.
Combining the traversal results, the final in-order traversal result is: D, H, B, E, A, F, C, I, G.

4. Post-order Traversal

Post-order Traversal: First traverse the left subtree, then the right subtree, and finally the root node. (Also known as “post-root order”)

Referring to the example diagram, starting from the bottom (left subtree): (first both sides, then middle)

The leftmost non-leaf node at the bottom has no left subtree, only traverse the right node H and the root node D.
Continue recursively, traverse the right subtree of the upper tree E and the root node B.
At this point, the left subtree of the root node has been traversed, now traverse the right subtree of the root node.
Since node C has a left subtree, first traverse the left subtree F, then traverse the right subtree of node C.
C‘s right subtree has only one left leaf node, resulting in the traversal: I, G.
Then traverse the root node of the right subtree C.
Finally, traverse the root node A.
Combining the traversal results, the final post-order traversal result is: H, D, E, B, F, I, G, C, A.

* Observation and Reflection *

Find several different binary trees and try to write their pre-order, in-order, and post-order traversals.

Example Problem: Traversing a Binary Tree

Given the post-order traversal sequence of a binary tree as D G J H E B I F C A and the in-order traversal sequence as D B G E H J A C I F, find the pre-order traversal sequence.

[ Thought Process ]

First, restore the binary tree based on the post-order and in-order traversal sequences
Then perform pre-order traversal on the binary tree

[ Specific Steps ]

Step 1: Establish the root node and left and right subtrees

From the post-order traversal sequence D G J H E B I F C A, we can see that the root node is A;
Thus, the in-order traversal sequence D B G E H JAC I F is divided into left and right parts by the A node, where the left subtree is D B G E H J and the right subtree is C I F.

Step 2: Restore the left subtree

The post-order traversal sequence of the left subtree is D G J H E B, so the root node of the left subtree is B;
The in-order traversal sequence of the left subtree is DBG E H J is divided into left and right parts by the B node, where the left subtree is D and the right subtree is G E H J.

Recursively continue to restore the entire left subtree:

Since the B node’s left subtree has only one element, it is directly attached to the left child of B;
B node’s right subtree post-order traversal sequence is G J H E, so the root node is E, and the in-order traversal sequence GEH J is divided into left and right parts by the E node, where the left subtree is G and the right subtree is H J;
Continue restoring the right subtree of E, whose post-order traversal sequence is J H, so the root node is H, and the in-order traversal sequence HJ is divided into left and right parts, where the left subtree is an empty tree, and the right subtree has only one element J, so it is directly attached to the right child of H, completing the restoration of the entire left subtree.

Step 3: Restore the right subtree

The post-order traversal sequence of the right subtree is I F C, so the root node of the right subtree is C;
The in-order traversal sequence of the right subtree is CI F is divided into left and right parts by the B node, where the left subtree is an empty tree, and the right subtree is I F.
C node’s right subtree post-order traversal sequence is I F, so the root node is F;
C node’s right subtree in-order traversal sequence is IF is divided into left and right parts, where the left subtree has only one element, directly attached to the left child, and the right subtree is an empty tree, completing the restoration of the entire binary tree.

Step 4: Pre-order Traverse the Binary Tree

Performing pre-order traversal on the above binary tree results in:A B D E G H J C F I.

* Observation and Reflection *

(1) Given the pre-order and in-order traversal sequences of a binary tree, can the binary tree be restored?

(2) Given the pre-order and post-order traversal sequences of a binary tree, can the binary tree be restored?

Exercises: Traversing Binary Trees

[ Question 1 ]

Given the pre-order traversal sequence of a binary tree as A B D E C F H J I G and the in-order traversal sequence as D B E A J H F I C G, find the post-order traversal sequence.

[ Question 2 ]

Given the pre-order traversal sequence of a binary tree as A B D E C F and the in-order traversal sequence as D B E A F C, find the post-order traversal sequence.

[ Question 3 ]

Given the in-order traversal sequence of a binary tree as 6 5 4 1 9 3 0 and the post-order traversal sequence as 6 5 9 1 0 3 4, find the pre-order traversal sequence.

[ Question 4 ]

Given the in-order traversal sequence of a binary tree as C B A D E and the post-order traversal sequence as C B E D A, find the pre-order traversal sequence.

< This lesson ends here >

Previous Recommendations

C++ Programming for Kids (21) Stacks and Queues

C++ Programming for Kids (20) Prefix Sums and Differences

C++ Programming for Kids (19) Algorithm Complexity

C++ Programming for Kids (18) Bitwise Operations

Scratch Version of “Gold Miner” (Paid)

J30-01 Knapsack Problem (Dynamic Programming)

Lazy Eye Training Mini Game – Fox Doodle(Paid)

Plants vs. Zombies(Paid)

Contra 2 – Monster Fighting

Lazy Eye Training Mini Game – Find the Text(Paid)

Scan the QR code to get