Why are these trees the same as ordered trees, but different as binary trees
In an ordered tree, child nodes are ordered from left to right. They are not ordered with respect to the parent node (or, alternatively, you can think of the parent node to always be first). If there is only one child, there is only one child.
A binary tree has a (optional) left child and an (optional) right child. If there is only one child, it can be either the left child or the right child, and both cases are different. Also, you can think of the parent node being between the child nodes, so you can distinguish the child node that comes before the parent from the child node that comes after the parent.
There is a homomorphism between ordered trees and binary trees with the same number of nodes: i.e. each ordered tree corresponds uniquely to a binary tree. To find a binary tree that matches an ordered tree: make the left child of each node in the binary tree point to the leftmost child node in the ordered tree, and create the correct child from each node in the binary tree points to the sibling to the right of the node in the ordered tree. (It should be obvious how to change the process so that you can see that each binary tree corresponds uniquely to an ordered tree.)
Therefore, the number of binary trees with nodes is the k
same as the number of ordered tree with nodes k
.
source to share
The referenced tree of trees or planes is a rooted tree that has an ordering given for the children of each vertex. This is called a "flat tree" because ordering the children is equivalent to nesting a tree into a plane. Assuming a nesting of the rooted tree in a plane, if we fix the direction of the children (starting at root, then the first child, the second child, etc.), say counterclockwise, then the nesting gives the ordering of the children. Conversely, given an ordered tree and the traditional top-top drawing of the root, then the child nodes in the ordered tree can be drawn from left to right, resulting in an essentially unique flat nesting .
Source: http://en.wikipedia.org/wiki/Ordered_tree#ordered_tree
I hope you did it!