Author |
Topic: CS: Binary Tree Print (Read 797 times) |
|
Jonathan the Red
Guest
|
Quote:How would you print out the data in a binary tree, level by level, starting at the top?
|
|
Well, the below works...
Code:
struct Node
{
int m_nData;
Node* m_pLeft;
Node* m_pRight;
};
void PrintBinaryTree(Node* pNode)
{
int nLevel = 0;
if (pNode)
{
while (PrintTreeRecursive(pNode, 0, nLevel++))
;
}
}
bool PrintTreeRecursive(Node* pNode, int nCurrentLevel, int nDesiredLevel)
{
bool bRet = false;
if (nCurrentLevel == nDesiredLevel)
{
printf("%d ", pNode->m_nData);
bRet = true;
}
else
{
if (pNode->m_pLeft)
{
bRet = bRet || PrintTreeRecursive(pNode->m_pLeft, nCurrentLevel+1, nDesiredLevel);
}
if (pNode->m_pRight)
{
bRet = bRet || PrintTreeRecursive(pNode->m_pRight, nCurrentLevel+1, nDesiredLevel);
}
}
return bRet;
}
|
|
...but it takes O(n log n) to complete. Can it be done more efficiently?
|
|
 IP Logged |
|
|
|
Jonathan the Red
Guest
|
I'm a gimboid... change the lines that look like this:
Code:
bRet = bRet || PrintTreeRecursive(pNode->m_pLeft, nCurrentLevel+1, nDesiredLevel);
|
|
...to this. Damned short-circuiting...
Code:
bRet = PrintTreeRecursive(pNode->m_pLeft, nCurrentLevel+1, nDesiredLevel) || bRet;
|
|
|
|
IP Logged |
|
|
|
-D-
Guest
|
To print out level by level I would use a breadth first search. Running time is O(|V|+|E|) which is some kind of linear.
You need a queue of pointers to nodes of the tree.
Basic algorithm
PrintTree()
{
enqueue( head )
while( p = dequeue() )
{
print_element_at( p );
enqueue( p.left );
enqueue( p.right );
}
}
|
|
IP Logged |
|
|
|
-D-
Guest
|
I'm a dork. O(|V|+|E|) is for graphs, this is a tree, it should just be O(n). Although a binary tree can be considered a special form of graph.
-D-
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
Re: CS: Binary Tree Print
« Reply #4 on: Aug 1st, 2002, 5:19pm » |
 Quote  Modify
|
Yeah, breadth-first traversal using the queue is the elegant way... faster than repeatedly depth-first-searching the tree, deeper each time.
If you substitute "push" for "enqueue" and "pop" for "dequeue" (i.e., use a stack instead of a queue) into this same basic algorithm you get depth-first search. First time I saw that I thought that was a great insight.
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
Re: CS: Binary Tree Print
« Reply #5 on: Aug 1st, 2002, 10:37pm » |
Quote Modify
 Remove
|
How would push/pop be able to replace enqueue/dequeue?
1
/ \
2 3
/ \ / \
4 56 7
push 1
pop 1
push 2
push 3
pop 3
push 6
push 7
pop 7 <-- error
I'm assuming i made a mistake in my thinking...
-D-
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
Re: CS: Binary Tree Print
« Reply #6 on: Aug 1st, 2002, 10:42pm » |
Quote Modify
Remove
|
I'm a dork again... I thought you said it would do the same thing. You're right, it'll do a depth first search.
However if you're going to do a depth first search, you might as well just use recursion, it's just about as costly and you don't have to use a stack.
PrintTreeDepthFirst()
{
PrintNode( head );
}
PrintNode( node *p )
{
printElement( p );
PrintNode( p->left );
PrintNode( p->right );
}
... vs ...
PrintTreeDepthFirst()
{
push( head )
while( p = pop() )
{
printElement( p );
push( p->left );
push( p->right );
}
}
Neither way is any better I suppose.... I think I'd rather use recursion instead of set up a stack, and I -HATE- STL.
-D-
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: CS: Binary Tree Print
« Reply #7 on: Aug 7th, 2002, 9:55am » |
Quote Modify
|
on Aug 1st, 2002, 10:42pm, -D- wrote:| However if you're going to do a depth first search, you might as well just use recursion, it's just about as costly and you don't have to use a stack. |
|
And for our viewers - note that a recursive solution is using a stack too, but implicitly - the function call stack. Agreed that it's easier to not have to code that though.
|
|
IP Logged |
|
|
|
Nyarly
Newbie
Gender:
Posts: 2
|
|
Re: CS: Binary Tree Print
« Reply #8 on: Aug 23rd, 2002, 1:34pm » |
Quote Modify
|
on Aug 7th, 2002, 9:55am, S. Owen wrote:
And for our viewers - note that a recursive solution is using a stack too, but implicitly - the function call stack. Agreed that it's easier to not have to code that though. |
|
Easier to code, if you don't a stack implementation already. Harder to understand for any but a real hacker, and hardly more efficient. The call stack is almost always bigger than an a generic stack (what with return information and all), and you take the function call hit with every iteration. And besides, when you debug it, your call stack is going to grow and grow and... Of course, maybe that's better than you stack implementation indenting off the map...
OT - Why doesn't any debugger understand the idea of a linked list? Sometimes they do arrays nicely, (Codewarrior and gdb, but not MS's sludge) but I've yet to see a debugger not indent a linked list into oblivion (and Ritchee help you if you're looking a graph). 
|
|
IP Logged |
|
|
|
moonz
Guest
|
|
Re: CS: Binary Tree Print
« Reply #9 on: Jul 24th, 2003, 12:43am » |
Quote Modify
Remove
|
Another implementation without using the Node Levels instead.
 prev mens "Left" and next means "Right" ..
