Lecture 16

A doubly linked list

This type of linked list contains links going backwards and forwards.

A doubly linked list allows items to be added and removed from the start and the end of the list.

Trees

A tree is a data structure in which items are organised in a hierarchy. An item in a tree is called a node. Trees are usually draw 'upside down' with the branches at the bottom. The top of the tree is called the root node.

Each node (except the root node) has only one node that it is connected to above it - its parent . A node can have any number of nodes connected below it - its children.

A node has one parent and zero or more children. Each node will be the root of a tree comprising all the nodes below it, this is called a subtree.

A tree in which a node may have many children is difficult to implement - each node must store a list of its children. A special case of a tree is a Binary Tree (this is not the same as a B-tree) - each node may have up to two children. The two children for each node are called the left and the right child.

Often a program must visit all the nodes in a tree, this is called traversing the tree. It is important to know the order in which nodes are traversed. There are three simple ways of traversing a tree.
 

  1. Inorder traversal
    1. traverse the left subtree using inorder traversal
    2. visit the root node
    3. traverse the right subtree using inorder traversal
  2. preorder traversal
    1. visit the root node
    2. traverse the left subtree using preorder traversal
    3. traverse the right subtree using preorder traversal
  3. postorder traversal
    1. traverse the left subtree using postorder traversal
    2. traverse the right subtree using postorder traversal
    3. visit the root node
For the tree given earlier - the nodes will be visited in the following order. Time to write some C.
#include <stdio.h>
#include <strings.h>

#define newptr(x,y) (x *)malloc((int)sizeof(x)*y)

typedef struct _node {
  char name[64];
  struct _node *left;
  struct _node *right;
} node;

typedef node *tree;
The structure contains pointers to the left and right trees. This function uses inorder traversal to print every node in the tree. Trees are very useful if the nodes are sorted. The search function assumes that the nodes are ordered. The list is ordered so that nodes would be visited in alphabetical order if they were traversed using inorder traversal. This function adds a new node to an ordered tree. Finally the main part of the program to test our data structure.
 
The tree that is built by this program is the following:

We can see that it is much quicker to find a piece of data in this tree than in the list. This is because at each node only one subtree needs to be searched.

For this reason trees are commonly used in databases.

One disadvantage of this simple binary tree is that the order of insertion determines the tree structure. If the nodes are inserted in alphabetical order, then the tree is just a linked list. In practice the tree would need to be reorganized (balanced) sometimes. Such a tree is called a balanced tree or B-tree.