时间戳

首页 > 解决方案 > 在 C 中创建一个 void toBST 函数，它接受 2 个参数：Tree* root 和一个数组，并将所有树节点添加到一个数组中 - 顺序无关紧要

c - 在 C 中创建一个 void toBST 函数，它接受 2 个参数：Tree* root 和一个数组，并将所有树节点添加到一个数组中 - 顺序无关紧要

问题描述

我正在尝试在 C 中实现以下功能：

void BSTtoArr(Tree * root,Tree* arr[])

它需要一棵树并将其节点添加到节点数组中。到目前为止我写的是：

void BSTtoArr(Tree * root,Tree* arr[]) {
    static int pos = 0;
    if(root == NULL) return;
    BSTtoArr(root->left,arr);
    v[pos++] = root->data;
    BSTtoArr(root->right,arr);
}

我也试过

void BSTtoArr(Tree * root,Tree* arr[],int i) {
    if(root == NULL) return;
    BSTtoArr(root->left,arr,i+1);
    v[i] = root->data;
    BSTtoArr(root->right,arr,i+1);

}

但是，当我尝试调用该函数时，我无法获得添加的值

Tree* arr = (Tree*) malloc(TreeSize(root) * sizeof(Tree));
BSTtoArray(root,&arr);

值未正确添加。你能帮我实现这个功能吗？

标签： calgorithmdata-structures

解决方案

第一个问题在这里：

Tree* arr = (Tree*) malloc(TreeSize(root) * sizeof(Tree));

这为您提供了元素的“数组”，Tree但您想要的是指向元素的指针的“数组” 。Tree

所以改成：

Tree** arr = malloc(TreeSize(root) * sizeof *arr);

第二个问题在这里：

void BSTtoArr(Tree * root,Tree* arr[],int i) {
    if(root == NULL) return;
    BSTtoArr(root->left,arr,i+1);  <---- i+1
    v[i] = root->data;             <---- data ???
    BSTtoArr(root->right,arr,i+1); <---- i+1

}

您将相同的数组索引传递给左右递归，因此递归调用将写入相同的索引。您需要确保每次写入数组时都使用新的索引值。为此，您可以将指针传递给索引变量并在数组中插入新元素时更新索引。

此外，您尝试保存root->data到数组中，但数组应该保存节点 - 而不是节点数据。

要解决此问题，您可以执行以下操作：

void BSTtoArr(Tree * root, Tree* arr[], int* i) {
    if(root == NULL) return;
    BSTtoArr(root->left, arr, i);
    v[*i] = root;
    *i = *i + 1;
    BSTtoArr(root->right, arr, i);

}

并称之为：

Tree** arr = malloc(TreeSize(root) * sizeof *arr);
int i = 0;
BSTtoArray(root, arr, &i);

推荐阅读