מבוא לתכנות ולמדעי המחשב בשפת C/מבני נתונים דינמיים - עצים בינאריים

עצים בינאריים

עץ בינארי הוא מבנה נתונים דינאמי הבנוי מקודקודים בעלי שני מצביעים לקודקודים מאותו הסוג. נהוג לקרוא לאחד מהקודקודים המוצבעים "בן שמאלי" ולשני "בן ימני". נהוג גם לקרוא לקודקוד הראשון, זה שאין קודקוד שמצביע עליו, "השורש" של העץ ולקודקדים שאינם מצביעים על קודקודים נוספים "העלים", של העץ.

עץ בינארי ממויין הוא עץ בינארי שקודקודיו מכילים ערכים ומתקיים: לכל קודקוד בעץ, תת העץ ששורשו הוא "הבן שמאלי" של הקודקוד מכיל ערכים קטנים מזה של הקודקוד ותת העץ ששורשו "הבן הימני" מכיל ערכים גדולים או שווים לזה שבקודקוד.

נצהיר על טיפוס קודקוד של עץ המחזיק int:

typedef struct Node {
    int data; 
    struct Node *ls, *rs; 
} Node;

הקוד הבא מדגים מימוש של עץ בינארי ממויין. בנוסף, הקוד מכיל פונקציה לחיפוש ערך מסויים בעץ, פונקציה המחשבת את גובהו ופונקציה הסופרת כמה קודקודים יש בו. גובה עץ מוגדר כאורך המקסימאלי של מסלול מהשורש עד אחד העלים.

#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct Node {
    int data; 
    struct Node *ls, *rs; 
} Node; 
 
Node* newNode(int data) {
    Node *p = (Node*) malloc (sizeof(Node)); 
    p->data = data; 
    p->ls = p->rs = NULL; 
    return p; 
}
 
/*
void insert(Node **root, int data) {
// insert using recursion 
    if(! *root) {
	*root = newNode(data); 
	return; 
    }
    if(data < (*root)->data)
	insert( &((*root)->ls),data); 
    else 
	insert( &((*root)->rs),data); 
 
}
*/

/* 
void insert(Node **root, int data) {
// insert using a loop and pointer to pointer 
    while(*root) {
	if(data < (*root)->data)
	    root = &( (*root)->ls); 
	else
	    root = &( (*root)->rs); 
    }
    *root = newNode(data); 
}
*/

void insert(Node **root, int data) {
  // insert using loop and a regular pointer 
  if(! *root) {
    *root = newNode(data); 
    return; 
  }
  Node *p = *root; 
  while(1) {
    if(data < p->data) {
      if(p->ls == NULL) {
	p->ls = newNode(data); 
	return; 
      } 
      p = p->ls; 
    } else {
      if(p->rs == NULL) {
	p->rs = newNode(data); 
	return; 
      } 
      p = p->rs; 
    }
  }
}

int max(int a, int b) {
    if(a > b)
	return a; 
    return b; 
}
 
int treeHeight(Node *root) {
    if(!root)
	return -1; 
    return max( treeHeight(root->ls), treeHeight(root->rs) )+1; 
}
 
int numOfNodes(Node *root) {
    if(!root)
	return 0; 
    return numOfNodes(root->ls) + numOfNodes(root->rs) + 1; 
}
 
void printTreeRec(Node *root) {
    if(!root) {
	printf("NULL");
	return; 
    }
 
    printf("(");
    printTreeRec(root->ls);
    printf(",%d,",root->data); 
    printTreeRec(root->rs);
    printf(")"); 
}
 
void printTree(Node *root) {
    printTreeRec(root);
    printf("\n"); 
}
 
void freeTree(Node *root) {
    if(!root)
	return; 
    freeTree(root->ls);
    freeTree(root->rs); 
    free(root); 
}
 
int isIn(Node *root, int data) {
    Node *p = root; 
    while(p) {
	if(data == p->data)
	    return 1; 
	if(data < p->data)
	    p = p->ls; 
	else
	    p = p->rs; 
    }
    return 0; 
}
 
int main() {
    int array[] = {5,3,8,1,4,9}; 
    int N = sizeof(array)/sizeof(int); 
 
    Node *root = NULL; 
    int i; 
    for(i=0; i<N; ++i)
	insert(&root,array[i]);
 
    printTree(root);
 
    for(i=1; i<=10; ++i)
	if(isIn(root,i))
	    printf("%d is in the tree.\n",i); 
 
 
    printf("Tree Height: %d\n", treeHeight(root)); 
 
    printf("Number of nodes: %d \n", numOfNodes(root)); 
    freeTree(root); 
 
    return 0;
}

תבנית:ניווט מבוא