Tuesday, May 26, 2015

Upward Accumulation dengan bst

Saya memiliki data sebagai berikut :
1000 0    0
1100 1000 0
1110 1100 0
1111 1110 100
1112 1110 100
1200 1000 0
1210 1200 0
1211 1210 200
1212 1210 200
1220 1200 0
1221 1220 10
1222 1220 10
1223 1220 10
1224 1220 10
1300 1000 0
1310 1300 300
diakumulasi menjadi
 1310  1300 300
 1300  1000 300
 1224  1220 10
 1223  1220 10
 1222  1220 10
 1221  1220 10
 1220  1200 40
 1212  1210 200
 1211  1210 200
 1210  1200 400
 1200  1000 440
 1112  1110 100
 1111  1110 100
 1110  1100 200
 1100  1000 200
 1000     0 940
bagaimanakah caranya ??. Saya membuat program pendek sebagai berikut :
/*
Copyright [2015] [Joko Adianto]

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

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

void PostorderAkumulasi(Node *root, Node* r);
Node* SearchV(Node* root,int data, int v);
Node* Insert(Node *root,Node *data);
void postOrder(Node *root,FILE *fptr);

void postOrder(Node *root,FILE *fptr){
    if(root == NULL) return;
    postOrder(root->left,fptr);
    postOrder(root->right,fptr);
    printf("%d %d %d \n",root->key,root->parent,root->value);
    fprintf(fptr,"%5d %5d %d\n",root->key,root->parent,root->value); //print di berkas kedua
}

void PostorderAkumulasi(Node *root, Node* r) {
    if(root == NULL) return;

    Node* p=NULL;
    PostorderAkumulasi(root->left, r);
    PostorderAkumulasi(root->right, r);

    if (root->value!=0){
        SearchV(r, root->parent, root->value);
        }

    printf("key : %5d parent : %5d value : %5d\n",
            root->key, root->parent, root->value);  //Print data di layar
}

Node* SearchV(Node* root,int key, int v) {
if(root == NULL) {
    return NULL;
    }
else if(root->key == key) {
    root->value= root->value + v;
    return root;
    }
else if(key <= root->key) {
    return SearchV(root->left,key, v);
    }
else {
    return SearchV(root->right,key, v);
    }
}

Node* Insert(Node *root,Node *data) {
    if(root == NULL) {
        root = (Node*) malloc(sizeof(Node));
        root->key = data->key;
        root->parent=data->parent;
        root->value=data->value;
        root->left = root->right = NULL;
    }
    else if(data->key <= root->key)
        root->left = Insert(root->left,data);
    else
        root->right = Insert(root->right,data);
    return root;
}

int main(){
    Node data;
    Node* root = NULL;
    int t=1;
    printf("Membaca File : filedata \n");
    FILE* fptr = fopen("filedata.txt", "r");
    if (fptr == NULL)
        {
           printf("Tidak dapat dibuka");
           return 0;
        }
    fscanf(fptr, "%d%d%d", &data.key, &data.parent, &data.value);
    while(!feof(fptr)){
        printf("key : %5d parent : %5d value : %5d\n", data.key, data.parent, data.value);
        root=Insert(root, &data);
        fscanf(fptr, "%d%d%d", &data.key, &data.parent, &data.value);
    }
    printf("Postorder Akumulasi: \n");
    PostorderAkumulasi(root, root);
    fclose(fptr);
    fptr = fopen("hasilAkumulasi.txt","w");
    postOrder(root,fptr);
    fclose(fptr);
    return 0;
}