二叉树——课上练（链式存储结构）

二叉树的链式存储结构是通过定义一个含有数据和指向左右子节点的指针的结构体来实现的。每个结点都包含一个数据项和两个指针，分别指向其左子节点和右子节点。采用链式存储结构的优点是可以灵活地插入、删除和修改节点，但相应的缺点是需要更多的存储空间和额外的指针操作。

在建立二叉树时，可以按照先序遍历的顺序输入节点序列，并采用递归方式进行建立。例如，按照先序输入的节点序列为：a b c # # # d e # f # # g # #。其中，#表示空节点。通过递归方式建立二叉树可以保证节点的插入顺序与先序输入的顺序一致。

关于二叉树的一些特性和存储方式，还有以下几点：
1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个节点。
2. 若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大节点数是2^k-1。
3. 对任何一棵二叉树，如果其叶节点个数为n0，度为2的非叶节点个数为n2，则有n0 = n2 + 1。
4. 具有n个节点的完全二叉树的深度k为log2(n+1)向上取整。

相关问题

一、实验目标 1.熟悉二叉树的链式存储结构特性； 2.掌握二叉树——能够用C语言实现二叉树的各种基本操作。 二、实验内容 实现二叉树的基本操作： (1)实现二叉树的创建功能； (2)实现遍历功能，先序、中序、后序，选择其中一种；打印出遍历序列； (3)实现“结点的度”的统计功能；输出每个结点的度； (4)计算树的深度。 三、测试数据 用于测试的二叉树为： 注意： (1)图中的灰色结点是不存在的； (2)结点“圆圈”中的数字，即为其所存储的数据； (3)采用链式存储而不是顺序存储方式； (4)在输出结点的度时，可用结点的值标识该结点（图示中每个结点所存数据已设定为各自不同）；例如，13：2，即表示(13)这个结点的度为2. (5)树的创建时，采用交互方式（键盘）输入树的数据。

好的，这是一个二叉树的实验，需要实现二叉树的创建、遍历、统计结点度和计算树的深度功能。下面我将逐一为您介绍如何实现这些功能。

1. 实现二叉树的创建功能

二叉树的创建可以采用递归方法，即每次输入一个结点的值，然后递归创建该结点的左子树和右子树。具体实现方式如下：

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

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

Node* createTree() {
    Node *node;
    int data;
    printf("请输入结点的值（-1表示该结点为空）：");
    scanf("%d", &data);
    if (data == -1) {
        node = NULL;
    } else {
        node = (Node*)malloc(sizeof(Node));
        node->data = data;
        node->left = createTree();
        node->right = createTree();
    }
    return node;
}

2. 实现遍历功能

遍历二叉树有三种方式：先序遍历、中序遍历和后序遍历。下面分别介绍实现方法。

先序遍历：

void preOrder(Node *node) {
    if (node != NULL) {
        printf("%d ", node->data);
        preOrder(node->left);
        preOrder(node->right);
    }
}

中序遍历：

void inOrder(Node *node) {
    if (node != NULL) {
        inOrder(node->left);
        printf("%d ", node->data);
        inOrder(node->right);
    }
}

后序遍历：

void postOrder(Node *node) {
    if (node != NULL) {
        postOrder(node->left);
        postOrder(node->right);
        printf("%d ", node->data);
    }
}

3. 实现“结点的度”的统计功能

结点的度是指一个结点的子节点个数。因此，统计结点的度需要遍历整棵树，对于每个结点，统计出其左子树和右子树的节点数即可。

int getDegree(Node *node) {
    if (node == NULL) {
        return 0;
    } else {
        int leftDegree = getDegree(node->left);
        int rightDegree = getDegree(node->right);
        return (node->left != NULL) + (node->right != NULL) + leftDegree + rightDegree;
    }
}

4. 计算树的深度

计算树的深度也需要遍历整棵树，对于每个结点，计算出其左子树和右子树的深度，然后取较大值加1即可。

int getDepth(Node *node) {
    if (node == NULL) {
        return 0;
    } else {
        int leftDepth = getDepth(node->left);
        int rightDepth = getDepth(node->right);
        return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
    }
}

整个程序的完整代码如下：

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

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

Node* createTree() {
    Node *node;
    int data;
    printf("请输入结点的值（-1表示该结点为空）：");
    scanf("%d", &data);
    if (data == -1) {
        node = NULL;
    } else {
        node = (Node*)malloc(sizeof(Node));
        node->data = data;
        node->left = createTree();
        node->right = createTree();
    }
    return node;
}

void preOrder(Node *node) {
    if (node != NULL) {
        printf("%d ", node->data);
        preOrder(node->left);
        preOrder(node->right);
    }
}

void inOrder(Node *node) {
    if (node != NULL) {
        inOrder(node->left);
        printf("%d ", node->data);
        inOrder(node->right);
    }
}

void postOrder(Node *node) {
    if (node != NULL) {
        postOrder(node->left);
        postOrder(node->right);
        printf("%d ", node->data);
    }
}

int getDegree(Node *node) {
    if (node == NULL) {
        return 0;
    } else {
        int leftDegree = getDegree(node->left);
        int rightDegree = getDegree(node->right);
        return (node->left != NULL) + (node->right != NULL) + leftDegree + rightDegree;
    }
}

int getDepth(Node *node) {
    if (node == NULL) {
        return 0;
    } else {
        int leftDepth = getDepth(node->left);
        int rightDepth = getDepth(node->right);
        return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
    }
}

int main() {
    Node *root = createTree();
    printf("先序遍历结果：");
    preOrder(root);
    printf("\n中序遍历结果：");
    inOrder(root);
    printf("\n后序遍历结果：");
    postOrder(root);
    printf("\n结点的度：\n");
    printf("%d:%d\n", root->data, getDegree(root));
    printf("%d:%d\n", root->left->data, getDegree(root->left));
    printf("%d:%d\n", root->right->data, getDegree(root->right));
    printf("%d:%d\n", root->left->left->data, getDegree(root->left->left));
    printf("%d:%d\n", root->left->right->data, getDegree(root->left->right));
    printf("树的深度：%d\n", getDepth(root));
    return 0;
}

希望这个程序对您有所帮助！