Binary Search Trees

Created by Flash- Nguyen Duc Quan
------------------------------------------------------------------------------------------------------------------

1. Definitions

  A binary tree is made of nodes where each node contains a "left", a "right" reference, and a data element. (Binary tree is an extended part of linked data structure). The node at top A is named root.

Figure 1: Binary tree

Every node (excluding a root) in tree is connected by a directed edge from exactly one other node. This node is called a parent. Beside, each node can connect to arbitrary node number of node (it is two in this situation), called children

Some tree terminology we should know:

• Root node: A
• Leaf node (External node): Node without children :  H, I, J, K, L
• Internal node: Node are not leaves:  B, D, E C, F, G.
• Siblings: Nodes with the same parent: such as: B and C, D and E....
• The depth of a node is the number of node from the root to the node. Ex: Depth of node B is 2
• The height of a node is the number of node from the node to the deepest leaf. Ex: Height of Node B is 3
• The height of a tree is a height of the root. Ex: In figure 1, this tree has height equal to 4.
• A compete binary tree: If height of tree is h, then every node which has depth lower than (h - 1), must have 2 children. Example Figure 2 a)

Figure 2: e) a complete binary tree , f) a full binary tree

• A full binary tree is a binary tree: Every node has which depth lower or equal to (h-1) must have two children

2. Advantages of trees

Trees are so useful and frequently used, because they have some very serious advantages:

• Trees reflect structural relationships in the data
• Trees are used to represent hierarchies
• Trees provide an efficient insertion and searching
• Trees are very flexible data, allowing to move sub-trees around with minimum effort

3. Representation of Binary Trees.

3.1 Representation by an array

With full binary tree, we can number easily for each node on the tree from depth 1 to higher depth, from left to right. Therefore, the children of node i is 2i and 2i + 1. Parent of node j is node j div 2. After that we can store tree by array T, i-th node is stored by element T[i].

Figure 3: nodes are numbered

The binary tree in Figure 3 can be stored liked Figure 4.

Figure 4: Representation by array

3.2 Representation by linked list

Figure 5: Node Structure of Binary Tree

Each node has 3 domains:

• Info: Store value of node
• Left Pointer: a pointer points to its left child.
• Right Pointer: a pointer points to its right child.

The Binary tree represented by linked list is shown in Figure 1.

4. Traversals

A traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear data structure, there is no unique traversal. We will consider several traversal algorithms with we group in the following two kinds

• depth-first traversal
• breadth-first traversal (or Level Order)

There are three different types of depth-first traversals, :

• PreOrder traversal - visit the parent first and then left and right children;

// Result with Figure 1: A B D H I E J C F K G L

?

1 2 3 4 5 6 7 8 9

Procedure Visit (N) // Suppose N is root of tree begin      if N != null then           begin            Print value of node N;            Visit (left node of N);            Visit (right node of N);      end; end;

• InOrder traversal - visit the left child, then the parent and the right child;

// Result with Figure 1: H D I B E J A K F C G L

?

1 2 3 4 5 6 7 8 9

Procedure Visit (N) // Suppose N is root of tree begin     if N != null then         begin         Visit (left node of N);         Print value of node N;         Visit (right node of N);      end; end;

• PostOrder traversal - visit left child, then the right child and then the parent;

// Result with Figure 1: H I D J E B K F L G C A

?

1 2 3 4 5 6 7 8 9

Procedure Visit (N) // Suppose N is root of tree begin     if N != null then          begin          Visit (left node of N);          Visit (right node of N);          Print value of node N;     end; end;

LevelOder traversal: This traversal visits nodes by levels from top to bottom and from left to right.
Result with Figure 1: A B C D E F G H I J K L

5. Funtions to binary trees

5.1 Declare a struct: node
// code

?

1 2 3 4 5

