Binary Search Trees C++
Author
Does anyone know how to accurately get the height of a binary search tree? (where it is unbalanced and could have any amount of elements?)
You can do it recursively. Traverse the binary tree, keeping track of the current level of recursion and the maximum level of recursion. The height of the tree will be that maximum at the end of the traversal (+/- 1 depending on how you count the recursion levels).
Let's see if you can write the function with that information -- show your work. [smile]
Let's see if you can write the function with that information -- show your work. [smile]
Author
ok so i have a depth first traversal...
[edits just fixing code]
and I don't really see where I could put a counter to count the levels
mInOrder(NODE *Current_Node){ if(Current_Node ==0) { cout << "Current tree is empty" << endl; return; } if(Current_Node->left_child!=0) mInOrder(Current_Node->left_child); if(Current_Node->right_child!=0) mInOrder(Current_Node->right_child); return;}[edits just fixing code]
and I don't really see where I could put a counter to count the levels
Quote:Original post by Boder
Pass it in as a parameter and then increment it when you move to a child node.
And pass the total height as a reference parameter. You will need a second function that calls the recursive traversal one.
void height_impl(NODE* tree, int depth, int& maxdepth); // recursive traversalint height(NODE* tree){ int result = 0; height_impl(tree, 0, result); return result;}(though actually it doesn't really matter - you're working with a tree, so you can't really do much tail recursion...)
Author
mInOrder(NODE *Current_Node){ if(Current_Node ==0) { cout << "Current tree is empty" << endl; return; } if(Current_Node->left_child!=0) { CurrentLevel++; mInOrder(Current_Node->left_child); CurrentLevel--; } if(Current_Node->right_child!=0) { CurrentLevel++; mInOrder(Current_Node->right_child); CurrentLevel--; } if(CurrentLevel > MaxLevel) MaxLevel=CurrentLevel; CurrentLevel--; return;}int tree::getheight(){ return MaxLevel;}might this work too? and just take the height as the maximum level? (CurrentLevel and MaxLevel are class members) Its just pseudocode right now, fixing :)
yeah, it should work, though it is simpler (in my eyes) to directly pass level+1 to the function call rather than keep an external level which you increment before and decrement after the function call.
void height_impl(NODE* tree, int depth, int& maxdepth){ if(depth>maxdepth) maxdepth=depth; if(tree->left_child != 0) height_impl(tree->left_child, depth+1, maxdepth); if(tree->right_child != 0) height_impl(tree->right_child, depth+1, maxdepth);}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
