Virgil wrote: > In article <email@example.com>, > Tony Orlow <firstname.lastname@example.org> wrote: > >> Hi All- >> >> I have alluded to the subroot node in the binary tree, and been coy >> about it, but it appears to need some explication, so please allow me to >> lay it out in the simplest possible terms. >> >> Say we have a tree, consisting of a set of nodes, most of which have a >> single associated edge (excepting one, the root, in most schemes), such >> that we have a countable set of nodes, and thus, edges. If we associate >> each of those nodes in the countable set with an element of N as >> normally conceived, then we may start with either 0 or 1, and can number >> the nodes at each level starting with the next after the last of the >> previous level. That's pretty normal. >> >> If we make the root 0, and its children are 1 and 2, and 1's children >> are 3 and 4, and 2's are 5 and 6, and so forth, x's children are equal >> to 2x+1 and 2x+2. On the other hand, if we start with root node 1, and >> child nodes 2 and 3, etc., then node x has children 2x and 2x+1. Then >> node 2 has children 4 and 5, and 3 has 6 and 7. In the first case the >> parent of x is floor((x-1)/2), and in the second, floor(x/2). If we >> inquire as to the parent of the root, we get node -1 in the first case >> and node 0 in the second. That rather makes sense. If we look at the >> children of this subroot node, they include the root, as well as the >> subroot itself. That's an interesting...twist, or loop, as one might >> call it. >> >> In general, if we number the root node with n in N, and count up in the >> same way, starting the left side of each row with the next after the >> right side of the last row, then the children of node x are 2x-n+1 and >> 2x-n+2, and the parent of x is floor((x-1+n)/2), which is always its own >> parent. >> >> So, in conclusion, the "complete" binary tree includes not only a root >> node, but a subroot node, which is its own parent, akin to the missing >> fifth of a point on the top of the pyramid. > > If Tony wants to attach such an appendix to his trees, fine, but no one > els needs one, and Tony himself may soon need an appendectomy.
So, you have no objection? That's nice. Does it appeal to you that every node now has a parent and a leading edge, or that the number of nodes up to each level n is now exactly equal to 2^n? Those seem like nice simplifications to me. No "except for the root" or "-1" about it.