c - 将节点从 BST 保存到一定范围内的向量

Question

程序要做的事情：给定一个 BST / 2 个数字 k1 和 k2 / 一个数组 []，我必须将所有 k1<=node_value<=k2 的节点按升序插入向量中。示例：节点：Vector[] 内的节点：1 2 3 4 5 6 K1=2 K2=6 我应该按照这个特定的顺序有数字 2 3 4 5 6，我必须计算这个数字。我的函数必须返回保存在向量中的数字（在这种情况下：5，因为我在向量中保存了 5 个数字）。

该函数必须是递归的并且必须是高效的。

我的问题：我不知道如何按升序将节点的值插入向量内。

如果有人可以帮助我将是不可思议的。先感谢您。我会把整个代码放好，所以如果有人想编译你可以做。给我带来问题的函数是第一个函数：RANGE。在此处输入代码

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

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

typedef struct tree{
    Node root;
}* Tree;

int range(Node u, int k1, int k2, int v[]){

    int rissx;
    int risdx;
  int i=0;

    if(k1>k2)
        return 0;

    if(u==NULL)
        return 0;
  rissx=range(u->left,k1,k2,&v[i+1]); 
  risdx=range(u->right,k1,k2,&v[i+1]);

    if((k1<=u->key) && (u->key<=k2)){
     v[i]=u->key; 
     return rissx+risdx+1;
  }

  return rissx+risdx;
}

/*create a new tree*/
Tree newtree(){
    Tree new = (Tree) malloc(sizeof(struct tree));
    return new;
}

/*create a new node;*/
Node create_node(int data)
{
    Node new_node = (Node)malloc(sizeof(struct node));
    new_node->key   = data;
    new_node->left  = NULL;
    new_node->right = NULL;
    new_node->p     = NULL;

    return new_node;
}

int treeempty(Tree t){
    Node u=t->root;
    if(u==NULL)
        return 0;
    else
    {
        return 1;
    }
}

void treeinsert(Tree t, Node z){
  Node y=NULL;
  Node x=t->root;

  while(x!=NULL){
    y=x;
    if(z->key<x->key)
      x=x->left;
    else
      x=x->right;

    z->p=y;
    if(y==NULL)
      t->root=z;
    else
    {
      if(y->key>z->key)
        y->left=z;
      else
      {
        y->right=z;
      }
    }
  }
}

Node tree_minimun(Node x){
  while(x->left){
    x = x->left;
  }
  return x;
}

Node tree_maximun(Node x){
  while(x->right){
    x = x->right;
  }
  return x;
}

Node tree_succ(Node x){
  if(x->right){
    return tree_minimun(x->right);
  }
  else{
    Node y;
    y=x->p;
    while(y && y->right==x){
      x=y;
      y=y->p;
    }
    return y;
  }
}
void printInorder(Node n) 
{ 
    if (n == NULL) 
        return; 

    /* first recur on left child */
    printInorder(n->left); 

    /* then print the data of node */
    printf("%d",n->key);

    /* now recur on right child */
    printInorder(n->right); 
} 
Node TreeBuiltAux(int vettore[],int inf,int sup,Node padre){

    int med=(inf+sup)/2;

    Node root;

    if(inf>sup)
      return NULL;

    root=create_node(vettore[med]);
    root->p=padre;
    root->left=TreeBuiltAux(vettore,inf,med-1,root);
    root->right=TreeBuiltAux(vettore,med+1,sup,root);

    return root;
}

Tree TreeBuilt(int vettore[],int dimensione){
  Tree t = newtree();
  t->root=  TreeBuiltAux(vettore,0,dimensione,NULL);
  return t;
}

int main(){
    int vettore[]={1,3,4,5,6,7,9,10};
    int dimension=8;
    int vettore2[9];
    int dimension2= sizeof(vettore2)/sizeof(vettore2[0]);
    int i;

    Tree t=newtree();
      for(i=0;i<dimension2;i++){
      vettore2[i]=0;
    }
    printf("TreeEmpty Function result %d\n",treeempty(t));
    printf("Creating the BST\n");
    t = TreeBuilt(vettore,dimension-1);
    printf("TreeEmpty Function result after the creation of the tree %d\n",treeempty(t));
    printInorder(t->root);
    printf("\n");

    printf("Risult of the function range è : %d ----- k1 : %d and k2 : %d\n",range(t->root,1,5,vettore2),1,5);
    printf("----------------------------------------------------------------\n");
    for(i=0;i<dimension2;i++){
      printf("%d\n",vettore2[i]);
    }
    printf("\n");
    return 0;

}

标签： cvectorbinary-search-tree