问题描述

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
height_if_balanced()这个函数如果二叉树是平衡的输出高度（取左右子树中高度加大的），否则输出-1
然后height_if_balanced()是一个递归函数，一层一层下去直到叶子节点跳出，最后返回高度
纯手打， 还有什么不懂的地方再问吧

解决方案二：

C语言二叉树知识点讲解与实现代码
C语言二叉树与队列实现基础代码