1. Trees
A tree is a dynamic data structure composed of multi-levels of linked lists. As a data structure, a tree is defined as a node, which itself consists of a value together with a list of references to other nodes. Symbolically, a tree is defined recursively as
node: value [&node[1], …, &node[k]]
where each node[i] is itself a (possibly empty) tree. The very first node of a tree is called the root of the tree. Each node is called a parent node if it points to a list of other nodes, which are called the children nodes of the parent node. In a tree, each node has a unique parent, but each node may have a variable number of children nodes, including none. A tree can be represented by a diagram, which is usually drawn upside-down, with the root node at the top. Figure 2.28 shows a general tree.
2. Binary Tree
The simplest kind of tree is the binary tree, in which each node has two pointers, denoted by left and right. We may define the node type containing a single key value for binary trees as
typedef struct node{
int key;
struct node *left;
struct node *right;
}NODE;
Every general tree can be implemented as a binary tree. We shall demonstrate this in Sect. 2.13.
2.1. Binary Search Tree
A Binary Search Tree (BST) is a binary tree with the following properties:
. All node keys are distinct, i.e. the tree contains no nodes with duplicated keys.
. The left subtree of a node contains only nodes with keys less than the node’s key.
. The right subtree of a node contains only nodes with keys greater than the node’s key.
. Each of the left and right subtrees is also a binary search tree.
As an example, Fig. 2.29 shows a binary search tree.
Fig. 2.29 A binary
search tree
Binary Search Tree provides an ordering among the node keys so that operations such as finding the minimum, maximum keys and search for a given key can be done quickly. The search depth of a BST depends on the shape of the tree. If a binary tree is balanced, i.e. every node has two children nodes, the search depth is log2(n) for a tree with n nodes. For unbalanced BST, the worst search depth would be n, if the nodes are all to the left or all to the right.
2.2. Build a Binary Search Tree (BST)
Example Program C2.7: Build a Binary Search Tree
/************ C2.7.c file ************/
#include <stdio.h>
#include <stdlib.h> typedef struct node{
int key;
struct node *left, *right;
}NODE;
#define N 7
int nodeValue[N] = {50,30,20,40,70,60,80};
// create a new node
NODE *new_node(int key)
{
NODE *node = (NODE *)malloc(sizeof(NODE));
node->key = key;
node->left = node->right = NULL;
return node;
}
// insert a new node with given key into BST
NODE *insert(NODE *node, int key)
{
if (node == NULL)
return new_node(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
int i;
NODE *root = NULL;
root = insert(root, nodeValue[0]);
for (i=1; i<N; i++){
insert(root, nodeVlaue[i]);
}
}
Fig. 2.30 A binary search tree
Figure 2.30 shows the BST generated by the Example Program C2.7.
2.3. Binary Tree Traversal Algorithms
From elementary data structure courses, the reader should have learned the following binary tree traversal algorithms.
. Pre-order Traversal: node; node.left; node.ight
. In-order traversal: node.left; node; node.right
. Post-order traversal: node.left; node.right; node
2.4. Depth-First Traversal Algorithms
All the above algorithms belong to Depth-First (DF) search/traversal algorithms, which use a stack for back-tracking. As such, they can be implemented naturally by recursion. As an example, search a BST for a given key can be implemented by rercusion, which is basically an in-order traversal of the BST.
/******** Search BST for a give key ********/
NODE *search(NODE *t, int key)
{
if (t == NULL || t->key == key)
return t;
if (key < t->key) // key is less than node key
return search(t->left, key);
else
return search(t->right, key); // key is greater than node key
}
2.5. Breadth-First Traversal Algorithms
A tree can also be traversed by Breadth-First (BF) algorithms, which use a queue to store the yet to be traversal parts of the tree. When applying BF traversal algorithm to a tree, we may print the tree level by level, as shown by the next example program.
Example Program C2.8: Print Binary Tree by Levels
/***** C2.8.c file: print binary tree by levels *****/
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
struct node *left;
int key;
struct node *right;
}NODE;
QE *q = *queue;
QE *r = (QE *)malloc(sizeof(QE));
r->node = node;
if (q == 0)
*queue = r;
else{
while (q->next)
q = q->next;
q->next = r;
}
r->next = 0;
}
NODE *dequeue(QE **queue)
{
QE *q = *queue;
if (q)
*queue = q->next;
return q->node;
}
int qlength(QE *queue)
{
int n = 0;
while (queue){
n+ + ;
queue = queue->next;
}
return n;
}
// print a binary tree by levels, each level on a line
void printLevel(NODE *root)
{
int nodeCount;
if (root == NULL) return;
QE queue = 0; // create a FIFO queue
enqueue(&queue, root); // start with root
while(1){
nodeCount = qlength(queue); if (nodeCount == 0) break;
// dequeue nodes of current level, enqueue nodes of next level
while (nodeCount > 0){
NODE *node = dequeue(&queue);
printf(“%d “, node->key);
if (node->left != NULL)
enqueue(&queue, node->left);
if (node->right != NULL)
enqueue(&queue, node->right);
nodeCount–;
}
printf(“\n”);
}
}
NODE *newNode(int key) // create a new node
{
NODE *t = (NODE *)malloc(sizeof(NODE));
t->key = key;
t->left = NULL;
t->right = NULL;
return t;
}
int main() // driver program to test printLevel()
{
queue = 0;
// create a simple binary tree
NODE *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->leftt = newNode(6);
root->right->right = 0; // right child = 0
printLevel(root);
return 0;
}
In the example program C2.8, each queue element has a next pointer and a NODE pointer to the node in the tree. The tree will be traversed but not altered in anyway; only its nodes (pointers) will be used in queue elements, which are entered into and removed from the queue. The printLevel() function starts with the root node in the queue. For each iteration, it dequeues a node of the current level, prints its key and enters the left child (if any), followed by the right child (if any), into the queue. The iteration ends when the queue becomes empty. For the simple binary tree constructed in main(), the program outputs are
1
2 3
4 5 6
which print each level of the tree on a separate line.
Source: Wang K.C. (2018), Systems Programming in Unix/Linux, Springer; 1st ed. 2018 edition.