白痴爱面包 发表于 2023-4-16 22:23:07

创建二叉树

如何方便地创建二叉树（结点较多）

isdkz 发表于 2023-4-16 22:28:39

创建二叉树有多种方法，以下是一种简单且易于理解的方法。我们将通过定义二叉树结点结构以及创建、插入和遍历函数来实现这个目标。以下是一个简单的C语言实现：

1、定义结点结构：

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

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

2、创建新结点的函数：

Node *createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

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

Node *insert(Node *root, int data) {
    if (root == NULL) {
      return createNode(data);
    }

    if (data < root->data) {
      root->left = insert(root->left, data);
    } else if (data > root->data) {
      root->right = insert(root->right, data);
    }
    return root;
}

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

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

5、测试上述函数：

int main() {
    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

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

    return 0;
}

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

你可以根据需要调整 data_list 的内容，以创建不同大小和形状的二叉树。

白痴爱面包 发表于 2023-4-16 22:44:35

isdkz 发表于 2023-4-16 22:28
创建二叉树有多种方法，以下是一种简单且易于理解的方法。我们将通过定义二叉树结点结构以及创建、插入和遍 ...

额，我想的是快速建立一颗二叉树便于测试，教材上是通过预先在文件中写好数据，然后创建时读入，但我想有没有更好的办法喃

isdkz 发表于 2023-4-16 22:47:14

白痴爱面包 发表于 2023-4-16 22:44
额，我想的是快速建立一颗二叉树便于测试，教材上是通过预先在文件中写好数据，然后创建时读入，但我想有 ...

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

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

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

Node *createNode(int data) {
    if (data == -1) {
      return NULL;
    }

    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Node *buildTree(int *arr, int idx, int n) {
    if (idx >= n || arr == -1) {
      return NULL;
    }

    Node *root = createNode(arr);
    root->left = buildTree(arr, 2 * idx + 1, n);
    root->right = buildTree(arr, 2 * idx + 2, n);
    return root;
}

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

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

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

    return 0;
}


在这个例子中，我们用一个数组 arr 表示二叉树，-1表示空节点。buildTree 函数将递归地创建树，根据数组的索引和数组长度判断子树是否为空。这样，你可以在代码中直接定义一个数组，方便地创建和修改树结构进行测试。
页: [1]
查看完整版本: 创建二叉树