以二叉链存储二叉树b，设计算法求二叉树的高度。 typedef struct node { ElemType data; struct node* lchild; struct node* rchild; }BTNode; int GetHeight(BTNode* b)

为了求解二叉树的高度，可以采用递归的方式，因为二叉树的高度就是其左右子树高度的最大值加1。以下是用给定的二叉链表示的结构体`BTNode`编写的一个算法：

int GetHeight(BTNode* b) {
    // 如果树为空，则高度为0
    if (b == NULL) {
        return 0;
    }
    
    // 分别计算左右子树的高度
    int left_height = GetHeight(b->lchild);
    int right_height = GetHeight(b->rchild);

    // 返回较大的那一边的高度加1（即当前节点的高度）
    return (left_height > right_height ? left_height + 1 : right_height + 1);
}

这个函数接受一个指向二叉树根节点的指针`b`，然后递归地访问左子树和右子树，直到找到空节点（表示到达叶节点或空树）。每次递归调用都会增加1来表示当前层级，所以最终返回的是整个树的高度。

如果你想要直接查看二叉树的高度而不是编写算法，可以遍历整棵树并记录深度，但在没有额外数据结构的情况下，递归是最直观且常用的方法。

相关问题

假设二叉树采用二叉链存储结构存储，设计一个算法SonNodes，求出一棵给定二叉树的所有非叶子结点的个数 已知二叉树结构体声明如下： typedef struct node{ ElemType data; struct node *lchild; struct node *rchild; } BTNode; 根据上述要求完成算法中的代码，并将完整代码写在答题框内(二叉树结构体声明无需写到答题框) int SonNodes(BTNode *b){ //补充算法中的代码 }

完整代码如下：

int SonNodes(BTNode *b){
    if(b == NULL || (b->lchild == NULL && b->rchild == NULL)) // 若为空树或为叶子结点，返回0
        return 0;
    else
        return SonNodes(b->lchild) + SonNodes(b->rchild) + 1; // 递归求解左右子树的非叶子结点个数，再加上当前结点
}

算法思路：

对于一棵二叉树，如果为空树或为叶子结点，那么它就没有非叶子结点；如果它有左右子树，则它本身也是一个非叶子结点。因此，我们可以使用递归的方式，对二叉树的左右子树分别求解它们的非叶子结点个数，并将它们的个数相加，加上当前结点，即可得到整棵树的非叶子结点个数。

以二叉链表作为二叉树的存储结构，请使用 C 语言分别实现以下递归算法： (1）将二叉树中所有结点的左右子树相互交换。 (2）求二叉树中叶子结点数目。 typedef char elemtype ; typedef struct node ( elemtype data ; struct node * Ichild ,* rchild ;} bittree ;/／二叉链表 请使用以上二叉链表定义完成如下函数定义 bittree * swap ( bittree * root );// root指向二叉树的根结点 int leafnum ( bittree * root );//返回叶子结点数目

好的，以下是对应的递归算法实现：

1. 将二叉树中所有结点的左右子树相互交换

bittree* swap(bittree* root) {
    if (root == NULL) {
        return NULL;
    }
    bittree* temp = root->lchild;
    root->lchild = swap(root->rchild);
    root->rchild = swap(temp);
    return root;
}

2. 求二叉树中叶子结点数目

int leafnum(bittree* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->lchild == NULL && root->rchild == NULL) {
        return 1;
    }
    return leafnum(root->lchild) + leafnum(root->rchild);
}