CODEWITHSUNDEEP
algorithmdata-structurestreebinary-tree
jantristanmilan
jantristanmilan

Reputation: 4368

Why are these trees the same as ordered trees but different as binary trees

I don' get it? Shouldn't they be different as ordered trees too? because the ordering is different

enter image description here

Upvotes: 3

Views: 392

Answers (2)

rici
rici

Reputation: 241931

In an ordered tree, child nodes are ordered from left to right. They are not ordered with respect to their parent node (or, alternatively, you could think of the parent node always coming first). If there is only one child, there is only one child.

In a binary tree, there is an (optional) left child and an (optional) right child. If there is only one child, it could be either a left child or a right child, and the two cases are different. Alternatively, you can think of the parent node coming between the child nodes, so you can distinguish a child node which comes before the parent from a child node which comes after the parent.

There is a homomorphism between ordered trees and binary trees with the same number of nodes: that is, every ordered tree corresponds uniquely to a binary tree. To find the binary tree corresponding to a ordered tree: make the left child of each node in the binary tree point to the leftmost child of the node in the ordered tree, and make the right child of each node in the binary tree point to the sibling to the right of the node in the ordered tree. (It should be obvious how to reverse the process, so that you can see that every binary tree corresponds uniquely to an ordered tree.)

Consequently, the number of binary trees with k nodes is the same as the number of ordered tree with k nodes.

Upvotes: 2

user1657017
user1657017

Reputation:

An ordered tree or plane tree is a rooted tree for which an ordering is specified for the children of each vertex. This is called a "plane tree" because an ordering of the children is equivalent to an embedding of the tree in the plane.Given an embedding of a rooted tree in the plane, if one fixes a direction of children (starting from root, then first child, second child, etc.), say counterclockwise, then an embedding gives an ordering of the children. Conversely, given an ordered tree, and conventionally draw the root at the top, then the child nodes in an ordered tree can be drawn left-to-right, yielding an essentially unique planar embedding.

Source:http://en.wikipedia.org/wiki/Ordered_tree#ordered_tree

I hope u got it!!

Upvotes: 0

Related Questions