Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 11: Q11RE (page 805)

a. Explain how to use preorder, in-order, and post-order traversals to find the pre-fix, in-fix, and post-fix forms of an arithmetic expression.

b. Draw the ordered rooted tree that represents \({\bf{((x - 3) + ((x/4) + (x - y)}} \uparrow {\bf{3))}}\)

c. Find the pre-fix and post-fix forms of the expression in part \(\left( {\bf{b}} \right)\).

Short Answer

Expert verified

a. The pre-fix form of an arithmetic expression is the pre-order traversal of the tree representing the arithmetic expression.

The in-fix form of an arithmetic expression is the in-order traversal of the tree representing the arithmetic expression.

The post-fix form of an arithmetic expression is the post-order traversal of the tree representing the arithmetic expression.

b. Ordered rooted tree is

c. Pre-fix form:\({\bf{ + - x3 + /x4}} \uparrow {\bf{ - xy3}}\)

Post-fix form:\({\bf{x3 - x4/xy - 3}} \uparrow {\bf{ + + }}\)

Step by step solution

01

Usage of pre-order, in-order and post-order

The pre-order traversal of a tree \({\bf{T}}\) with root \({\bf{r}}\) begins by visiting \({\bf{r}}\), then the most left subtree at \({\bf{r}}\) in pre-order, then the second most left subtree at \({\bf{r}}\) in pre-order, and so on.

The in-order traversal of a tree \({\bf{T}}\) with root \({\bf{r}}\) begins by visiting the left most sub tree in in-order, then visits \({\bf{r}}\), then the second left most subtree at \({\bf{r}}\) in in-order, then the third most left subtree at \({\bf{r}}\) in in-order, and so on.

The post-order traversal of a tree \({\bf{T}}\) with root \({\bf{r}}\) begins by visiting the left most subtree of \({\bf{r}}\) in post-order, then the second left most subtree of \({\bf{r}}\) in post-order, and so on until the right most subtree of \({\bf{r}}\) in post-order and finally, we then visit the root \({\bf{r}}\).

02

Prefix form

The pre-fix form of an arithmetic expression is the pre-order traversal of the tree representing the arithmetic expression.

The in-fix form of an arithmetic expression is the in-order traversal of the tree representing the arithmetic expression.

The post-fix form of an arithmetic expression is the post-order traversal of the tree representing the arithmetic expression.

03

Rooted tree

\({\bf{((x - 3) + ((x/4) + (x - y)}} \uparrow {\bf{3))}}\)

The last operation to occur in the given expression is the addition of \(\left( {{\bf{x - 3}}} \right)\) and \({\bf{((x/4) + (x - y)}} \uparrow {\bf{3)}}\). The root of the tree should then be \({\bf{ + }}\). The left child of the tree will be the subtree representing \(\left( {{\bf{x - 3}}} \right)\) and the right child of the will be the subtree representing \({\bf{((x/4) + (x - y)}} \uparrow {\bf{3)}}\).

Similarly, the subtree representing an expression will contain the last operator to occur in the expression as the root and the expression on either side of the operator as their children.

Following these guidelines, you should then obtain the following graph:

04

Step 4:Prefix and postfix form

The pre-fix form of the expression in part \(\left( {\bf{b}} \right)\) is the pre-order traversal of the tree in part \(\left( {\bf{b}} \right)\).

We start from the root, then state the left child of the previous vertex until the vertex has no child, then we move on to its sibling and repeat the procedure. If all siblings of a vertex have been listed, then move on to the parent of the last vertex until you obtain an unlisted sibling. Repeat until all vertices have been listed.

\({\bf{ + - x3 + /x4}} \uparrow {\bf{ - xy3}}\)

The post-fix form of the expression in part \(\left( {\bf{b}} \right)\) is the pre-order traversal of the tree in part \(\left( {\bf{b}} \right)\).

We start from the root and move on the left child if possible. If the vertex has no child, then list the vertex. Move on to an unlisted sibling if possible and move on to the left child if possible until you again arrive at a vertex with no children. If a vertex was listed and if the vertex has no longer any unlisted siblings, then then list its parent and repeat the procedure for the parent.

\({\bf{x3 - x4/xy - 3}} \uparrow {\bf{ + + }}\)

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Sollin's algorithm produces a minimum spanning tree from a connected weighted simple graph \({\bf{G = (V,E)}}\) by successively adding groups of edges. Suppose that the vertices in \({\bf{V}}\) are ordered. This produces an ordering of the edges where \({\bf{\{ }}{{\bf{u}}_{\bf{0}}}{\bf{,}}{{\bf{v}}_{\bf{0}}}{\bf{\} }}\) precedes \({\bf{\{ }}{{\bf{u}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{1}}}{\bf{\} }}\) if \({{\bf{u}}_{\bf{0}}}\) precedes \({{\bf{u}}_{\bf{1}}}\) or if \({{\bf{u}}_{\bf{0}}}{\bf{ = }}{{\bf{u}}_{\bf{1}}}\) and \({{\bf{v}}_{\bf{0}}}\) precedes \({{\bf{v}}_{\bf{1}}}\). The algorithm begins by simultaneously choosing the edge of least weight incident to each vertex. The first edge in the ordering is taken in the case of ties. This produces a graph with no simple circuits, that is, a forest of trees (Exercise \({\bf{24}}\) asks for a proof of this fact). Next, simultaneously choose for each tree in the forest the shortest edge between a vertex in this tree and a vertex in a different tree. Again the first edge in the ordering is chosen in the case of ties. (This produces a graph with no simple circuits containing fewer trees than were present before this step; see Exercise \({\bf{24}}\).) Continue the process of simultaneously adding edges connecting trees until \({\bf{n - 1}}\) edges have been chosen. At this stage a minimum spanning tree has been constructed.

Show that the addition of edges at each stage of Sollin’s algorithm produces a forest.

Give an upper bound and a lower bound for the height of a B-tree of degree k with n leaves.

Explain how to use breadth-first search to find the length of a shortest path between two vertices in an undirected graph.

a. Explain how backtracking can be used to determine whether a simple graph can be colored using \(n\) colors.

b. Show, with an example, how backtracking can be used to show that a graph with a chromatic number equal to \({\bf{4}}\) cannot be colored with three colors, but can be colored with four colors.

Show that a simple graph is a tree if and only if it contains no simple circuits and the addition of an edge connecting two nonadjacent vertices produces a new graph that has exactly one simple circuit (where circuits that contain the same edges are not considered different).
See all solutions

Recommended explanations on Math Textbooks

Discrete Mathematics

Read Explanation

Applied Mathematics

Read Explanation

Geometry

Read Explanation

Logic and Functions

Read Explanation

Pure Maths

Read Explanation

Probability and Statistics

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free