/* * File: tree6.c * Creator: George Ferguson * * Sixth version of the binary tree program. * Uses typedef to get rid of all the explicit pointers. * Like it or not, it does make the program look an awful lot like Java. */ #include #include typedef struct Node* Node; struct Node { int value; Node leftChild; Node rightChild; }; Node new_Node(int value) { Node this = (Node)malloc(sizeof(struct Node)); if (this == NULL) { return NULL; // Out of memory... } this->value = value; this->leftChild = NULL; this->rightChild = NULL; return this; } void Node_print(Node this) { if (this != NULL) { Node_print(this->leftChild); printf("%d\n", this->value); Node_print(this->rightChild); } } Node Node_add(Node this, int value) { if (this == NULL) { return new_Node(value); } else if (value < this->value) { this->leftChild = Node_add(this->leftChild, value); } else if (value > this->value) { this->rightChild = Node_add(this->rightChild, value); } else { // Already in tree: ignore (or you could do something else) } return this; } int Node_find(Node this, int value) { if (this == NULL) { return 0; } else if (value < this->value) { return Node_find(this->leftChild, value); } else if (value > this->value) { return Node_find(this->rightChild, value); } else { return 1; // value == this->value } } void Node_walk(Node this, void (*callback)(int)) { if (this != NULL) { Node_walk(this->leftChild, callback); (*callback)(this->value); Node_walk(this->rightChild, callback); } } typedef struct Tree* Tree; struct Tree { Node root; }; Tree new_Tree() { Tree this = (Tree)malloc(sizeof(struct Tree)); if (this == NULL) { return NULL; // Out of memory... } this->root = NULL; return this; } void Tree_add(Tree this, int value) { this->root = Node_add(this->root, value); } void Tree_print(Tree this) { Node_print(this->root); } int Tree_find(Tree this, int value) { return Node_find(this->root, value); } void Tree_walk(Tree this, void (*callback)(int)) { Node_walk(this->root, callback); } void myCallback(int value) { printf("%d\n", value); } int main(int argc, char* argv[]) { Tree tree = new_Tree(); Tree_add(tree, 20); Tree_add(tree, 10); Tree_add(tree, 5); Tree_add(tree, 15); Tree_add(tree, 30); Tree_add(tree, 40); Tree_add(tree, 20); Tree_walk(tree, myCallback); }