设树采用孩子兄弟表示法存放，用类C语言设计算法计算树的高度。

Question

不要复制，谢谢。

Answer 1

采用递归求解，先求左子树的高度和右子树的高度，然后整棵树的高度就是两颗子树高度的最大值+1。假定叶子节点高度为0。代码如下：

struct node {
    int val;
    struct node* left;
    struct node* right;
};

int height(struct node* root)
{
    int h, lh, rh;
    if ( root == NULL)
        return -1;//这里返回-1表示叶子节点的高度为0，若规定叶子节点的高度为1，这里返回0即可
    lh = height(root->left);
    rh = height(root->right);
    if (lh > rh) 
        h = lh + 1;
    else 
        h = rh + 1;
    return h;
}

追问

能写个程序吗？

追答

代码我上面不是已经写了吗，你可以把这个函数添加到自己的程序里面去啊

Answer 2

计算树的高度是一个很简单的递归算法。下面这个算法充分简洁的表达了计算的全部过程。
int height(Node node){
//计算自身高度
int myheight;
if(!node.hasChild()){
myheight=1;
}else{
//注意按孩子兄弟表示法的树节点一般只有一个孩子
Node child=node.getChild();
myheight=height(child)+1;
}

//计算兄弟最大高度
int brotherheight=0;
List<Node> brothers=node.getBrothers();
if(brothers!=null&&brothers.size()>0){
//此处自行加一个循环计算兄弟的最大高度
brothers=maxHeight(brothers);
}
return myheight>brotherheight?myheight:brotherheight;
}

Answer 3

你的问题看数据结构可以自己解决的。