#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <malloc.h>
#include <stdbool.h>
//первый элемент nocolor нужен для поиска родителя-корня

enum node_t{
    nocolor, red, green, blue, orange, yellow, indigo, violet, brown, white, black
} ;

struct Node {
    enum node_t Color; //цвет
    struct Node *Son; //указатель на первого сына
    struct Node *Brother; //указатель на слеующего брата
};
struct Node * Root = NULL; //корень дерева
void AddElement();
void DelElement();
void OutTree();
void CalcMinDepth();
void Exit();
int GetNum();
enum node_t GetColor(bool);
//преобразование enum в строку

char* GetColorString(enum node_t color) {
    switch (color) {
        case nocolor:
            return "корень или братья корня";
        case red:
            return "красный";
        case green:
            return "зеленый";
        case blue:
            return "голубой";
        case orange:
            return "оранжевый";
        case yellow:
            return "желтый";
        case indigo:
            return "индиго";
        case violet:
            return "фиолетовый";
        case brown:
            return "коричневый";
        case white:
            return "белый";
        case black:
            return "черный";
        default:
            return "неизвестный"; //на всякий случай
    }
}
char *mesMain[] = //сообщения меню
{
    "Включить новый элемент",
    "Удалить элемент",
    "Вывести дерево",
    "Найти лист с минимальной глубиной",
    "Выход"
};
//количество пунктов меню
int MesMainCount = sizeof ( mesMain) / sizeof ( mesMain[0]);
//функции отработки пунктов меню
void ( *funcMain[])() = {AddElement, DelElement, OutTree, CalcMinDepth, Exit};
//создание нового узла, возвращает указатель на этот элемент

struct Node* CreateNode(enum node_t Color) {
    struct Node * node = (struct Node*) malloc(sizeof (struct Node));
    node->Color = Color; //цвет
    node->Son = NULL; //без детей
    node->Brother = NULL; //и брата нет
    return node;
}
//рекурентный поиск узла с аданным цветом
//Current - первый в списке братьев
//Color - искомый цвет
//pParent - адрес указателя на родителя, в начале должен быть NULL
// используется при удалении узла
//pBrother- арес указателя на предыдущего брата, там в начале должен быть NULL
// используется при удалении узла

struct Node* Find(struct Node* Current, enum node_t Color, struct Node** pParent, struct Node** pBrother) {
    struct Node *node, *nodeSon;
    //сначала сравним поле для братьев, начиная с заданного
    for (node = Current; node; node = node->Brother) {
        //сравниваем цвет
        if (node->Color == Color) {
            return node; //нашли, вернем указатель на узел
        }
        *pParent = NULL; //NULL для всех последующих братьев
        *pBrother = node; //сохраним указатель на предыдущего брата
    }
    //идем на седующий уровень - по сыновьям всех братьев
    for (node = Current; node; node = node->Brother) {
        //зададим родителя для первого сына
        *pParent = node;
        //ищем среди всех потомков текущего брата
        if (NULL != (nodeSon = Find(node->Son, Color, pParent, pBrother)))
            //если наши, то возвращаем выше указатель на узел
            return nodeSon;
    }
    return NULL; //не найдено
}
//поиск последнего в списке братьев

struct Node* Last(struct Node * node) {
    for (; node->Brother; node = node->Brother);
    return node;
}
//добавение узла с указанием цвета родителя(или 0 для корня и его братьев) и вставяемого узла

