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));

}

No comments:

Post a Comment