给定一棵用二叉链表表示的二叉树，其根指针为 root，试写出求二叉树的深度的法,用c语言实现算法

以下是求二叉树深度的C语言实现：

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

我们可以使用递归的方法来求二叉树的深度。对于当前节点，它的深度等于它左右子树的深度的最大值加1。如果节点为空，深度为0。

可以通过调用maxDepth(root)来计算二叉树的深度，其中root是二叉树的根节点。

相关问题

设二叉树为以二叉链表为存储结构，且树中结点的关键字均不同。用c语言编写算法，判别给定二叉树是否为二叉排序树

可以使用中序遍历二叉树，将遍历结果存储在一个数组中，然后判断数组是否为升序排列即可。

具体实现代码如下：

#include <stdio.h>
#include <stdlib.h>

// 二叉树结点定义
typedef struct node {
    int data; // 结点数据
    struct node *left; // 左子树指针
    struct node *right; // 右子树指针
} Node;

// 中序遍历二叉树，将结果存储在数组中
void inorder(Node *root, int arr[], int *index) {
    if (root == NULL) {
        return;
    }
    inorder(root->left, arr, index);
    arr[(*index)++] = root->data;
    inorder(root->right, arr, index);
}

// 判断数组是否为升序排列
int isSorted(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i+1]) {
            return 0;
        }
    }
    return 1;
}

// 判断给定二叉树是否为二叉排序树
int isBST(Node *root) {
    int arr[100]; // 存储中序遍历结果的数组
    int index = 0; // 数组下标
    inorder(root, arr, &index);
    return isSorted(arr, index);
}

// 创建二叉树结点
Node* createNode(int data) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // 创建二叉排序树
    Node *root = createNode(4);
    root->left = createNode(2);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    root->right = createNode(6);
    root->right->left = createNode(5);
    root->right->right = createNode(7);

    // 判断是否为二叉排序树
    if (isBST(root)) {
        printf("给定二叉树是二叉排序树\n");
    } else {
        printf("给定二叉树不是二叉排序树\n");
    }

    return 0;
}

输出结果：

给定二叉树是二叉排序树

题目描述 二叉树的带权路径长度(WPLWPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二又树 TT,采用二叉链表存储，结点结构为: 其中叶结点的 weightweight 域保存该结点的非负权值。设 rootroot 为指向T的根结点的指针，请设计求 TT 的 WPLWPL 的算法. 程序中的主要部分已经帮你写好了，你只需要将如下代码拷贝到你的环境中，并且补充 WPL 函数功能即可。函数功能描述如下： 输入参数 输入参数 root：表示二叉树的根节点 返回值说明 返回一个整形值，表示题目中所求的WPL 用c语言

以下是求解二叉树带权路径长度的完整代码实现：

#include <stdio.h>
#include <stdlib.h>

//二叉树结点的结构体定义
typedef struct BiTNode
{
    int weight;  //权值
    struct BiTNode *lchild, *rchild;  //左右子树指针
}BiTNode, *BiTree;

//计算二叉树的带权路径长度
int WPL(BiTree root, int depth)
{
    int wpl = 0;
    if (root == NULL)  //空树
        return 0;
    else if (root->lchild == NULL && root->rchild == NULL)  //叶子结点
        return root->weight * depth;
    else  //非叶子结点
    {
        wpl = WPL(root->lchild, depth + 1) + WPL(root->rchild, depth + 1);
        return wpl;
    }
}

int main()
{
    //构建一棵二叉树
    BiTree root = (BiTree)malloc(sizeof(BiTNode));
    root->weight = 10;
    root->lchild = (BiTree)malloc(sizeof(BiTNode));
    root->lchild->weight = 5;
    root->lchild->lchild = NULL;
    root->lchild->rchild = NULL;
    root->rchild = (BiTree)malloc(sizeof(BiTNode));
    root->rchild->weight = 3;
    root->rchild->lchild = (BiTree)malloc(sizeof(BiTNode));
    root->rchild->lchild->weight = 2;
    root->rchild->lchild->lchild = NULL;
    root->rchild->lchild->rchild = NULL;
    root->rchild->rchild = (BiTree)malloc(sizeof(BiTNode));
    root->rchild->rchild->weight = 1;
    root->rchild->rchild->lchild = NULL;
    root->rchild->rchild->rchild = NULL;

    int depth = 1;  //根结点的深度为1
    int wpl = WPL(root, depth);
    printf("该二叉树的带权路径长度为：%d\n", wpl);

    return 0;
}

在上面的代码中，WPL函数采用递归的方式计算二叉树的带权路径长度。当树为空时，直接返回0；当树为单个结点时，返回该结点的权值乘以该结点的深度；当树为非叶子结点时，递归计算左右子树的带权路径长度之和。最终返回整棵树的带权路径长度。