Created by JUNHWI KIM 2017-06-08

tree.c

      /*
Example of Binary Tree from 

Ellis Horowitz, et al. 
Fundamentals of data structures in C. 
2nd ed., Silicon Press, 2008, pp. 204-205.

Written by Junhwi Kim <junhwi.kim23@gmail.com>
*/

#define MAX_STACK_SIZE 100
#define MAX_QUEUE_SIZE 100

#include <stdio.h>
#include <stdlib.h>

typedef struct node *tree_pointer;
typedef struct node {
    int data;
    tree_pointer left_child, right_child;
};

void inorder (tree_pointer ptr)
/* inorder tree traversal */
{
  if (ptr) {
    inorder(ptr->left_child);
    printf("%d", ptr->data);
    inorder(ptr->right_child);
  }
}

void preorder (tree_pointer ptr)
/* preorder tree traversal */
{
  if (ptr) {
    printf("%d", ptr->data);
    inorder(ptr->left_child);
    inorder(ptr->right_child);
  }
}

void postorder (tree_pointer ptr)
/* postorder tree traversal */
{
  if (ptr) {
    inorder(ptr->left_child);
    inorder(ptr->right_child);
    printf("%d", ptr->data);
  }
}

void iter_inorder(tree_pointer node)
{
  int top = 0;
  tree_pointer stack[MAX_STACK_SIZE];
  for (;;) {
    for(; node; node = node->left_child) {
      stack[++top] = node;
    }
    node = stack[top--];
    if (!node) break;
    printf("%d", node->data);
    node = node->right_child;
  }
}

void level_order(tree_pointer ptr)
/* level order tree traversal */
{
  int front = 0;
  int rear = 0;
  tree_pointer queue[MAX_QUEUE_SIZE];
  if (!ptr) return;
  queue[++rear] = ptr;
  for (;;) {
    ptr = queue[++front];
    if (ptr) {
      printf("%d", ptr->data);
      if(ptr->left_child)
        queue[++rear] = ptr->left_child;
      if(ptr->right_child)
        queue[++rear] = ptr->right_child;
    }
    else break;
  }
}

tree_pointer search(tree_pointer root, int key)
/* return a pointer to the element whose key is k,
if there is no such element, return NULL. */
{
  if (!root) return NULL;
  if (key == root->data) return root;
  if (key < root->data)
    return search(root->left_child, key);
  return search(root->right_child, key);
}

tree_pointer iter_search(tree_pointer tree, int k)
{
  while (tree) {
    if (k == tree->data) return tree;
    if (k < tree->data)
      tree = tree->left_child;
    else
      tree = tree->right_child;
  }
  return NULL;
}

    

Comments (4)

HTTPS

SSH

You can clone a snippet to your computer for local editing. Learn more.