How would you write this code in C using arrays instead-CodePudding

void storeBSTNodes(Node* root, vector<Node*> &nodes)
{
  if (root == NULL)
    return;

  storeBSTNodes(root->left, nodes);
  nodes.push_back(root);
  storeBSTNodes(root->right, nodes);
}

How would you write this code in C (it's in C format currently) using an array? This is what I've got so far, but I'm confused about the part regarding nodes.push_back(root); and root->left, nodes

void storeBSTNodes(Node* root, int arr[])
{
  if (root == NULL)
    return;

  storeBSTNodes(root->left, arr);
  ?
  storeBSTNodes(root->right, arr);
}

Code from: https://www.geeksforgeeks.org/convert-normal-bst-balanced-bst/

CodePudding user response：

The key is realloc.

But you'll soon realize that Node arr[] would have to be changed since you would need to know the existing number of elements in the array, and you would need to return the new number of elements in the array and the updated buffer pointer. Using a vector-like "class" or library would help.

Given the (untested) library below, you could use the following:

void storeBSTNodes(Node* root, Vector* nodes)
{
  if (root == NULL)
    return;

  storeBSTNodes(root->left, nodes);
  Vector_push(nodes, root);             // Ignores failures.
  storeBSTNodes(root->right, nodes);
}

Vector.h:

#ifndef VECTOR_H
#define VECTOR_H

#include <stdlib.h>

// A fixed-size circular buffer.
typedef struct {
   size_t size;
   size_t used;
   void** buf;
} Vector;

// Returns NULL and sets errno on error.
// Free the vector with Vector_delete when done.
Vector* Vector_new(void);

// Returns 0 and sets errno on error.
// Destroy the vector with Vector_destroy when done.
int Vector_init(Vector* v);

// Inverse of Vector_new.
// Only call when the vector is empty.
void Vector_delete(Vector* v);

// Inverse of Vector_init.
// Only call when the vector is empty.
void Vector_destroy(Vector* v);

int Vector_is_empty(Vector* v);

// Appends an element to the vector.
// Returns 0 and sets errno on error.
int Vector_push(Vector* v, void* ele);

// Removes the last element of the vector and returns it.
// Note that this also NULL if empty.
void* Vector_pop(Vector* v);

#endif

Vector.c:

#include <assert.h>
#include <stdlib.h>

#include "Vector.h"

Vector* Vector_new(void) {
   Vector v = malloc(sizeof(Vector));
   if (v == NULL)
      goto Error1;

   if (!Vector_init(v))
      goto Error2;

   return v;

Error2:
   free(v);
Error1:
   return NULL;
}

int Vector_init(Vector* v) {
   v->size = 0;
   v->used = 0;
   v->buf = NULL;
   return 1;
}

void Vector_delete(Vector* v) {
   Vector_destroy(v);
   free(v);
}

void Vector_destroy(Vector* v) {
   assert(v->used == 0);
   free(v->buf);
}

int Vector_is_empty(Vector* v) {
   return v->used == 0;
}

int Vector_push(Vector* v, void* ele) {
   if (v->used == v->size) {
      size_t new_size = v->size;
      new_size = new_size ? new_size * 2 : 4;

      void* new_buf = realloc(v->buf, new_size * sizeof(void*));
      if (new_buf == NULL)
         return 0;

      v->size = new_size;
      v->buf  = new_buf;
   }

   v->buf[ (v->used)   ] = ele;
   return 1;   
}

void* Vector_pop(Vector* v) {
   if (v->used == 0)
      return NULL;

   return v->buf[ --(v->used) ];
}

Add other "methods" as needed.

CodePudding user response：

Allocation of temporary storage would be more efficient if you could get the number of elements in the tree efficiently, for example by maintaining a counter. Failing that, a recursive function could be used to count the elements:

size_t CountBSTElements(Node *root) {
    if (root)
        return 1   CountBSTElements(root->left)   CountBSTElements(root->right);
    else
        return 0;
}

Once the total number of elements is known, the following function can be called to allocate an array filled with an in-order traversal of the tree:

/*
 * Allocates and fills array of node pointers from BST tree.
 * root is the root node and n is the total number of elements in the tree.
 */
Node **GetInOrderBSTNodes(Node *root, size_t n) {
    Node **nodes = malloc(n * sizeof(*nodes));
    size_t front = 0;
    size_t back = n;

    if (!nodes)
        return NULL;

    while (front < back) {
        if (root) {
            nodes[--back] = root;
            root = root->left;
        } else {
            root = nodes[back  ];
            nodes[front  ] = root;
            root = root->right;
        }
    }
    return nodes;
}

Demonstration follows. The temporary storage needs to be freed once it has been used to build the balanced tree.

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

typedef struct Node Node;

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

/*
 * Allocates and fills array of node pointers from BST tree.
 * root is the root node and n is the total number of elements in the tree.
 */
Node **GetInOrderBSTNodes(Node *root, size_t n) {
    Node **nodes = malloc(n * sizeof(*nodes));
    size_t front = 0;
    size_t back = n;

    if (!nodes)
        return NULL;

    while (front < back) {
        if (root) {
            nodes[--back] = root;
            root = root->left;
        } else {
            root = nodes[back  ];
            nodes[front  ] = root;
            root = root->right;
        }
    }
    return nodes;
}

size_t CountBSTElements(Node *root) {
    if (root)
        return 1   CountBSTElements(root->left)   CountBSTElements(root->right);
    else
        return 0;
}

/* 
 * N.B. The usage of the end index is slightly different in this version of
 * buildTreeUtil() compared to the linked source:
 * https://www.geeksforgeeks.org/convert-normal-bst-balanced-bst/
 *
 * In this version, end is one past the last index.
 * I did it this way to keep the indices unsigned.
 */

/*
 * Build BST from array of node pointers.
 * nodes is the array of node pointers.
 * start is start index in the array.
 * end is one past the end index in the array.
 *
 * Sorry, it is recursive. :-)
 */
Node *BuildTreeUtil(Node **nodes, size_t start, size_t end)
{
    Node *root;
    size_t mid;

    if (start >= end)
        return NULL;

    mid = (start   end - 1) / 2;
    root = nodes[mid];
    root->left = BuildTreeUtil(nodes, start, mid);
    root->right = BuildTreeUtil(nodes, mid   1, end);
    return root;
}

Node *BuildTree(Node *root, size_t nelems) {
    Node **nodes = GetInOrderBSTNodes(root, nelems);
 
    if (nodes) {
        /* Build BST from in-order node pointers. */
        root = BuildTreeUtil(nodes, 0, nelems);
        /* Free temporary storage. */
        free(nodes);
    } /* else leave it unbalanced */

    return root;
}

/* Utility function to create a new node */
/* Borrowed from linked source. */
Node *NewNode(int data) {
    Node *node = malloc(sizeof(*node));

    if (node) {
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    return (node);
}

/* Print in-order traversal of BST. */
/* Borrowed from linked source, but renamed. */
void PrintPreOrder(Node* node)
{
    if (node == NULL)
        return;
    printf("%d ", node->data);
    PrintPreOrder(node->left);
    PrintPreOrder(node->right);
}

int main(void) {
    Node *root;
    size_t count;

    /*
     * Construct unbalanced BST:
     *
     *         4
     *        / \ 
     *       3   5
     *      /     \ 
     *     2       6
     *    /         \ 
     *   1           7
     */
    root = NewNode(4);
    root->left = NewNode(3);
    root->left->left = NewNode(2);
    root->left->left->left = NewNode(1);
    root->right = NewNode(5);
    root->right->right = NewNode(6);
    root->right->right->right = NewNode(7);

    printf("Pre-order traversal of unbalanced BST is:\n");
    PrintPreOrder(root);
    printf("\n");

    /* Get number of nodes. */
#if 0
    count = 7;  /* efficient :-) */
#else
    count = CountBSTElements(root);
#endif

    /*
     * Build balanced BST:
     *
     *         4
     *       /   \ 
     *      2     6
     *     / \   / \ 
     *    1   3 5   7
     */
    root = BuildTree(root, count);

    printf("Pre-order traversal of balanced BST is:\n");
    PrintPreOrder(root);
    printf("\n");

    return 0;
}