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

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.

- Inorder traversal
- traverse the left subtree using inorder traversal
- visit the root node
- traverse the right subtree using inorder traversal
- preorder traversal
- visit the root node
- traverse the left subtree using preorder traversal
- traverse the right subtree using preorder traversal
- postorder traversal
- traverse the left subtree using postorder traversal
- traverse the right subtree using postorder traversal
- visit the root node

- inorder
- preorder
- postorder

DBEAFCG

ABDECFG

DEBFGCA

The structure contains pointers to the left and right trees.#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;

This function uses inorder traversal to print every node in the tree.void print_tree(tree root) { if(root) { print_tree(root -> left); puts(root -> name); print_tree(root -> right); } }

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.tree search(tree t,char *name) { int c; if (t==NULL) return NULL; c=strcmp(name,t->name); if (c==0) return t; if (c<0) return search(t->left,name); return search(t->right,name); }

This function adds a new node to an ordered tree.void insert_node(tree *t,char *name) { node *new_node; if (*t==NULL) { new_node=newptr(node, 1); *t=new_node; strcpy(new_node->name, name); new_node -> left = NULL; new_node -> right = NULL; } else if (strcmp(name,((*t)->name)) < 0) insert_node(&(*t)->left,name); else if (strcmp(name,((*t)->name)) > 0) insert_node(&(*t)->right,name); }

Finally the main part of the program to test our data structure.main() { tree t=NULL,t1; insert_node(&t,"Florence"); insert_node(&t,"Dougal"); insert_node(&t,"Dylan"); insert_node(&t,"Zebedee"); insert_node(&t,"Mr Rusty"); insert_node(&t,"Mr McHenry"); insert_node(&t,"Brian"); print_tree(t); t1=search(t,"Brian"); if (!t1) puts("Brian Not Found"); t1=search(t,"Martin"); if (!t1) puts("Martin Not Found"); }

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.