Здравствуйте, Барс Иван!
В тексте программы найдете все подпрограммы
Для демонстрации я добавил и создание дерева из заданного массива ключей...

В чем суть двоичного дерева? В том, что у каждого узла есть не более двух потомков, левого и правого.
Потому и называется "двоичный". Т.о., каждый узел должен содержать поле данных и ровно два указателя на два потомка.
(Посмотрите структуру Node)
Дерево же общего вида не ограничивает число потомков. Их может быть сколь угодно много. Поэтому каждый узел должен содержать в себе поле данных, указатель на начало списка "братьев" и на начало списка "сыновей".

где
Node.next - следующий элемент в текущем списке "братьев",
Node.child - указатель на первый элемент списка потомков.

Программа:
[code h=200]#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>

struct Node
{
int key; //ключ
Node *left; //левое поддерево
Node *right; //правое поддерево
};

void del(Node *node) //удаление дерева, начиная с корня
{
if (node != 0) //если не пустое
{
del(node->left) ; //удаляем левое поддерево
del(node->right) ; //правое
free(node); //сам узел
}
}

Node* insert( Node *node, int x ) //вставка узла в дерево
{
if (node==0) //узел пустой
{ //создаем
node = (Node *) malloc (sizeof(Node));
node->key = x ; //пишем ключ
node->left = node->right = 0 ; //и помечаем, что без потомков
} //узел есть
else if (x<=node->key) //новый ключ меньше или равно
node->left = insert (node->left, x); //вставляем в левое поддерево
else
node->right = insert (node->right, x); //иначе - в правое
return node ; //вернем корень
}

//подсчет всех узлов дерева, count - адрес переменной, в которой должен быть 0
void CalcAllNodes(Node *node, int *count)
{
if (node != NULL) //узел непустой?
{
(*count)++; //считаем себя
CalcAllNodes(node->left, count); //всех в левом поддереве
CalcAllNodes(node->right, count); //и в правом
}
}

//подсчет листьев (узлов без потомков)
void CalcLeafNodes(Node *node, int *count)
{
if (node == NULL) //узла нет - выходим
return;
if ((node->left == NULL) && (node->right == NULL)) //нет потомков - лист!
(*count)++; //считаем!!!
else
{ //иначе - считаем в левом поддереве и в правом
CalcLeafNodes(node->left, count);
CalcLeafNodes(node->right, count);
}
}

//подсчет степени дерева (максимальной длины цепочки потомков)
int CalcTreeLevel(Node *node)
{
if (node == NULL) //узла нет - выходим
return 0;
else //есть - считаем себя и максимальную из левого
return (1 + __max ( CalcTreeLevel(node->left), //и правого поддерева
CalcTreeLevel(node->right) ));
}

//подсчет степени узла (числа потомков)
//сначала ищем узел по ключу, затем в level пишем степень вершины, возвращаем true
//если узел не найден - возвращаем false
bool CalcNodeLevel(Node *node, int key, int *level)
{
if (node != NULL) //проверяем, есть и узел
{
if (node->key == key) //сравниваем ключ, и если равен, то
{ //возвращаем число потомков
*level = (node->left != NULL) + (node->right != NULL);
return true; //и true
} //ключ не равен, ищем дальше
if (CalcNodeLevel(node->left, key, level)) //в левом поддереве
return true; //если там найден, то выходим
if (CalcNodeLevel(node->right, key, level)) //и правом поддереве
return true; //если там найден, то выходим
}
return false; //ключ не найден
}

int main(void)
{
Node *root = NULL; //корень дерева
//зададим ключи для построения дерева
int d[15] = {10,5,15,1,8,3,6,9,12,2,18,13,21,11,4};
int count, level;

for (int i=0; i<15; i++) //построим дерево
root = insert(root, d[i]);

count = 0; //считаем все узлы
CalcAllNodes(root, &count);
printf ("Nodes count = %d\n", count);

count = 0; //листья
if (root) //сначала надо проверить на наличие корня
CalcLeafNodes(root, &count);
printf ("Leafs count = %d\n", count);

//степень дерева
printf ("Tree level = %d\n", CalcTreeLevel(root));

//найдем степень разных узлов
if (CalcNodeLevel(root, 9, &level)) //у которой 0 потомков
printf ("Node 9 level = %d\n", level);
else
printf("Node 9 not found\n");

if (CalcNodeLevel(root, 18, &level)) //1 потомок
printf ("Node 18 level = %d\n", level);
else
printf("Node 18 not found\n");

if (CalcNodeLevel(root, 12, &level)) //2 потомка
printf ("Node 12 level = %d\n", level);
else
printf("Node 12 not found\n");

if (CalcNodeLevel(root, 19, &level)) //нет узла
printf ("Node 19 level = %d\n", level);
else
printf("Node 19 not found\n");

del(root); //удалим дерево

_getch();

return 0;
}
[/code]