-
May 20th, 2012, 12:46 PM
#1
question about binary tree
hello
i solve this question but am not sure if it is correct
can someone checked it out for me
thanks i appreciate it
http://tinypic.com/r/66vjbq/6
-
May 20th, 2012, 05:10 PM
#2
Re: question about binary tree
Well, since it's against the policy of the forums to simply hand out answers, I can tell you how to check it yourself - by reminding you what each of the definitions mean:
- The height (a.k.a. depth) of the binary tree (or any rooted tree) is the length of the path from the root to the deepest node in the tree. So, you essentially count the edges, or alternatively, if you consider the nodes as being on different levels, you start counting the levels from 0 (so, a tree with only the root has the height of 0).
- The task specifically says that you should find the nodes with a left sub-tree, and with no right sub-tree. A sub-tree is anything that's linked to a node - it could be a single child node, or it could be a rooted hierarchy of nodes.
Answer this question: do leaf nodes have a sub-tree attached to them? Much less a left sub-tree? Easy answer, right? So, I suppose that one's there by accident.
Next, make sure all the nodes you listed satisfy the condition.
- Finally, the in-order traversal:
left sub-tree ---> root ---> right sub-tree
Or rather:
left sub-tree (if it exists) ---> root ---> right sub-tree (if it exists)
You can use some visual tools to help you. For example, I found this here.
These common traversals can be represented as a single algorithm by assuming that we visit each node three times. An Euler tour is a walk around the binary tree where each edge is treated as a wall, which you cannot cross. In this walk each node will be visited either on the left, or under the below, or on the right. The Euler tour in which we visit nodes on the left produces a preorder traversal. When we visit nodes from the below, we get an inorder traversal. And when we visit nodes on the right, we get a postorder traversal.
So, basically, draw a path around the tree, and see in what order you "walk by" each node's bottom wall. In the example above, it's H, A, C, D, J, G, E, F, B, K.
P.S. Make sure to re-check each of the answers, all of them have an error. Some errors are not too bad, but some are important.
Last edited by TheGreatCthulhu; May 20th, 2012 at 05:15 PM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|