设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 创建二叉树
返回列表 发新帖
查看: 621|回复: 3

[已解决]创建二叉树

[复制链接]
白痴爱面包
发表于 2023-4-16 22:23:07 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
如何方便地创建二叉树（结点较多）
最佳答案
月排行榜 / 总排行榜
isdkz
2023-4-16 22:47:14
白痴爱面包 发表于 2023-4-16 22:44
额，我想的是快速建立一颗二叉树便于测试，教材上是通过预先在文件中写好数据，然后创建时读入，但我想有 ...

明白你的需求了，可以使用数组快速地创建一颗二叉树，下面的例子使用层序遍历顺序表示的数组，空结点用-1表示。这样，你可以直接在代码中定义一个数组，快速创建一棵二叉树。

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

  4. typedef struct Node {
  5.     int data;
  6.     struct Node *left;
  7.     struct Node *right;
  8. } Node;

  10. Node *createNode(int data) {
  11.     if (data == -1) {
  12.         return NULL;
  13.     }

  15.     Node *newNode = (Node *)malloc(sizeof(Node));
  16.     newNode->data = data;
  17.     newNode->left = NULL;
  18.     newNode->right = NULL;
  19.     return newNode;
  20. }

  22. Node *buildTree(int *arr, int idx, int n) {
  23.     if (idx >= n || arr[idx] == -1) {
  24.         return NULL;
  25.     }

  27.     Node *root = createNode(arr[idx]);
  28.     root->left = buildTree(arr, 2 * idx + 1, n);
  29.     root->right = buildTree(arr, 2 * idx + 2, n);
  30.     return root;
  31. }

  33. void inorderTraversal(Node *root) {
  34.     if (root != NULL) {
  35.         inorderTraversal(root->left);
  36.         printf("%d ", root->data);
  37.         inorderTraversal(root->right);
  38.     }
  39. }

  41. int main() {
  42.     int arr[] = {1, 2, 3, 4, 5, -1, 6, -1, -1, 7, 8, -1, -1, 9, 10};
  43.     int n = sizeof(arr) / sizeof(arr[0]);
  44.     Node *root = buildTree(arr, 0, n);

  46.     printf("中序遍历结果：\n");
  47.     inorderTraversal(root);

  49.     return 0;
  50. }
复制代码


在这个例子中，我们用一个数组 arr 表示二叉树，-1表示空节点。buildTree 函数将递归地创建树，根据数组的索引和数组长度判断子树是否为空。这样，你可以在代码中直接定义一个数组，方便地创建和修改树结构进行测试。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

isdkz
发表于 2023-4-16 22:28:39 | 显示全部楼层
创建二叉树有多种方法，以下是一种简单且易于理解的方法。我们将通过定义二叉树结点结构以及创建、插入和遍历函数来实现这个目标。以下是一个简单的C语言实现：

1、定义结点结构：

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

  4. typedef struct Node {
  5.     int data;
  6.     struct Node *left;
  7.     struct Node *right;
  8. } Node;
复制代码


2、创建新结点的函数：

  1. Node *createNode(int data) {
  2.     Node *newNode = (Node *)malloc(sizeof(Node));
  3.     newNode->data = data;
  4.     newNode->left = NULL;
  5.     newNode->right = NULL;
  6.     return newNode;
  7. }
复制代码


3、插入新结点的函数（以二叉搜索树为例）：

  1. Node *insert(Node *root, int data) {
  2.     if (root == NULL) {
  3.         return createNode(data);
  4.     }

  6.     if (data < root->data) {
  7.         root->left = insert(root->left, data);
  8.     } else if (data > root->data) {
  9.         root->right = insert(root->right, data);
  10.     }
  11.     return root;
  12. }
复制代码


4、遍历二叉树（这里使用中序遍历）：

  1. void inorderTraversal(Node *root) {
  2.     if (root != NULL) {
  3.         inorderTraversal(root->left);
  4.         printf("%d ", root->data);
  5.         inorderTraversal(root->right);
  6.     }
  7. }
复制代码


5、测试上述函数：

  1. int main() {
  2.     Node *root = NULL;
  3.     root = insert(root, 50);
  4.     insert(root, 30);
  5.     insert(root, 20);
  6.     insert(root, 40);
  7.     insert(root, 70);
  8.     insert(root, 60);
  9.     insert(root, 80);

  11.     printf("中序遍历结果：\n");
  12.     inorderTraversal(root);

  14.     return 0;
  15. }
复制代码


在这个例子中，我们使用 data_list 来表示二叉树的层次遍历。None 代表空节点。create_binary_tree 函数将根据这个层次遍历列表来构建二叉树。这是一个方便的方法，因为你可以用一个列表来表示整个树的结构。

你可以根据需要调整 data_list 的内容，以创建不同大小和形状的二叉树。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

白痴爱面包
 楼主| 发表于 2023-4-16 22:44:35 | 显示全部楼层
isdkz 发表于 2023-4-16 22:28
创建二叉树有多种方法，以下是一种简单且易于理解的方法。我们将通过定义二叉树结点结构以及创建、插入和遍 ...

额，我想的是快速建立一颗二叉树便于测试，教材上是通过预先在文件中写好数据，然后创建时读入，但我想有没有更好的办法喃
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

isdkz
发表于 2023-4-16 22:47:14 | 显示全部楼层    本楼为最佳答案   
白痴爱面包 发表于 2023-4-16 22:44
额，我想的是快速建立一颗二叉树便于测试，教材上是通过预先在文件中写好数据，然后创建时读入，但我想有 ...

明白你的需求了，可以使用数组快速地创建一颗二叉树，下面的例子使用层序遍历顺序表示的数组，空结点用-1表示。这样，你可以直接在代码中定义一个数组，快速创建一棵二叉树。

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

  4. typedef struct Node {
  5.     int data;
  6.     struct Node *left;
  7.     struct Node *right;
  8. } Node;

  10. Node *createNode(int data) {
  11.     if (data == -1) {
  12.         return NULL;
  13.     }

  15.     Node *newNode = (Node *)malloc(sizeof(Node));
  16.     newNode->data = data;
  17.     newNode->left = NULL;
  18.     newNode->right = NULL;
  19.     return newNode;
  20. }

  22. Node *buildTree(int *arr, int idx, int n) {
  23.     if (idx >= n || arr[idx] == -1) {
  24.         return NULL;
  25.     }

  27.     Node *root = createNode(arr[idx]);
  28.     root->left = buildTree(arr, 2 * idx + 1, n);
  29.     root->right = buildTree(arr, 2 * idx + 2, n);
  30.     return root;
  31. }

  33. void inorderTraversal(Node *root) {
  34.     if (root != NULL) {
  35.         inorderTraversal(root->left);
  36.         printf("%d ", root->data);
  37.         inorderTraversal(root->right);
  38.     }
  39. }

  41. int main() {
  42.     int arr[] = {1, 2, 3, 4, 5, -1, 6, -1, -1, 7, 8, -1, -1, 9, 10};
  43.     int n = sizeof(arr) / sizeof(arr[0]);
  44.     Node *root = buildTree(arr, 0, n);

  46.     printf("中序遍历结果：\n");
  47.     inorderTraversal(root);

  49.     return 0;
  50. }
复制代码


在这个例子中，我们用一个数组 arr 表示二叉树，-1表示空节点。buildTree 函数将递归地创建树，根据数组的索引和数组长度判断子树是否为空。这样，你可以在代码中直接定义一个数组，方便地创建和修改树结构进行测试。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-5-2 00:32

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表