448,470 Members | 966 Online
Need help? Post your question and get tips & solutions from a community of 448,470 IT Pros & Developers. It's quick & easy.

# Binary trees

 P: n/a - with 10 nodes, give one example of an unbalanced binary tree and one example of a balanced binary tree - what is the advantage of having a balanced binary tree over an unbalanced tree? - number your nodes, then give the order in which nodes will be visited by a depth-first-search - explain the differences between traversing the tree pre-order, in- order and post-order May 4 '07 #1
8 Replies

 P: n/a In article <11**********************@h2g2000hsg.googlegroups. com>,

 P: n/a n.******@gmail.com wrote: - with 10 nodes, give one example of an unbalanced binary tree and one example of a balanced binary tree Unbalanced tree: AB,C'K:D'EH:FJ:G: (notation adapted from Knuth, TAOCP 2.3.3 equation 3) To balance the tree, put another one on the other pan. - what is the advantage of having a balanced binary tree over an unbalanced tree? Easier access to firewood. When the next high wind topples the unbalanced tree, the balanced tree that's over it will fall at the same time and save you the work of cutting it down. - number your nodes, then give the order in which nodes will be visited by a depth-first-search Numbers: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 Depth-first order: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 - explain the differences between traversing the tree pre-order, in- order and post-order With pre-order, the pizza is ready when you arrive at the shop and you needn't wait. With in-order, you may need to pay a restaurant tax to eat the pizza on the premises. With post- order, the pizza reaches you three to five business days later and is unpalatable. -- Eric Sosman es*****@acm-dot-org.invalid May 4 '07 #3

 P: n/a n.******@gmail.com wrote: - with 10 nodes, give one example of an unbalanced binary tree and one example of a balanced binary tree - what is the advantage of having a balanced binary tree over an unbalanced tree? - number your nodes, then give the order in which nodes will be visited by a depth-first-search - explain the differences between traversing the tree pre-order, in- order and post-order I think you should have posted to comp.lazy.domyhomework, since (a) this is homework; having someone else do it for you misses the point; (b) it's off-topic, since it isn't about C at all. -- Not A Number, A Free Hedgehog Meaning precedes definition. May 4 '07 #4

 P: n/a n.******@gmail.com wrote: - with 10 nodes, give one example of an unbalanced binary tree and one example of a balanced binary tree http://en.wikipedia.org/wiki/Binary_tree - what is the advantage of having a balanced binary tree over an unbalanced tree? A balanced tree will not fall over in a storm, as long as the wind blows evenly from all directions. - number your nodes, then give the order in which nodes will be visited by a depth-first-search http://en.wikipedia.org/wiki/Binary_...th-first_order - explain the differences between traversing the tree pre-order, in- order and post-order http://en.wikipedia.org/wiki/Binary_...rder_traversal. -- clvrmnky Direct replies will be blacklisted. Replace "spamtrap" with my name to contact me directly. May 4 '07 #5

 P: n/a In article <6N****************@nnrp.ca.mci.com!nnrp1.uunet.ca >, Clever Monkey n.******@gmail.com wrote: > - what is the advantage of having a balanced binary tree over anunbalanced tree? A balanced tree will not fall over in a storm, as long as the wind blowsevenly from all directions. But the wind in most storms doesn't blow evenly from all directions. If you're going for storm tolerance, you really want an unbalanced tree, but the problem with that is that every time the wind changes you have to go out and re-unbalance it for the new wind direction. dave -- Dave Vandervies dj******@csclub.uwaterloo.ca And there was nothing insulting about it. Some people would rather take being called a ``normal person'' as an insult. --Nils Goesche in comp.lang.c May 4 '07 #6

 P: n/a In article , Eric Sosman n.******@gmail.com wrote: > - with 10 nodes, give one example of an unbalanced binary tree andone example of a balanced binary tree Unbalanced tree: AB,C'K:D'EH:FJ:G: (notation adaptedfrom Knuth, TAOCP 2.3.3 equation 3) Unless you have a different edition than I do (3rd), I think you meant equation 4. dave -- Dave Vandervies dj******@csclub.uwaterloo.ca The DS 9000 is a conforming implementation. The DS 9001 is so cleverly designed that experts can't agree whether it is conforming or not! --Christian Bau in comp.lang.c May 4 '07 #7

 P: n/a Dave Vandervies wrote On 05/04/07 16:08,: In article , Eric Sosman >n.******@gmail.com wrote: >> - with 10 nodes, give one example of an unbalanced binary tree andone example of a balanced binary tree Unbalanced tree: AB,C'K:D'EH:FJ:G: (notation adapted >>from Knuth, TAOCP 2.3.3 equation 3) Unless you have a different edition than I do (3rd), I think you meant equation 4. The renumbering was part of the adaptation. -- Er*********@sun.com May 4 '07 #8

 P: n/a Dave Vandervies wrote: In article <6N****************@nnrp.ca.mci.com!nnrp1.uunet.ca >, Clever Monkey n.******@gmail.com wrote: >> - what is the advantage of having a balanced binary tree over anunbalanced tree? A balanced tree will not fall over in a storm, as long as the wind blowsevenly from all directions. But the wind in most storms doesn't blow evenly from all directions. If you're going for storm tolerance, you really want an unbalanced tree, but the problem with that is that every time the wind changes you have to go out and re-unbalance it for the new wind direction. So true. I think I'm barking up the wrong tree here. We better leaf this alone for while, or we might end up branching off into the wrong direction. If I twig onto anything else, I'll let you know, but I think this conversation will not bear any new fruit. Either that, or I'm the fall guy and can't see the tree for the forest. -- clvrmnky Direct replies will be blacklisted. Replace "spamtrap" with my name to contact me directly. May 4 '07 #9

### This discussion thread is closed

Replies have been disabled for this discussion.