A binary tree is a tree, where every branch has (potentially) exactly two sub-br

Question

A binary tree is a tree, where every branch has (potentially) exactly two sub-branches. If we draw a binary tree on the screen using characters, we might have 1 branch on the top row, 2 on the next row, then 4, 8, 16, and so on. You can draw this tree using a recursive makeBranches () function with arguments left and right, which are the endpoints of a horizontal range. When you first enter the routine, left is 0 and right is the number of characters (including dashes) in all the lines, minus 1. You draw an X in the center of this range. Then the function calls itself twice: once for the left half of the range and once for the right half. Return when the range gets too small. You will probably want to put all the dashes and Xs into an array and display the array all at once, perhaps with a display() function. Write a main() program to draw the tree by calling makeBranches() and display(). Allow main() to determine the line length of the display (32, 64, or whatever). Ensure that the array that holds the characters for display is no larger than it needs to be.

Explanation / Answer

ANS In my tree if you pick yes that means go to the left branch.. no then means go to the right branch. It's important to keep which side your affirmatives and negatives are on! This also means you can extrapolate that branches are for questions and leaves are for answers. The tree updates itself so if the application is on a leaf and guesses, but FAILS, the question the user provides replace of the current leaf, the old value becomes the left child and the user's answer becomes the right! I also rely on some end game user feed back. Since I am too lazy to sit around entering questions and possible answers - I only feel up for one question. If it turns out that answer is not right then prompt the user for input to further define things! That's right - with each start of the game - if my program fails to guess right it gets the answer from the user and asks them to provide a question that differentiates between the failed guess and the user's answer. Sure the first hundred or so games might not be exciting but once the structure fleshes out looks spooky smart! Also, for you math buffs out there have you thought about the number of nodes I could have? I start out with one root note (1). Then that node can have two children (2). Each of those can have two children (4).. and those can have a pair of children (8).. that looks like a series! To get how many nodes are on a row it looks like: 2^n will do! n is what level you are want to check (and assuming the root is level 0). That means we can extrapolate that each layer is a question and if we wanted to see how many answers we could house that would be 2^20! (See we start counting at 0 and that last row of answer leaves are sort of questions.. so you have twenty proper questions before you ask "is it X". A quick calculation says 2^20 is 1,048,576 possible answers! Now if you are curious the total number of nodes in this whole structure could be (playing 20 questions) - that is a (2^(n+1))-1. (Trust me on this). That is two to the the power of n minus 1... all of that minus one. n is the level.. and again the root is level 0. This means at level 20 we have a total of: (2^(20+1))-1 or 2,097,151 nodes! Just a bit

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.