tpop(2.8): Trees

2.8 Trees

A tree is a hierarchical data structure that stores a set of items in which each item has a value, may point to zero or more others, and is pointed to by exactly one other. The root of the tree is the sole exception; no item points to it.

Binary search trees have tow links at each node. They're the easiest to implement, and demonstrate the essential properties of trees. A node in a binary search tree has a value and two pointers, left and right, that point to its children. The child pointers may be two null if the node has fewer than two children. In a binary search tree, the values at the nodes define the tree: all children to the left of a particular node have lower values, and all children to the right have higher values.

Because of this property, we can use a variant of binary search to search the tree quickly for a specific value or determine that it is not present.

/**
  tpop(2.8)Algorithm and Data Structure: Trees
  created on Jul 9, 2011
  */


 #include <stdio.h>

typedef struct Nameval Nameval;
struct Nameval {
    char *name;
    int value;
    Nameval *left; /* lesser */
    Nameval *right; /* greater */
};


/* newitem: */
Nameval *newitem(char *name, int value) {
    Nameval *newp;
    newp = (Nameval*)malloc(sizeof(Nameval));
    newp->name = name;
    newp->value = value;
    newp->left = NULL;
    newp->right = NULL;
    return newp;
}

/* insert: insert newp in treep, return treep */
Nameval *insert(Nameval *treep, Nameval *newp) {
    int cmp;

    if(treep == NULL)
      return newp;
    cmp = strcmp(newp->name, treep->name);
    if (cmp == 0)
      printf("insert: duplicate entry %s ignored", newp->name);
    else if (cmp < 0)
      treep->left = insert(treep->left, newp);
    else
      treep->right = insert(treep->right, newp);
    return treep;
}

/* lookup: look up name in tree treep */
Nameval *lookup(Nameval *treep, char *name)
{
    int cmp;

    if (treep == NULL)
      return NULL;
    cmp = strcmp(name, treep->name);
    if (cmp == 0)
      return treep;
    else if (cmp < 0)
      return lookup(treep->left, name);
    else
      return lookup(treep->right, name);
}

/* nrlookup: non-recursively look up name in tree treep */
Nameval *nrlookup(Nameval *treep, char *name)
{
    int cmp;
    while (treep != NULL) {
    cmp = strcmp(name, treep->name);
    if (cmp == 0)
      return treep;
    else if (cmp < 0)
      treep = treep->left;
    else
      treep = treep->right;
    }
    return NULL;
}

/* applyinorder: inorder application of fn to treep
 typical use: applyinorder(treep, printnv, "%s: %x\n");*/
void applyinorder(Nameval *treep,
        void (*fn)(Nameval*, void*), void *arg){
    if (treep == NULL)
      return;
    applyinorder(treep->left, fn, arg);
    (*fn)(treep, arg);
    applyinorder(treep->right, fn, arg);
}

int main(int argc, char* argv[]) {
    Nameval *nt = newitem("smiley", 0x263A);
    Nameval *rc = newitem("zeta", 0x03b6);
    Nameval *lc = newitem("Aacute", 0x00c1);
    nt = insert(nt, lc);
    nt = insert(nt, rc);
    Nameval *look = lookup(nt, "zeta");
     printf("The look result is %s\n", look->name);
    if (nt->left == NULL)
       printf("The right child  is %s\n", nt->right->name);
    else
      printf("The left child is %s\n", nt->left->name);
}