Revision as of 16:25, 23 March 2022 edit Walrusmcd (talk \| contribs) 5 edits No edit summary ← Previous edit		Revision as of 08:36, 24 March 2022 edit undo Jochen Burghardt (talk \| contribs) Extended confirmed users 24,305 edits →Applications: rm confusing text written in unencyclopedic style; as far as there was truth in the paragraph, it becomes more clear from the copy / delete examples Next edit →
Line 99: Post-order traversal can generate a postfix representation ([[Reverse Polish notation]]) of a binary tree. Traversing the depicted arithmetic expression in post-order yields "''A'' ''B'' ''C'' − * ''D'' ''E'' + +"; the latter can easily be transformed into [[machine code]] to evaluate the expression by a [[stack machine]]. Postorder traversal is also used to delete the tree. Each node is freed after freeing its children. In-order traversal is very commonly used on [[binary search tree]]s because it returns values from the underlying set in order, according to the comparator that set up the binary search tree. In general, if you know you need to explore the roots before inspecting any leaves, you pick pre-order because you will encounter all the roots before all of the leaves. If you know you need to explore all the leaves before any nodes, you select post-order because you don't waste any time inspecting roots in search for leaves. If you know that the tree has an inherent sequence in the nodes, and you want to flatten the tree back into its original sequence, than an in-order traversal should be used. ==Implementations==

Tree traversal: Difference between revisions