Two- vs. multi-way trees in Assignment 4.

  Are binary trees instrumental to the N-neighbor tree built by assignment 4,
  or should the number of children for each subtree be dependent on n. i.e. if
  n = 3, then should each subtree have n children starting at the root?

There is no direct relation between n and the number of children a node can
have in the tree; a word may have tens or perhaps hundreds of 3-neighbors for
example, or it may have none at all.

The code in show-tree.cc asks each tree-node two questions: "How many children
do you have?" (tree_node::child_count()) and "What is your i-th child?"
(tree_node::get_child(); skip tree_node::get_word()). As long as your
implementation of tree-node can correctly answer these two questions, you can
implement tree-nodes in whatever way you want (subject to the usual
constraints).

Using binary trees to implement multi-way trees is possible, but it is somewhat
clumsy, and Nyhoff doesn't talk about how you might do that (I won't have
lecture time for it either). If you're interested, see Section 2.3.2 in
Knuth's Art of Computer Programming, vol. 1 (Fundamental Algorithms). An
alternative is to implement multi-way trees more directly, but the tricky part
here is you can't reasonably bound the number of children.
Received on Tue Mar 14 2006 - 13:05:40 EST