int AddNode(enum node_t ColorParent,enum node_t Color) {
    struct Node *node, *nodeLast, *nodeNew;
    struct Node *Parent = NULL;
    struct Node *Brother = NULL;
    //что-то есть вообще?
    if (Root == NULL) //корня еще пока нет
    {
        if (ColorParent == nocolor) //проверим правильность задания цвета родителя! Для корня 0!
        {
            Root = CreateNode(Color); //создаем корень
            return 1; //внесли
        } else
            return 2; //неправильные данные - родитель не найден!
    } else if (ColorParent == nocolor) //родитель - 0 уровень, т.е. братья корня?
    {
        if (NULL == Find(Root, Color, &Parent, &Brother)) //есть ли уже узел с цветом color?
        {
            nodeNew = CreateNode(Color); //создаем узел
            nodeLast = Last(Root); //ищем последнего брата
            nodeLast->Brother = nodeNew; //добавляем нового в цепочку братьев
            return 1; //внесли
        } else
            return 0; //дубликат цвета
    }//родитель - не корень
        //ищем родителя
    else if (NULL != (node = Find(Root, ColorParent, &Parent, &Brother))) {
        //есть ли уже узел с цветом color?
        Parent = NULL; //начинаем искать с начала
        Brother = NULL;
        if (NULL == Find(Root, Color, &Parent, &Brother)) { //цвет не найден
            //добавяем
            nodeNew = CreateNode(Color); //создаем узел
            if (NULL == node->Son) //у родителя уже есть дети?
                node->Son = nodeNew; //нет - будем первым сыном
            else { //есть - будем младшим сыном
                nodeLast = Last(node->Son); //ищем самого последнего
                nodeLast->Brother = nodeNew; //и добавляем новый элемент в конец цепочки братьев
            }
            return 1; //внесли
        } else
            return 0; //дубликат цвета
    } else
        return 2; //родитель не найден!
}
//рекурентное удаление узла вместе со всеми потомками

void DeleteAllSons(struct Node *nodeParent) {
    struct Node *node, *nodeBrother;
    //по всем сыновьям
    for (node = nodeParent->Son; node; node = nodeBrother) {
        //запомним следуюещго брата
        nodeBrother = node->Brother;
        //удаляем текущего сына со всего его потомками
        DeleteAllSons(node);
    }
    //удаляем сам узел
    free(nodeParent);
}
//удаление узла с заанным цветом

bool DelNode(enum node_t Color) {
    struct Node *node, *nodeBrother;
    struct Node *Parent = NULL;
    struct Node *Brother = NULL;
    //ищем узел
    if (NULL != (node = Find(Root, Color, &Parent, &Brother))) { //нашли!
        nodeBrother = node->Brother; //запомним следующего брата
        DeleteAllSons(node); //удаляем узел со всеми потомками
        //подправим ссылку
        if (node == Root) //узел - корень?
            Root = nodeBrother; //корнем будет следующий брат
        else if (Parent != NULL) //узел - первый из братьев?
            Parent->Son = nodeBrother; //делаем первым сыном брата
        else
            Brother->Brother = nodeBrother; //сеующий брат будет идти за предыдущим брат
        return true; //уалили
    } else
        return false; //узел не найден
}
//удаение всего дерева (в конце)

void DelAll(void) {
    while (Root)
        DelNode(Root->Color); //удаяем всех братьев корня
}
//рекурентный структуированный вывод дерева, начиная с узла node
//уровень узла задается параметром level

void PrintTree(struct Node* node, int level) {
    char str[80]; //для формирования первых пробелов
    int i;
    for (; node; node = node->Brother) //по братьям
    {
        for (i = 0; i < level; i++) //сформируем level пробелов
            str[i] = ' '; //можно по-разному, я сделал "в лоб"
        str[i] = 0; //закрываем строку нулем
        //выводим цвет с пробелами
        printf("%s%s\n", str, GetColorString(node->Color));
        PrintTree(node->Son, level + 2); //выводим потомков, на каждый уровень по 2 пробела
    }
}
//рекурентный поиск узла с минимальной глубиной
//nodeParent - началный узел
//iDepth - глубина до текущего уровня (в начале 0)
//piDepthMin - адрес переменной - минимальной глубины
//nodeMin - адрес указателя на узел с минимальной глубиной

void SearchLeafs(struct Node *nodeParent, int iDepth, int *piDepthMin, struct Node **nodeMin) {
    struct Node *node;
    //если NULL, то начинаем с корня, иначе с первого сына
    node = (nodeParent == NULL) ? Root : nodeParent->Son;
    iDepth++; //глубина текущего уровня
    for (; node; node = node->Brother) //по братьям
    {
        if (node->Son == NULL) //узел - лист (без сыновей)?
        { //в начале просто сохраняем первого
            //для всех остальных - ищем минимального
            if ((*piDepthMin == NULL) || (*piDepthMin > iDepth)) {
                *piDepthMin = iDepth; //сохраняем глубину
                *nodeMin = node; //и узел
            }
        } else //имеет потомков - задаем поиск по потомкам
            SearchLeafs(node, iDepth, piDepthMin, nodeMin);
    }
}
//добавить элемент

