C语言实现二叉树的创建、遍历和销毁实验报告

二叉树是一种常用的数据结构，它由若干个节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。本次实验旨在掌握二叉树的基本操作，包括创建二叉树、遍历二叉树和销毁二叉树。

一、创建二叉树

创建二叉树的方法有多种，本次实验采用先序遍历的方式构建二叉树。先序遍历的顺序是先遍历根节点，然后遍历左子树，最后遍历右子树。因此，我们可以通过递归的方式创建二叉树。具体代码如下：

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

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

TreeNode* createTree(int* nums, int size, int index) {
  if (index >= size || nums[index] == -1) {
    return NULL;
  }

  TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
  root->val = nums[index];
  root->left = createTree(nums, size, 2 * index + 1);
  root->right = createTree(nums, size, 2 * index + 2);

  return root;
}

int main() {
  int nums[] = {1, 2, 3, 4, -1, 5, 6};
  int size = sizeof(nums) / sizeof(int);
  TreeNode* root = createTree(nums, size, 0);
  return 0;
}

上述代码中，我们定义了一个结构体 TreeNode 来表示二叉树的节点。其中 val 表示节点的值，left 和 right 分别表示左右子节点。函数 createTree 接收一个整数数组 nums，数组中的元素按照先序遍历的顺序排列，-1 表示空节点。变量 size 表示数组的长度，index 表示当前节点在数组中的下标。如果当前节点为空节点，返回 NULL。否则，创建一个节点，并递归创建其左右子树，最后返回根节点。

二、遍历二叉树

遍历二叉树的方法有三种，分别是先序遍历、中序遍历和后序遍历。本次实验实现了先序遍历和中序遍历。具体代码如下：

void preOrder(TreeNode* root) {
  if (root == NULL) {
    return;
  }

  printf('%d ', root->val);
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(TreeNode* root) {
  if (root == NULL) {
    return;
  }

  inOrder(root->left);
  printf('%d ', root->val);
  inOrder(root->right);
}

上述代码中，函数 preOrder 和 inOrder 分别实现了先序遍历和中序遍历。如果当前节点为空节点，返回。否则，先访问当前节点，再递归遍历其左右子树。其中，先序遍历是先遍历根节点，中序遍历是先遍历左子树。

三、销毁二叉树

销毁二叉树的方法是先释放其左右子树，再释放根节点。具体代码如下：

void destroyTree(TreeNode* root) {
  if (root == NULL) {
    return;
  }

  destroyTree(root->left);
  destroyTree(root->right);
  free(root);
}

上述代码中，函数 destroyTree 接收一个根节点，先递归销毁其左右子树，最后释放根节点。

完整代码如下：

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

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

TreeNode* createTree(int* nums, int size, int index) {
  if (index >= size || nums[index] == -1) {
    return NULL;
  }

  TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
  root->val = nums[index];
  root->left = createTree(nums, size, 2 * index + 1);
  root->right = createTree(nums, size, 2 * index + 2);

  return root;
}

void preOrder(TreeNode* root) {
  if (root == NULL) {
    return;
  }

  printf('%d ', root->val);
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(TreeNode* root) {
  if (root == NULL) {
    return;
  }

  inOrder(root->left);
  printf('%d ', root->val);
  inOrder(root->right);
}

void destroyTree(TreeNode* root) {
  if (root == NULL) {
    return;
  }

  destroyTree(root->left);
  destroyTree(root->right);
  free(root);
}

int main() {
  int nums[] = {1, 2, 3, 4, -1, 5, 6};
  int size = sizeof(nums) / sizeof(int);
  TreeNode* root = createTree(nums, size, 0);

  printf("Preorder traversal: ");
  preOrder(root);
  printf("\n");

  printf("Inorder traversal: ");
  inOrder(root);
  printf("\n");

  destroyTree(root);
  return 0;
}

上述代码中，我们先创建一个二叉树，然后分别进行先序遍历和中序遍历。最后，销毁二叉树。运行结果如下：

Preorder traversal: 1 2 4 3 5 6 
Inorder traversal: 4 2 1 5 3 6 

综上所述，本次实验通过C语言实现了二叉树的创建、遍历和销毁。这些操作是二叉树基本操作，也是其他高级操作的基础。掌握了这些基本操作，我们可以更好地理解和应用二叉树。