מבוא לתכנות ולמדעי המחשב בשפת C/תרגיל 8: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
אורי מוסנזון (שיחה | תרומות) יצירת דף עם התוכן "<center> לדף הקורס </center> == תרגיל קטן על עצים בינאריים == שכתבו את ה..." |
אורי מוסנזון (שיחה | תרומות) |
||
שורה 69:
'''בהצלחה!'''
</center>
== פתרון ==
<syntaxhighlight>
#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;
}
</syntaxhighlight>
<center>
| |||