Unrooted binary tree: Difference between revisions

Revision as of 02:12, 17 November 2012

Revision as of 12:17, 20 April 2014

Line 11:

==Related structures==

===Rooted binary trees===

{{Main|Rooted binary tree}}

An unrooted binary tree ''T'' may be transformed into a full rooted [[binary tree]] (that is, a rooted tree in which each non-leaf node has exactly two children) by choosing a ''root edge'' ''e'' of ''T'', placing a new root node in the middle of ''e'', and directing every edge of the resulting subdivided tree away from the root node. Conversely, any full rooted binary tree may be transformed into an unrooted binary tree by removing the root node, replacing the path between its two children by a single undirected edge, and suppressing the orientation of the remaining edges in the graph. For this reason, there are exactly 2''n''&nbsp;&minus;3 times as many full rooted binary trees with ''n'' leaves as there are unrooted binary trees with ''n'' leaves.<ref name="f84"/>