//Tree definition
struct Node{
Node* Left;
Node* Right;
int Val;
};
typedef Node * tree;
/*Helper functions to find minimum and maximum*/
int MaxVal (int iNum1, int iNum2)
{
return iNum1 >= iNum2 ? iNum1 : iNum2;
}
int MinVal (int iNum1, int iNum2)
{
return iNum1 <= iNum2 ? iNum1 : iNum2;
}
/* Depth of trees */
int FindTreeDepth (tree t)
{
if (t == NULL)
return 0;
return 1 + MaxVal(FindTreeDepth(t->Left), FindTreeDepth(t->Right));
}
/* Minimum depth of a leaf */
int FindMinDepthOfLeaf (tree t)
{
if (t == NULL)
return 0;
if (t->Left == NULL)
if (t->Right == NULL)
return 1;
else
return 1 + FindMinDepthOfLeaf(t->Right);
else
if (t->Right == NULL)
return 1 + FindMinDepthOfLeaf(t->Left);
else
return 1 + MinVal(FindMinDepthOfLeaf(t->Left),
FindMinDepthOfLeaf(t->Right));
}
bool IsTreeBalanced (tree t)
{
//For tree to be balanced the depths of two arbitrary leaves must differ
//by at most 1
return FindTreeDepth(t) - FindMinDepthOfLeaf(t) < = 1;
}
Wednesday, December 31, 2008
Subscribe to:
Post Comments (Atom)
.jpg)
No comments:
Post a Comment