.实验内容与步骤 （1）构造利用二叉链表存储表示的二叉树； （2）利用先序遍历创建一个二叉树； （3）递归计算二叉树的深度和叶子结点的个数。

好的，以下是实验内容与步骤：

1. 构造二叉链表存储表示的二叉树：

定义二叉链表结构体，包含三个成员：数据域，左子树指针和右子树指针。每个结点的左右子树指针初始值为 NULL，表示该结点没有左右子树。

2. 利用先序遍历创建二叉树：

先序遍历二叉树的顺序为：先访问根节点，然后访问左子树，最后访问右子树。我们可以利用这个顺序递归地创建二叉树。具体步骤如下：

1）读入当前结点的数据，若数据为特定值（如 #），则返回 NULL。

2）创建一个新结点，将当前数据存储到新结点的数据域中。

3）递归创建左子树，将返回值赋给新结点的左子树指针。

4）递归创建右子树，将返回值赋给新结点的右子树指针。

5）返回新结点的指针。

3. 递归计算二叉树的深度和叶子结点的个数：

二叉树的深度为从根节点到最深叶子结点的路径长度。我们可以递归地计算左子树和右子树的深度，并返回深度较大的值加一，即可得到整棵树的深度。

叶子结点是指没有左右子树的结点。我们可以递归地遍历整棵树，统计叶子结点的个数。

具体步骤如下：

1）递归计算左子树的深度，将返回值存储到 left_depth 变量中。

2）递归计算右子树的深度，将返回值存储到 right_depth 变量中。

3）返回 left_depth 和 right_depth 中较大的值加一，即为整棵树的深度。

4）若当前结点没有左右子树，则返回 1，表示该结点是叶子结点。

5）否则，递归计算左子树和右子树的叶子结点个数，并返回两个值之和。

以上就是实验内容与步骤。希望能对你有所帮助！

相关问题

c语言 构造利用二叉链表存储表示的二叉树 利用先序遍历创建一个二叉树 递归计算二叉树的深度和叶子结点的个数。

好的，下面是代码实现：

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

// 二叉树的结构体
typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 先序遍历创建二叉树
void CreateBiTree(BiTree *T) {
    char c;
    scanf("%c", &c);
    if (c == ' ') {
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = c;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

// 递归计算二叉树深度
int GetDepth(BiTree T) {
    if (!T) {
        return 0;
    } else {
        int left_depth = GetDepth(T->lchild);
        int right_depth = GetDepth(T->rchild);
        return (left_depth > right_depth ? left_depth : right_depth) + 1;
    }
}

// 递归计算叶子节点个数
int GetLeafCount(BiTree T) {
    if (!T) {
        return 0;
    } else if (!T->lchild && !T->rchild) {
        return 1;
    } else {
        return GetLeafCount(T->lchild) + GetLeafCount(T->rchild);
    }
}

int main() {
    BiTree T;
    printf("请按先序遍历的顺序输入二叉树（空格表示空节点）：\n");
    CreateBiTree(&T);

    printf("二叉树的深度为：%d\n", GetDepth(T));
    printf("叶子节点的个数为：%d\n", GetLeafCount(T));

    return 0;
}

以上代码中，`BiTNode`是二叉树的结构体，包括数据域`data`和左右孩子指针`lchild`和`rchild`。`CreateBiTree`函数用于先序遍历创建二叉树。`GetDepth`函数用于递归计算二叉树的深度。`GetLeafCount`函数用于递归计算叶子节点个数。在`main`函数中，先调用`CreateBiTree`函数创建二叉树，然后调用`GetDepth`和`GetLeafCount`函数计算深度和叶子节点个数并输出结果。

构造利用二叉链表存储表示的二叉树； （2）利用先序遍历创建一个二叉树； （3）递归计算二叉树的深度和叶子结点的个数。

1. 二叉链表存储表示的二叉树

二叉链表存储表示的二叉树是指将每个结点用一个三元组表示，包括其本身的数据域和指向左右子树的两个指针。具体实现如下：

typedef struct BinaryTreeNode {
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
} BinaryTreeNode;

2. 先序遍历创建二叉树

先序遍历创建二叉树是指根据树的先序遍历序列创建一棵二叉树。具体实现如下：

BinaryTreeNode* createBinaryTree() {
    int data;
    cin >> data;
    if (data == -1) { // -1 表示空结点
        return NULL;
    }
    BinaryTreeNode* root = new BinaryTreeNode;
    root->data = data;
    root->left = createBinaryTree();
    root->right = createBinaryTree();
    return root;
}

3. 递归计算二叉树的深度和叶子结点个数

二叉树的深度可以通过递归求解，其深度等于左右子树深度的最大值加1。叶子结点个数可以通过递归求解，其个数等于左右子树叶子结点个数之和。

int getDepth(BinaryTreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int left = getDepth(root->left);
    int right = getDepth(root->right);
    return max(left, right) + 1;
}

int getLeafCount(BinaryTreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    int left = getLeafCount(root->left);
    int right = getLeafCount(root->right);
    return left + right;
}