When to use preorder tree, postprocessing, and external binary search tree ordering strategies

Question

I recently realized that when I used BST a lot in my life, I didn’t even plan to use anything other than the Inorder crawl (so far I know and know how easy it is to adapt the program to use the pre / post-order crawl).

Having realized this, I pulled out some of my old textbooks on data structures and searched for arguments about the usefulness of preliminary and post-orders - they didn’t talk very much.

What are some examples of when to use pre-order / mail order in practice? When does this make sense, what is okay?

Answer 1

When to use the Order Tracking Strategy, In-Order and Post-Order

Before you can understand under what circumstances to use pre-order, order, and post-order for a binary tree, you need to understand exactly how each workaround strategy works. Use the following tree as an example.

Tree root 7 , leftmost node 0 , rightmost node 10 .

Bypass preview :

Summary: starts at the root ( 7 ), ends at the rightmost node ( 10 )

The sequence of passage: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Bypass in order :

Summary: starts at the leftmost node ( 0 ), ends at the rightmost node ( 10 )

The sequence of passage: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Postprocessing :

Summary: begins with the leftmost node ( 0 ), ends with the root ( 7 )

The sequence of passage: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

When to use pre-orders, orders or mail order?

The workaround strategy chosen by the programmer depends on the specific needs of the algorithm being developed. The goal is speed, so choose a strategy that brings you the nodes you need.

• If you know that you need to research the roots before checking any leaves, you select a pre-order because you will meet all the roots in front of all the leaves.

• If you know that you need to examine all the leaves in front of any nodes, you choose post-order , because you do not waste time checking the roots in the search for leaves.

• If you know that the tree has an integral sequence in the nodes, and you want to smooth the tree back to the original sequence, then you should use the in-order traversal. The tree will be flattened just as it was created. Walking in order or in order may not cancel the tree back into the sequence that was used to create it.

Recursive algorithms for order, order and post-order (C ++):

struct Node{ int data; Node *left, *right; }; void preOrderPrint(Node *root) { print(root->name); //record root if (root->left != NULL) preOrderPrint(root->left); //traverse left if exists if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists } void inOrderPrint(Node *root) { if (root.left != NULL) inOrderPrint(root->left); //traverse left if exists print(root->name); //record root if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists } void postOrderPrint(Node *root) { if (root->left != NULL) postOrderPrint(root->left); //traverse left if exists if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists print(root->name); //record root } 

Answer 2

If I just wanted to print the hierarchical tree format in a linear format, I would probably use pre-order traversal. For example:

 - ROOT - A - B - C - D - E - F - G 

Answer 3

Pre-order / In order / use after order: Simple words

Pre-order: Used to create a copy of the tree Example. If you want to create a tree replica and you need the node values ​​in the array, and when you insert these values ​​from index 0 at the end of the new tree, you get a replica

In order:: to get node values ​​in unordered order

Post-order:: if you want to remove the tree from the leaf to the root

Answer 4

There are many places where you see that this difference plays a real role.

One great thing I will point out is generating code for the compiler. Consider the statement:

 x := y + 32 

How would you generate code for this (naive, of course), to first generate code to load y into register, load 32 into register and then create a command to add two. Because something must be in the register before you manipulate it (for example, you can always do constant operands, but whatever), you must do it this way.

In general, the answers you can get to this question basically boil down to this: the difference really matters when there is some correlation between the processing of various parts of the data structure. You see this when printing elements, when you generate code (the external state matters, you can also view it as a rule, as well) or when performing other types of calculations according to a structure that includes calculations depending on the children being processed in the first place.

Answer 5

Pre- and post-order relate to recursive algorithms from top to bottom and bottom to top, respectively. If you want to write this recursive algorithm on binary trees in an iterative way, this is what you will essentially do.

Also, observe that the sequences before and after the order together completely define the tree at hand, which gives compact coding (for less sparse trees).