struct node {    int a;// Value of  node    node *letf , *right;// Two Pointers to left and right nodes };

5.2 Init a tree
// code

?

1	struct node *head = NULL;

5.3 Check a tree, empty or not
// code

?

1 2 3 4 5

int empty_tree(nodeptr root) {    if(root == NULL)   return 1;    else return 0; }

5.4 Generate a tree
// code

?

1. void generate(struct node **head, int num)  
2. {  
3.     struct node *temp = *head, *prev = *head;  
4.        
5.     // Neu la lan dau thi do la root  
6.     if (*head == NULL)  
7.     {  
8.         *head = (struct node *)malloc(sizeof(struct node));  
9.         (*head)->a = num;  
10.         (*head)->left = (*head)->right = NULL;  
11.     }  
12.     else  
13.     {  
14.         while (temp != NULL)  
15.         {  
16.             if (num > temp->a)    
17.             {  
18.                 prev = temp;  
19.                 temp = temp->right;  
20.             }  
21.             else                 
22.             {  
23.                 prev = temp;  
24.                 temp = temp->left;  
25.             }  
26.         }  
27.         temp = (struct node *)malloc(sizeof(struct node));   
28.         temp->a = num;  
29.    
30.         // Noi node cha den node moi tao  
31.         if (num >= prev->a)      
32.         {  
33.             prev->right = temp;      
34.         }  
35.         else  
36.         {  
37.             prev->left = temp;  
38.         }  
39.     }  
40. }  

5.5 Delete tree
// code

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

void delete(struct node **head) {     if (*head != NULL)     {         if ((*head)->left)         {             delete(&(*head)->left);         }         if ((*head)->right)         {             delete(&(*head)->right);         }         free(*head);     } }

5.6 Tree Depth and Tree Height
// code

?

1 2 3 4 5 6 7 8 9 10

int TreeDepth(struct node *root) {     if(root == NULL)     {         return 0;     }     int nLeft = TreeDepth(root->left);     int nRight = TreeDepth(root->right);     return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1); }

5.7 Find largest number on tree
// code

?

1 2 3 4 5 6 7 8 9 10 11 12 13

void largest(struct node *root) {     if (root->right  == NULL)     {         printf("-------------->Largest element is %d <---------------- n="" root-="">a);     }     while (root != NULL && root->right != NULL)     {         root = root->right;     }     printf("\n---------------> Largest value is %d <----------------- n="" root-="">a); } <!---------------------><!-------------------->

5.8 Counting the number of nodes in a tree
// code 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

int count_num_nodes(struct node *root) {     int c = 1;        if (root == NULL)     {         return 0;     }     else     {         if(root -> left != NULL)         {             c += count_num_nodes(root->left);         }         if(root -> right != NULL)         {             c += count_num_nodes(root->right);         }         return c;     } }

5.9 Count number of leaf nodes 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

<b>void count_leaf(struct node * root) {     if (root == NULL)     {         return;     }     if (root->left == NULL && root->right == NULL)     {         count++;     }     count_leaf(root->left);     count_leaf(root->right); } </b>

// code

5.10 Traversal
a. Depth First Search: Pre-order
// code 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

void DFS_Pre_Order(struct node *head) {     if (head != NULL)     {         printf("%d  ", head->a);         if (head->left != NULL)         {             DFS_Pre_Order(head->left);         }         if (head->right != NULL)         {             DFS_Pre_Order(head->right);         }     } }

?

1

b. Depth First Search: In_order
//code 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

void DFS_In_Order(struct node *head) {     if (head != NULL)     {         if (head->left != NULL)         {             DFS_In_Order(head->left);         }         printf("%d  ", head->a);         if (head->right != NULL)         {             DFS_In_Order(head->right);         }        } }

c. Depth First Search: Post-order
//code 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

void DFS_Post_Order(struct node *head) {     if (head != NULL)     {         if (head->left != NULL)         {             DFS_Post_Order(head->left);         }         if (head->right != NULL)         {             DFS_Post_Order(head->right);         }         printf("%d  ", head->a);     } }

5.11 Search a node on tree using recursion algorithm
// code 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

int search_recursion(struct node *head, int key) {     if (head != NULL)      {         if(key > head->a)         {             return search_recursion(head->right, key);         }         else         {             if(key < head -> a)             {                 return search_recursion(head->left, key);             }             else             {                 return 1;             }         }     }     return 0; }

5.12 Search a node on tree not using recursion algorithm

// code

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

struct node *search_nonrecurion(struct node *head, int key, struct node **parent) {     while (head != NULL)     {         if (key > head->a)         {             *parent = head;             head = head->right;         }         else         {             if (key < head->a)             {                 *parent = head;                 head = head->left;                }             else             {                 return head;             }           }     }     return NULL; }