Software 1 - Structures (9)

administrivia

Web Page - http://www.cs.tau.ac.il/~efif/courses/Software1_Spring_04

A thief with a key is still a thief

• Don't reference freed memory

  while (ptr != NULL) { free(ptr); ptr = ptr->next; }

User defined data structure

• struct - basic user-defined data type in C

• typedef struct node { struct node * right; struct node * left; int value; } Node;

• The following are equivalent

  node_ptr->value;

  <=>

  (*node_ptr).value;

Operations on structures

• define structures
• declare variables of structure type
• assign entire structures

  node1 = node2;

• pass structures as arguments to functions
• declare and define functions which return structures
• initialize a structure variable - comma-separated list of values enclosed in braces {}

  Node node = {NULL, NULL, 0};

Node allocation and initialization

• Allocates a new node and initialize it

  Node *create_node(int value) { Node * tmp = (Node *) malloc(sizeof(Node)); if (!tmp) { fprintf(stderr, "ERROR: not enough memory!\n"); return NULL; } tmp->left = tmp->right = NULL; tmp->value = value; return tmp; }

Print Values

• Print the tree pointed by root in ascending order

  void print_tree(Node *root) { if (!root) return; print_tree(root->left); printf("%d ", root->value); print_tree(root->right); }

Insertion

• Inserts a given value into a tree pointed by root

  Node * insert(Node * root, int value) { Node * parent; Node * child; Node * new_node; new_node = create_node(value); if (!new_node) return NULL; if (!root) return new_node; child = root; while (child) { parent = child; if (child->value > value) child = child->left; else child = child->right; } if (parent->value > value) parent->left = new_node; else parent->right = new_node; return root; }

Simple Binary Tree

• simple_btree.c

Function Pointer

• pointers to functions

  typedef void(Op)(void *);

Traversal

• Traverses the tree in left, middle, then right order

  void traverse_tree(Node * root, Op * op) { if (!root) return; traverse_tree(root->left, op); op((void *)root->value); traverse_tree(root->right, op); }

• Prints the value of a node

  void print_node(void * value) { printf("%d ", (int) value); }

• Usage:

  traverse_tree(root, print_node);

Binary Tree

• btree.h
• btree.c
• main.c