#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//structure that defines a binary search
//tree
struct BSTREE {
long long int key;
struct BSTREE *left;
struct BSTREE *right;
};
//this function returns the root of the modified tree
struct BSTREE *insert(struct BSTREE *root, long long int num){
int exit=1;
struct BSTREE *temp = root;
//if tree is empty, return new node
if (root == NULL){
struct BSTREE *newNode = malloc(sizeof(struct BSTREE));
newNode->key = num;
newNode->left = NULL;
newNode->right=NULL;
root = newNode;
return root;
}
while(exit){
if (num > temp->key)
{
//if reached end then create space
if (temp->right == NULL){
struct BSTREE *newNode = malloc(sizeof(struct BSTREE));
newNode->key = num;
newNode->left = NULL;
newNode->right=NULL;
temp->right = newNode;
exit = 0;
} else
temp = temp->right;
}
else
{
//if reached end then create space
if (temp->left == NULL){
struct BSTREE *newNode = malloc(sizeof(struct BSTREE));
newNode->key = num;
newNode->left = NULL;
newNode->right=NULL;
temp->left = newNode;
exit = 0;
} else
temp = temp->left;
}
}
return root;
}
//this function performs an inorder traversal and
//prints out to the file specified
void inorderTraversal(struct BSTREE* root, FILE *fp) {
//if not at the end of binary search tree
if (root != NULL) {
//go to left
inorderTraversal(root->left, fp);
//printing out the nodes to the file specified
fprintf(fp, "%lld\n", root->key);
//go to right
inorderTraversal(root->right, fp);
}
}
int main() {
struct BSTREE *root = NULL;
/*inserting a value
root = insert(root, 15);
root = insert(root, 800);
root = insert(root, 32);
*/
//part 2: insert numbers 1 to n into the binary search
//tree.
long long int n =50000;
//二分探索木構造は、(以下のアルゴリズムから) あまりにも多くの値を取ることができないようです。何らかの理由で、//50 000 に到達しようとするとクラッシュし続けましたが、n = 30 000 の場合など、それ以下であれば問題なく動作します。 //問題は、for ループが //数値を挿入するクロック関数の間で展開しています私は信じている。私はそれがうまく機能しているように見えることをテストしましたが、50 000に近づくにつれて//i. クラッシュするようです。構造体が // より多くの値を処理できるように十分なスペースを割り当てる方法はありますか? (最大 100 000)。挿入に関する追加のコメントは、挿入アルゴリズム自体に問題があるかどうかをテストすることでした。しかし、私はそれが事実であるとは思いませんでした。PS私はそれをIterativeに変更し、より多くの値を保持できました-最大42000-しかし、それでも必要な量を取り込むことができませんでした.
//recording the time spent to build the data structure
clock_t begin = clock();
for (long long int i = 1; i <= n; i++) {
root = insert(root, i);
if (i == 30000)
printf("reached end\n");
}
printf("done for loop\n");
clock_t end = clock();
double time_spent = (double) (end - begin) / CLOCKS_PER_SEC;
printf("The time spent building the data structure is %f\n", time_spent);
//creating the file for the sorted values
FILE *fp;
fp = fopen("sorted.txt", "w+");
//runs the inorder traversal
inorderTraversal(root, fp);
fclose(fp);
return 0;
}