Opgave 12.7 Højde-funktion af binært træ

Højden af et binært træ defineres som højden af træets rod.

Højden af en knude K i træet er den længste sti fra K til et blad. Med dette bliver højden af et blad altså 0.

Skriv en funktion i C der beregner højden af et træ. Udgangspunktet (parameteren) skal være en pointer til en knude i træet. Afprøv funktionen på forskellige træer.

Her er et godt udgangspunkt for denne opgave - dog givet i kontekst af binære søgetræer - og svarende til de programmer der er diskuteret i lektionsvideoen.

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

struct tree_node{
  int key;
  struct tree_node *leftp, *rightp;
};

typedef struct tree_node tree_node;

tree_node *make_tree(int key, tree_node *left, tree_node *right);
void assert_allocation_success(void *alloc_pointer);
tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e);
void print_tree(tree_node *tree_ptr);
void print_tree_helper(tree_node *tree_ptr, int level);
int tree_height(tree_node *tree_ptr);

int main(void) {

  tree_node *tree4 = NULL;
  tree4 = insert_in_binary_search_tree(tree4, 6);
  tree4 = insert_in_binary_search_tree(tree4, 2);
  tree4 = insert_in_binary_search_tree(tree4, 1);
  tree4 = insert_in_binary_search_tree(tree4, 4);
  tree4 = insert_in_binary_search_tree(tree4, 3);
  tree4 = insert_in_binary_search_tree(tree4, 5);
  tree4 = insert_in_binary_search_tree(tree4, 7);
  tree4 = insert_in_binary_search_tree(tree4, 9);
  tree4 = insert_in_binary_search_tree(tree4, 8);

  printf("tree4:\n");
  print_tree(tree4);

  exit(EXIT_FAILURE);
}


tree_node *make_tree(int key, tree_node *left, tree_node *right){
  tree_node *the_tree = malloc(sizeof(tree_node));
  assert_allocation_success(the_tree);
  the_tree->key = key; 
  the_tree->leftp = left; 
  the_tree->rightp = right; 
  return the_tree;
} 

void assert_allocation_success(void *alloc_pointer){
  if (alloc_pointer == NULL){
    printf("Allocation problems. Your program stops.");
    exit(EXIT_FAILURE);
  }
}

/* Insert the element e i the binary search tree, designated by tree_ptr. 
   Drop the insertion if e is already in the tree. 
   Return the tree  in terms of a pointer to its root node. */
tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e){
  if (tree_ptr == NULL){
    /* Make a small tree rooted with e and empty subtrees */
    /* This branch is never reached via recursion */
    tree_node *the_tree = make_tree(e, NULL, NULL);
    return the_tree;
  }
  else if (e == tree_ptr->key){
    /* Do nothing */
    return tree_ptr;
  }
  else if (e < tree_ptr->key && tree_ptr->leftp == NULL){
    tree_node *the_tree = make_tree(e, NULL, NULL);
    tree_ptr->leftp = the_tree;
    return tree_ptr;         
  }
  else if (e < tree_ptr->key){
    insert_in_binary_search_tree(tree_ptr->leftp, e);
    return tree_ptr;
  }
  else if (e > tree_ptr->key && tree_ptr->rightp == NULL){
    tree_node *the_tree = make_tree(e, NULL, NULL);
    tree_ptr->rightp = the_tree;
    return tree_ptr;         
  }
  else { /* e > tree_ptr->key) */
    insert_in_binary_search_tree(tree_ptr->rightp, e);
    return tree_ptr;
  }
}

void print_tree(tree_node *tree_ptr){
  print_tree_helper(tree_ptr, 0);
}    

/* print the tree designated by tree_ptr as horizotally, as an indented text, on standard output.
   Empty subtrees are printed as "." if tree_ptr is passsed as NULL */
void print_tree_helper(tree_node *tree_ptr, int level){
  int i; 

  /* print indented root */
  for(i = 0; i < level; ++i) 
    printf("   ");
  if (tree_ptr == NULL)
    printf(".\n");  /* Missing part */
  else
    printf("%d\n", tree_ptr->key);

  if(tree_ptr != NULL){
    /* print branches */
    if (tree_ptr->leftp == NULL && tree_ptr->rightp == NULL){
      /* print nothing */
    }
    else if (tree_ptr->leftp != NULL && tree_ptr->rightp == NULL){
      print_tree_helper(tree_ptr->leftp, level+1);
      print_tree_helper(NULL, level+1);
    }   
    else if (tree_ptr->leftp == NULL && tree_ptr->rightp != NULL){
      print_tree_helper(NULL, level+1);
      print_tree_helper(tree_ptr->rightp, level+1);
    }
    else {  
      print_tree_helper(tree_ptr->leftp, level+1);
      print_tree_helper(tree_ptr->rightp, level+1);
    }
  }
}


/* Opgave */
int tree_height(tree_node *tree_ptr){
  return 0;
}