int BinaryTree::findTreedepth(Node* node) {
if (!node)
return 0;
int x = findTreedepth(node->prev);
int y = findTreedepth(node->next);
return (x>y) ? 1+x:1+y;
}
void BinaryTree::printNodeLevelWise(Node *node,int printLevel, int depth) {
if (!node)
return;
depth++;
if (printLevel == depth)
printf("Node at Level %d is: %d\n",printLevel,node->val);
else
printNodeLevelWise(node->prev, printLevel, depth);
printNodeLevelWise(node->next, printLevel, depth);
}
void BinaryTree::printTreeLevelWise() {
int depth = findTreedepth(root);
if (!depth) return;
for (int i = 1 ; i <= depth ; i++) {
printNodeLevelWise(root,i,0);
}
}
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: CS: Binary Tree Print
« Reply #10 on: Jul 30th, 2003, 2:04pm » |
Quote Modify
|
Here's another way:
Find the height of the tree, then convert the tree into a heap-like tree (in an array), indicating which elements are null. Caveat: this takes time O( exp(height of tree) ), bad for a poorly balanced tree.
Now print out the heap-tree, ignoring empty spots.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Johan
Newbie
Gender:
Posts: 3
|
|
Re: CS: Binary Tree Print
« Reply #11 on: Jan 24th, 2007, 5:28am » |
Quote Modify
|
on Aug 1st, 2002, 1:20pm, Jonathan the Red wrote:
Well, the below works...
Code:
struct Node
{
int m_nData;
Node* m_pLeft;
Node* m_pRight;
};
void PrintBinaryTree(Node* pNode)
{
int nLevel = 0;
if (pNode)
{
while (PrintTreeRecursive(pNode, 0, nLevel++))
;
}
}
bool PrintTreeRecursive(Node* pNode, int nCurrentLevel, int nDesiredLevel)
{
bool bRet = false;
if (nCurrentLevel == nDesiredLevel)
{
printf("%d ", pNode->m_nData);
bRet = true;
}
else
{
if (pNode->m_pLeft)
{
bRet = bRet || PrintTreeRecursive(pNode->m_pLeft, nCurrentLevel+1, nDesiredLevel);
}
if (pNode->m_pRight)
{
bRet = bRet || PrintTreeRecursive(pNode->m_pRight, nCurrentLevel+1, nDesiredLevel);
}
}
return bRet;
}
|
|
...but it takes O(n log n) to complete. Can it be done more efficiently?
|
|
It is actually O(n), not O(n log n). And it's much more memory effiecient than the queuing solutions (O(n)). But only if the tree is balanced.
(For a totally unbalanced tree (with just one leg) its is O(n²) and uses O(n) memory (for the return stack).)
Why is it O(n) and not O(N log n)?
For level one: 1 node is checked.
For level two: 1+2 nodes
For level three: 1+2+4 nodes
...
For level log(N): 1+2+...+N/2
As you can see every new level uses more than twice the time of the previous level, and consequently more time than all the lower levels taken together! (I leave the formal proof to someone less rusty.)
Thus the final level takes more than half the total time.
The final level takes only O(n) time (visiting every node once).
Thus the total time is less than 2*O(n) which is of course O(n)
OK, not a very neat proof.... But it's been a long time. 
Comments? Anyone can do it nicer?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print