Frankjunyu
2015-10-29 06:52
采纳率: 58.8%
浏览 1.5k
已采纳

c语言二叉树问题,代码不太理解,求大神解释,急

问题:A Binary Tree is called balanced if, for each node in the tree, the height of its left and right subtrees differ by no more than one. Write a function
int height_if_balanced( Tnode *root )
which returns -1 if the tree is not balanced, and returns the height of the tree, if it is balanced.

代码:

int height_if_balanced( Tnode *root )
{
int leftHeight, rightHeight, heightDiff;

if( root == NULL ) {
return 0; // tree is empty
}

leftHeight = height_if_balanced( root->left );
rightHeight = height_if_balanced( root->right );

if( leftHeight == -1 || rightHeight == -1 ) {
// if either the left or right subtree is unbalanced,
return -1 ; // then the whole tree is unbalanced
}

heightDiff = leftHeight - rightHeight;

if( heightDiff < -1 || heightDiff > 1 ) {
return -1; // tree is unbalanced
}

// tree is balanced, so we return its height
if( heightDiff > 0 ) {
return( leftHeight + 1 );
}
else {
return( rightHeight + 1 );
}
}

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • cxlovu 2015-10-29 09:46
    已采纳

    其实这个英文注解很清楚了,这个函数的功能是判断这棵二叉树是否为平衡的
    所谓的平衡是指两边子树的高度之差绝对值不大于1
    height_if_balanced()这个函数如果二叉树是平衡的输出高度(取左右子树中高度加大的),否则输出-1
    然后height_if_balanced()是一个递归函数,一层一层下去直到叶子节点跳出,最后返回高度
    纯手打, 还有什么不懂的地方再问吧

    已采纳该答案
    打赏 评论

相关推荐 更多相似问题