Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
355 views
in Technique[技术] by (71.8m points)

algorithm - Making a void toBST function in C which takes 2 arguments : Tree* root and an array and adds all tree nodes to an array - order does not matter

I am trying to implement the following function in C :

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

which takes a tree and add its nodes into an array of nodes. What I ve written so far was :

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);
}

I also tried

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);

}

However I can not get the values added , when I am trying to call the function

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

The values are not added properly. Can you help me with an implementation for this function?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

The first problem is here:

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

This gives you "an array" of Tree elements but what you want is "an array" of pointers to Tree elements.

So change it to:

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

The second problem is here:

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

}

You pass the same array index to the left and the right recursion so the recursive calls will write to the same index. You need to make sure that every time you write to the array, it's done with a new index value. To do that you can pass a pointer to the index variable and update the index when a new element is inserted in the array.

Further, you to try to save root->data into the array but the array is supposed to hold the nodes - not the node data.

To solve this you can do:

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);

}

and call it like:

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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...