-1

下面的代码读取一个输入数组，并从中构造一个 BST。如果当前 arr[i] 是树中节点的副本，则丢弃 arr[i]。struct节点中的count是指一个数字在数组中出现的次数。fi 指的是在数组中找到的元素的第一个索引。插入后，我正在对树进行后序遍历并打印数据、计数和索引（按此顺序）。运行此代码时得到的输出是：

0 0 7
0 0 6

感谢您的帮助。

吉夫

 struct node{

    int data;
    struct node *left;
    struct node *right;
    int fi;
    int count;

};

struct node* binSearchTree(int arr[], int size);
int setdata(struct node**node, int data, int index);
void insert(int data, struct node **root, int index);
void sortOnCount(struct node* root);

void main(){

    int arr[] = {2,5,2,8,5,6,8,8};
    int size = sizeof(arr)/sizeof(arr[0]);
struct node* temp = binSearchTree(arr, size);
sortOnCount(temp);

}   

struct node* binSearchTree(int arr[], int size){

    struct node* root = (struct node*)malloc(sizeof(struct node));

    if(!setdata(&root, arr[0], 0))
        fprintf(stderr, "root couldn't be initialized");

    int i = 1;
    for(;i<size;i++){
        insert(arr[i], &root, i);
    }

    return root;
}    

int  setdata(struct node** nod, int data, int index){

    if(*nod!=NULL){

    (*nod)->fi = index;
    (*nod)->left = NULL;
    (*nod)->right = NULL;
    return 1;
}
return 0;
}

void insert(int data, struct node **root, int index){

struct node* new = (struct node*)malloc(sizeof(struct node));
setdata(&new, data, index);
struct node** temp = root;

while(1){

    if(data<=(*temp)->data){
        if((*temp)->left!=NULL)
            *temp=(*temp)->left;
        else{
            (*temp)->left = new;
            break;
        }
    }
    else if(data>(*temp)->data){
        if((*temp)->right!=NULL)
            *temp=(*temp)->right;
        else{
            (*temp)->right = new;
            break;
        }
    }
    else{
        (*temp)->count++;
        free(new);
        break;
    }
}



}

void sortOnCount(struct node* root){

if(root!=NULL){

    sortOnCount(root->left);
    sortOnCount(root->right);
    printf("%d %d %d\n", (root)->data, (root)->count, (root)->fi);
}   
}
4

2 回答 2

0

在插入函数的while循环中放置一个if条件。

while(1)
{
    if(data==(*temp)->data)
          break;
    else
    {
         your stuff;
    }
}

它可能是你的答案。

于 2012-09-15T03:01:52.573 回答
0

好吧，首先，您将指针传递给插入函数中的指针：

void insert(int data, struct node **root, int index);

然后你有一个临时变量：

struct node** temp = root;

你用来遍历你的树。当你这样做时，你正在改变你的根。只需传递一个指针，即

void insert(int data, node *root , int index){

其次， if(data<=(*temp)->data){应该只是 <，而不是 <=。

提示：一般来说，当你真正需要将一个指针传递给一个指针时，这是相当罕见的。

于 2012-09-15T03:35:01.300 回答