Menu
Does the term "inorder traversal" have a well-defined meaning for trees wider than binary trees, or are "pre-" and "post-" order the only type of DFS that makes sense? I mean with n>2 children per-node.
I guess for n that is even it might mean going to the 'root' after n/2 children, but is this ever used like this? And what about odd n?
910
In-order Traversal In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself. If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.
A tree can be binary on non-binary. In a binary tree, each node has at most two — left and right — children. A node in a non-binary tree can have more children. Traversing a tree means going through every node in it.
3. Inorder Traversal. An inorder traversal first visits the left child (including its entire subtree), then visits the node, and finally visits the right child (including its entire subtree). The binary search tree makes use of this traversal to print all nodes in ascending order of value.
A non-binary, or multifurcating, tree is a tree in which at least one node has more than two children. Such nodes are referred to as polytomies, or non-binary nodes. A polytomy can have several meanings [9]. In Notung, polytomies are represented as vertical edges with more than two children.
The inorder traversal will continue to be well defined only if you explicitly partition the children set into left children and right children.
To see this, note that the inorder traversal actually enumerates nodes in the order in which they will appear if we flatten the tree (or equivalently, the order in which the nodes will appear if we gaze over the tree starting from left).
Thus, for an n-ary tree, you will process the left children set first, followed by the parent and the right children set.
For example, consider the following tree : 
If we define the set of left children to be the first 2 child nodes from the left, and the set of right children as the single last node, we will get the following inorder traversal :
14, 15, 5, 16, 17, 18, 6, 19, 2, 20, 21, 7, 8, 9, 3, 10, 1, 11, 12, 4, 13
The method of choosing the left and right children set will depend on the problem in hand.
193
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