void AddElement() {
    enum node_t parent, Color;
    printf("Введите цвет родителя\n");
    parent = GetColor(true); //вводим цвет родителя, с возможностью ввода корня
    printf("Введите цвет элемента\n");
    Color = GetColor(false); //вводим цвет нового элемента
    switch (AddNode(parent, Color)) //пытаемся добавить
    {
        case 1:
            printf("Элемент добавлен\n");
            break;
        case 0:
            printf("Элемент c данным цветом уже есть\n");
            break;
        case 2:
            printf("Родитель не найден\n");
    }
}
//удалить элемент

void DelElement() {
    enum node_t Color;
    printf("Введите цвет элемента\n");
    Color = GetColor(false); //вводим цвет
    if (DelNode(Color)) //пытаемся удалить
        printf("Элемент удален\n");
    else
        printf("Элемент c данным цветом не найден\n");
}
//вывод дерева

void OutTree() {
    PrintTree(Root, 0); //начинаем с корня и уровня 0
}
//поиск узла с минималной глубиной

void CalcMinDepth() {
    int iDepthMin = 0;
    struct Node *nodeMin = NULL;
    SearchLeafs(NULL, 0, &iDepthMin, &nodeMin); //ищем
    if (iDepthMin)
        printf("Минимальная глубина = %d, Цвет = %s\n", iDepthMin, GetColorString(nodeMin->Color));
    else
        printf("Дерево пустое\n");
}

void Exit() //выход
{
    DelAll(); //освобождаем память
}

bool IsNum(char *str) //проверка строки на число
{
    for (; isdigit(*str); str++);
    return (*str == 0);
}
//ввод числа

int GetNum() {
    char str[80];
    while (1) {
        gets(str); //введем строку
        if (IsNum(str)) //проверим на корректность
            return (atoi(str)); //возвращаем число
        printf("Введите число!\n");
    }
    //сюда не попадем, но
    return -1; //подпрограмма должна что-то возвращать
}
//ввод цвета с отображением всех цветов
//Parent = true для выбора родителя - корня

enum node_t GetColor(bool Parent) {
    enum node_t iColor;
    while (1) {
        //выведем цведа в две строки для выбора
        for (iColor = red; iColor < yellow; iColor = (enum node_t) ((int) iColor + 1))
            printf("%d.%s,\t", iColor, GetColorString(iColor));
        printf("%d.%s\n", iColor, GetColorString(iColor));
        for (iColor = indigo; iColor < black; iColor = (enum node_t) ((int) iColor + 1))
            printf("%d.%s,\t", iColor, GetColorString(iColor));
        printf("%d.%s\n", iColor, GetColorString(iColor));
        //выбор корня нужен?
        if (Parent)
            printf("%d.%s\n", nocolor, GetColorString(nocolor));
        printf("Ваш выбор: ");
        iColor = (enum node_t) GetNum();
        if (Parent) {
            if ((iColor >= nocolor) || (iColor <= black))
                return (iColor);
        } else if ((iColor >= red) || (iColor <= black))
            return (iColor);
        else
            printf("Введите число из диапозона!\n");
    }
    return nocolor; //сюда не попадем никогда
}
//показ меню с вводом номера строки

int ViewMenu(char** mes, int max) {
    int ret,i;
    do {
        //меню
        for (i = 0; i < max; i++)
            printf("%d. %s\n", i + 1, mes[i]);
        printf("Ваш выбор: ");
        //вводим число
        ret = GetNum();
    }//проверим на допустимость
    while (ret < 1 || ret > max);
    //вернем номер строки
    return ret;
}

int main() {
    int ret;
    //чтобы писалось по-русски
    system("chcp 1251 >> nul");
    do {
        ret = ViewMenu(mesMain, MesMainCount); //выводим меню, вводим номер строки
        funcMain[ret - 1](); //отрабатываем пункт меню
        printf("--------------------------------\n");
        if (ret == MesMainCount) //последняя - выход
            break;
    } while (ret);
    return 0;
}

main.c: В функции ‘SearchLeafs’:
main.c:232:30: предупреждение: сравнение указателя и целого
 
build/Debug/GNU-Linux-x86/main.o: In function `GetNum':
main.c:303: warning: the `gets' function is dangerous and should not be used.

ПОСТРОИТЬ SUCCESSFUL (общее время: 163мс)