מבוא לתכנות ולמדעי המחשב בשפת C/תרגיל 8

לדף הקורס

תרגיל קטן על עצים בינאריים

שכתבו את הקוד של עץ החיפוש הבינארי משיעור 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; 
}

לדף הקורס