מבוא לתכנות ולמדעי המחשב בשפת C/תרגיל 8: הבדלים בין גרסאות בדף
מ 3 גרסאות |
מ Illuyanka העביר את הדף מבוא למדעי המחשב ב-C/מבוא לתכנות/תרגיל 8 ל־מבוא לתכנות ולמדעי המחשב/ תרגיל 8 בלי להשאיר הפניה |
(אין הבדלים)
|
גרסה מ־20:28, 31 באוקטובר 2012
תרגיל קטן על עצים בינאריים
שכתבו את הקוד של עץ החיפוש הבינארי משיעור 15 כך שישתמש בטיפוס המייצג את העץ כולו. בדומה לשכתוב שעשינו לרשימה המשורשרת בשיעור 16, הטיפוס המייצג את העץ יכיל גם שדה המחזיק את מספר הקודקודים בעץ.
בנוסף, עליכם להוסיף פונקציה הסופרת את מספר העלים בעץ. כזכור, עלים הם קודקודים שאינם מצביעים על קודקדים אחרים.
עליכם להוסיף לקוד הבא את כל הפונקציות הדרושות בהן משתמשת הפונקציה main:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *ls,*rs;
} Node;
typedef struct Tree {
Node *root;
int size;
} Tree;
//...
int main() {
int array[] = {5,3,8,1,4,9,100,50,21,67,78};
int N = sizeof(array)/sizeof(int);
Tree *tree = newTree();
int i;
for(i=0; i<N; ++i)
insert(tree, array[i]);
printTree(tree);
printf("Number of nodes: %d \n",tree->size);
printf("\nNumber of leaves: %d \n",numOfLeaves(tree));
freeTree(tree);
return 0;
}
הפלט שלו אמור להיות:
(((NULL,1,NULL),3,(NULL,4,NULL)),5,(NULL,8,(NULL,9,(((NULL,21,NULL),50,(NULL,67,(NULL,78,NULL))),100,NULL))))
Number of nodes: 11
Number of leaves: 4
הגשה
מועד הגשה: יום חמישי ה - 19.1.12, עד סוף היום.
יש להגיש ב"תרגיל שמיני" במודל קובץ בודד בשם q1.c המכיל את הקוד הדרוש. אין צורך בקובץ tgz.
בהצלחה!
פתרון
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *ls,*rs;
} Node;
typedef struct Tree {
Node *root;
int size;
} Tree;
Tree* newTree() {
Tree *p = (Tree*) malloc (sizeof(Tree));
p->root = NULL;
p->size = 0;
return p;
}
Node* newNode(int data) {
Node *p = (Node*) malloc (sizeof(Node));
p->data = data;
p->ls = p->rs = NULL;
return p;
}
void insert(Tree *tree, int data) {
Node **root = & tree->root;
while(*root) {
if(data < (*root)->data)
root = &( (*root)->ls);
else
root = &( (*root)->rs);
}
*root = newNode(data);
++ tree->size;
}
void printTreeRec(Node *root) {
if(!root) {
printf("NULL");
return;
}
printf("(");
printTreeRec(root->ls);
printf(",%d,",root->data);
printTreeRec(root->rs);
printf(")");
}
void printTree(Tree *tree) {
printTreeRec(tree->root);
printf("\n");
}
void freeTreeRec(Node *root) {
if(!root)
return;
freeTreeRec(root->ls);
freeTreeRec(root->rs);
free(root);
}
void freeTree(Tree *tree) {
freeTreeRec(tree->root);
free(tree);
}
int numOfLeavesRec(Node *p) {
if(!p)
return 0;
int tmp = numOfLeavesRec(p->ls)+numOfLeavesRec(p->rs);
if(tmp == 0)
return 1;
return tmp;
}
int numOfLeaves(Tree *tree) {
return numOfLeavesRec(tree->root);
}
int main() {
int array[] = {5,3,8,1,4,9,100,50,21,67,78};
int N = sizeof(array)/sizeof(int);
Tree *tree = newTree();
int i;
for(i=0; i<N; ++i)
insert(tree, array[i]);
printTree(tree);
printf("Number of nodes: %d \n",tree->size);
printf("\nNumber of leaves: %d \n",numOfLeaves(tree));
freeTree(tree);
return 0;
}