Monday, October 22, 2012
tree depth and balance tree
int Gettreedepth(BinaryTreeNode *pNode)
{
if(NULL ==pNode)
return 0;
if(pNode->left)
int leftdepth = Gettreedepth(pNode->left);
if(pNode->right)
int rightdepth = Gettreedepth(pNode->right);
return (leftdepth > rightdepth) ? (leftdepth+1) : (rightdepth+1);
}
bool IsBalanced(BinaryTreeNode *pRoot)
{
if(NULL==pRoot)
return true;
if(pRoot->left)
int ld = Gettreedepth(pRoot->left);
if(pRoot->right)
int rd = Gettreedepth(pRoot->right);
if ((ld-rd)>1 || (ld-rd)< -1)
return false;
return (IsBalanced(pRoot->left) && IsBalanced(pRoot->right));
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment