二叉搜索树算法 returns 一个范围内的值数组

Question

写一个递归范围函数给定一个二叉搜索树，两个整数 k1 和 k2 使得 k1 ≤ k2 和一个向量 v，插入 v所有键按升序排列在树中，使得 k1 ≤ k ≤ k2 。函数returns向量v的大小

这是我的解决方案：

typedef struct node {
  int key;
  struct node * left;
  struct node * right;
  struct node * parent;
} * Node;

void rangeRic(Node u, int k1, int k2, int v[], int * pindex) {
  if (u == NULL) {
    return;
  }

  rangeRic(u->left,k1,k2,v,pindex);

  if (u->key >= k1 && u->key <= k2) {
    v[*pindex] = u->key;
    *pindex += 1;
  }

  rangeRic(u->right,k1,k2,v,pindex);
}

int range(Node u, int k1, int k2, int v[]) {
  int i = 0;
  rangeRic(u,k1,k2,v,&i);
  return i;
}

我的问题是练习描述中还指出了以下内容：

不能使用任何辅助函数，向量v已经足够 space包含所有满足条件的元素。

最后一条语句使我的解决方案无效。

如何编译： gcc -std=gnu89 -pedantic -Wall -o main main.c binarySearchTree.c

你们能帮我解决这个问题吗？

Answer 1

您可以return从每个节点添加了多少项并将其用作数组的索引。

int range(Node u, int k1, int k2, int v[]) {
  if (u == NULL) {
    return 0;
  }

  // Will return how many items added from the left side
  int count = range(u->left, k1, k2, v);

  if (u->key >= k1 && u->key <= k2) {
    // Add and increment counter
    v[count++] = u->key;
  }

  // Add how many from the right side
  // Note: passing the last part of the array
  // Could also write v+count as &v[count]
  return count + range(u->right, k1, k2, v + count);
}

二叉搜索树算法 returns 一个范围内的值数组

Binary Search Tree algorithm which returns an array of value within a range

c

function

recursion

binary-search-tree

definition