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

could have at most*h*nodes*2*^{h-1}For a binary tree with height

, it could have at most*h*nodes*2*^{h}-1For a binary tree with

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

nodes, its height should be*n**log*_{2}(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);
}
```