Hi I have read a lot and I could not get what does ordered tree mean? would you explain me with some examples thanks!
A:
An ordered tree contains nodes (elements) which can be ordered according to a specific criteria. Often it is a binary tree, i.e. nodes have at most two children (conveniently called the left and right child). The tree is ordered when at every node, all elements in its left child tree are smaller than elements in its right subtree (and if the non-leaf node itself contains an element, it is greater than the elements in the left subtree and less than the elements in the right subtree).
(provided all elements in the tree are unique - if not, then some "greater than" / "less than" above becomes "greater or equal to" / "less or equal to".)
Simple example:
4
/ \
2 6
/ \ / \
1 3 5 7
Here is a more detailed explanation.
Péter Török
2010-06-25 08:18:10
you mean that for example the left child of a parent should be less than a right child of that parent?
2010-06-25 09:24:37
@matin1234, exactly. However, not just the direct child, but _all_ nodes within the left subtree. As in the example above, the elements 1, 2 and 3 in the left subtree all are less than their parent node 4, and all the elements in the right subtree.
Péter Török
2010-06-25 09:41:11
aha,so for example we know that heap are like a complete binary tree and binary tree is an ordered tree that must have this situation that you have written above ,please refer to this link and would you mind help me that why that example is not a max heap ? maybe because the right child of 28 is less than left child!link :http://stackoverflow.com/questions/3116858/max-heap-and-binary-tree
2010-06-25 09:49:20
@matin1234, all answerers to that question say that it __is__ a max heap, and I have to agree with them. However, it is not an _ordered_ tree, for the reason you state above.
Péter Török
2010-06-25 10:06:26
thanks for your answer :)
2010-06-25 10:24:07