REN

Binary Tree is a tree data structure in which each node has at most two children. I'll show the data structure of binary tree in C language and its corresponding operations such as pre-order, in-order and post-order traversal in this article.

Properties of Binary Trees

Based on the structure of binary tree, we can conclude some properties of binary tree:

• For a binary tree, at height h could have at most 2^h-1 nodes

• For a binary tree with height h, it could have at most 2^h-1 nodes

• For a binary tree with n nodes, it could have at most (n + 1) / 2 leaf nodes

• For a binary tree with n nodes, its height should be log₂ (n + 1)

Full Binary Tree & Complete Binary Tree & Perfect Binary Tree

A full binary tree is a tree where every nodes has either two children or no child.

A complete binary tree is a tree in which all levels are completely filled except possibly the last level and the last level has all keys as left as possible.

A perfect binary tree is a tree every node except for leaf nodes has two children and leaf nodes have no child.

Data Structure and Operation of Binary Tree

Here, I'll make the data type of binary tree to be char for simplicity, and the type could be any. The data structure of each node of binary tree is below:

typedef char type;

typedef struct bTree {
	type value;
	struct bTree *left;
	struct bTree *right;
} bTree;

Create Binary Tree

This is a recursive function creating the binary tree in an pre-order. We use a char array as an input containing what should be in the binary tree. Thus the char array "abd##e##cf##g##" ('#' represents no child) means the following binary tree:

bTree* createBTreeR(bTree* t, type* value, int* cnt, int length) {
	if (*cnt < length) {
		if (value[*cnt] != '#') {
			t = (bTree*)malloc(sizeof(bTree));
			t->value = value[*cnt];
			(*cnt)++;
			t->left  = createBTreeR(t->left, value, cnt, length);
			(*cnt)++;
			t->right = createBTreeR(t->right, value, cnt, length);
		} else {
			t = NULL;
		}
	}
	return t;
}

Pre-order Traversal

void preOrder(bTree *t) {
	if (t) {
		printf("%c ", t->value);
		preOrder(t->left);
		preOrder(t->right);
	}
}

In-order Traversal

void inOrder(bTree *t) {
	if (t) {
		inOrder(t->left);
		printf("%c ", t->value);
		inOrder(t->right);
	}
}

Post-order Traversal

void postOrder(bTree *t) {
	if (t) {
		postOrder(t->left);
		postOrder(t->right);
		printf("%c ", t->value);
	}
}

Destroy

Free the dynamic memory for the binary tree.

void destoryBTree(bTree *t) {
	if (t->left || t->right) {
		destoryBTree(t->left);
		destoryBTree(t->right);
	} else 
		free(t);
}