Highlighted text? Practice this concept. Highlighted passages and figures open related questions.
Practice related questions (9)Progress & bookmarks
Current section
1-4-1 Practical Use of Binary Tree
p. 412
Practice this section 9 linked exam questions with default filters
Progress
Not marked complete
Related questions in this lesson 12
Reverse Polish notation from post-order traversal7Binary search tree ordering3Heap sort by root extraction2Operator-tree grouping rules2p. 412 · PDF 422
1-4-1 Practical Use of Binary Tree
(1) Notation of expressions with binary trees
Example: Represent the expression “a×(b+c)” in the reverse Polish notation.
p. 413 · PDF 423
Original source text
(1) Represent the expression with binary tree.
1) Create a binary tree where the node is arithmetic operator “×” which is
executed later.
2) Create a binary tree where “b+c” is the right subtree; in other words,
arithmetic operator “+” is the node, and then, “b” and “c” are the left child
and the right child respectively.
(2) Extract node values with depth-first search (i.e., post-order traversal).
Reverse Polish notation: a b c + ×
Source visual description
Original Practical Use of Binary Tree source layout. Source labels: (1) Represent the expression with binary tree.; 1) Create a binary tree where the node is arithmetic operator “×” which is; executed later.; 2) Create a binary tree where “b+c” is the right subtree; in other words,; arithmetic operator “+” is the node, and then, “b” and “c” are the left child.
(2) Binary search tree
Original source text
Left subtree
Node
Right subtree
18, 34, 41
50
72, 83
18
34
41
–
72
83
Note: In all nodes,
Left subtree < Node < Right subtree
Figure 7-9 Example of binary search tree
Source visual description
The original binary search tree is accompanied by a Left subtree, Node and Right subtree value table.
[Data searching procedure in binary search tree]
1) Let the root be the first search node.
2) Repeat the following process until search nodes are exhausted or the target value is found:
- • Compare node value of the search node with target value.
→ “Node value>Target value”: Let the left child node be the next search node. → “Node value<Target value”: Let the right child node be the next search node.
p. 414 · PDF 424
(3) Heap
Heap is a complete binary tree where a constant magnitude relation holds true between the parent node and the corresponding child nodes. Magnitude relation of only the child and parent is constant. There is no constant magnitude relation between sister nodes. (Like a binary search tree or heap, a tree structure with a constant order relation between nodes is called an ordered tree).
Original source text
Figure 7-10 Examples of a heap and a non-heap
Source visual description
The original heap and non-heap examples retain the node values and the marked location where the magnitude relation differs.
Original source text
Figure 7-11 Image of heap sort
Source visual description
The original heap-sort stages transfer extracted tree values into the adjacent array.
Section progress
Original chapter exercises
Original chapter exercises →New FE Textbook Vol.1 · IT Fundamentals · First Edition, April 2015