How to Create a Binary Tree in C

How to Create a Binary Tree in C. Binary trees in C are a good way to dynamically organize data for easy searching. However, they require a lot of work to maintain.

Create the Binary Tree

Step

Structure your binary tree. Every binary tree will need a structure, even if it only has one variable. Choose a name, then use typedef to create it: typedef struct student_data STUDENT_DATA;

Step

Define the structure. Include two pointers to the same structure: struct student_data { int student_ID; int student_grade; STUDENT_DATA left, right;};

Step

Allocate a pointer to this data structure, initializing it to NULL, to be the tree's head: STUDENT_DATA *students = NULL;

Add to the Binary Tree

Step

Allocate two temporary pointers to the data structure: STUDENT_DATA _newstudent, cur_student;

Step

Use malloc() to create a new element, always checking for an error: if ((new_student = malloc(sizeof(STUDENT_DATA))) == NULL) { abort(); }

Step

Populate the new element's fields. Set its left and right fields to NULL: new_student->student_ID = newID;new_student->student_size = newsize;new_student->left = NULL;new_student->right = NULL;

Step

Consider the head variable. If the head variable is NULL, this is the first element added to the tree, so set the head variable to point to it, and you're done: if (!students) { students = new_student; return; }

Step

Start at the top of the tree: cur_student = students;while (cur_student) {

Step

Handle the duplicate entry if the new value and current value are equal: if (newID == cur_student->student_ID) { abort(); }

Step

Deal with unequal values. If the new value is less than the current value, the new element goes on the left. Add it immediately if there's nothing on the left. Otherwise, traverse left and loop: if (newID < cur_student->student_ID) { if (cur_student->left == NULL) { cur_student->left = newstudent; return 1; } cur_student = cur_student->left;

Step

Do the same thing on the right, otherwise: } else { if (cur_student->right == NULL) { cur_student->right = newstudent; return 1; } cur_student = cur_student->right; }}

Search the Binary Tree

Step

Create a temporary variable pointing to the data structure: STUDENT_DATA *cur_student;

Step

Set your temporary variable to the head variable: cur_student = students_head;

Step

Loop through the elements, checking for the desired value: while (cur_student) { if (cur_student->student_ID == 15) { return cur_student->student_grade; }

Step

Branch left or right, and loop, if it's not found: if (cur_student->student_ID < 15) { cur_student = cur_student->right; } else { cur_student = cur_student->left; }

Step

See if the loop ends. If it does, it means you never found the item: }return 0;

Clean Up

Step

Deallocate the binary tree when your program ends, as not all operating systems will handle this automatically. This is best done using a recursive function: void deallocate_binary_tree(STUDENT_DATA *tree) {

Step

Observe: If there isn't any tree, there's nothing to do: if (!tree) return;

Step

Deallocate the left and right subtrees recursively: deallocate_binary_tree(tree->left); deallocate_binary_tree(tree->right);

Step

Deallocate the element, and you're done: free(tree);}