Обход бинарного дерева в ширину

#include <stdio.h>
#include <stdlib.h>
#include <clocale>
#include <Windows.h>
#define partslen 24
 
struct part{
    short num;
    short cangoto[4];
};
 
void rec(short nowid, short *lastids, struct part *parts);
 
 
int main(void){
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    part parts[partslen];
    short lastids[partslen];
    short i;
    for(i = 0; i < partslen; i++){
        lastids[i] = -1;
    }
    
 
    i = 0; parts[i].num = 0; parts[i].cangoto[0] = 6; parts[i].cangoto[1] = 15; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    i = 1; parts[i].num = 0; parts[i].cangoto[0] = -1; parts[i].cangoto[1] = -1; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    i = 2; parts[i].num = 29; parts[i].cangoto[0] = 6; parts[i].cangoto[1] = 7; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    i = 3; parts[i].num = 16; parts[i].cangoto[0] = 7; parts[i].cangoto[1] = 8; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    i = 4; parts[i].num = 46; parts[i].cangoto[0] = 8; parts[i].cangoto[1] = 9; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    i = 5; parts[i].num = 27; parts[i].cangoto[0] = 9; parts[i].cangoto[1] = 10; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    i = 6; parts[i].num = 24; parts[i].cangoto[0] = 2; parts[i].cangoto[1] = 11; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    i = 7; parts[i].num = 31; parts[i].cangoto[0] = 2; parts[i].cangoto[1] = 11; parts[i].cangoto[2] = 3; parts[i].cangoto[3] = 12;
    i = 8; parts[i].num = 17; parts[i].cangoto[0] = 3; parts[i].cangoto[1] = 4; parts[i].cangoto[2] = 12; parts[i].cangoto[3] = 13;
    i = 9; parts[i].num = 21; parts[i].cangoto[0] = 4; parts[i].cangoto[1] = 5; parts[i].cangoto[2] = 13; parts[i].cangoto[3] = 14;
    i = 10; parts[i].num = 52; parts[i].cangoto[0] = 5; parts[i].cangoto[1] = 14; parts[i].cangoto[2] = 1; parts[i].cangoto[3] = -1;
    i = 11; parts[i].num = 13; parts[i].cangoto[0] = 6; parts[i].cangoto[1] = 15; parts[i].cangoto[2] = 7; parts[i].cangoto[3] = 16;
    i = 12; parts[i].num = 35; parts[i].cangoto[0] = 7; parts[i].cangoto[1] = 8; parts[i].cangoto[2] = 16; parts[i].cangoto[3] = 17;
    i = 13; parts[i].num = 11; parts[i].cangoto[0] = 8; parts[i].cangoto[1] = 9; parts[i].cangoto[2] = 17; parts[i].cangoto[3] = 18;
    i = 14; parts[i].num = 14; parts[i].cangoto[0] = 9; parts[i].cangoto[1] = 10; parts[i].cangoto[2] = 18; parts[i].cangoto[3] = 19;
    i = 15; parts[i].num = 43; parts[i].cangoto[0] = 11; parts[i].cangoto[1] = 20; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    i = 16; parts[i].num = 21; parts[i].cangoto[0] = 11; parts[i].cangoto[1] = 12; parts[i].cangoto[2] = 20; parts[i].cangoto[3] = 21;
    i = 17; parts[i].num = 53; parts[i].cangoto[0] = 12; parts[i].cangoto[1] = 13; parts[i].cangoto[2] = 21; parts[i].cangoto[3] = 22;
    i = 18; parts[i].num = 63; parts[i].cangoto[0] = 13; parts[i].cangoto[1] = 14; parts[i].cangoto[2] = 22; parts[i].cangoto[3] = 23;
    i = 19; parts[i].num = 15; parts[i].cangoto[0] = 14; parts[i].cangoto[1] = 1; parts[i].cangoto[2] = 23; parts[i].cangoto[3] = -1;
    i = 20; parts[i].num = 76; parts[i].cangoto[0] = 15; parts[i].cangoto[1] = 16; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    i = 21; parts[i].num = 19; parts[i].cangoto[0] = 16; parts[i].cangoto[1] = 17; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    i = 22; parts[i].num = 48; parts[i].cangoto[0] = 17; parts[i].cangoto[1] = 18; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    i = 23; parts[i].num = 12; parts[i].cangoto[0] = 18; parts[i].cangoto[1] = 19; parts[i].cangoto[2] = -1; parts[i].cangoto[3] = -1;
    
    rec(0, lastids, parts);
}
 
 
void rec(short nowid, short *lastids, struct part *parts){
    short mylastids[partslen];
    long i, j;
 
    if(nowid == 1){
        i = 0;
        for(j = 0; j < partslen && lastids[j] >= 0; j++){
            i += parts[lastids[j]].num;
        }
        if(i == 350){
            static int a=1;
            printf("Âàð³àíò ç 350 ¹%d:\n",a);
            for(i = 0; i < partslen && lastids[i] >= 0; i++){
                printf("%hd ", lastids[i]);
            }
            printf("\n");
            a++;
        }
        if(i == 250){
            static int b=1;
            printf("Âàð³àíò ç 250 ¹%d:\n",b);
            for(i = 0; i < partslen && lastids[i] >= 0; i++){
                printf("%hd ", lastids[i]);
            }
            printf("\n");
            b++;
        }
        return;
    }
    for(i = 0; i < 4; i++){
        if(parts[nowid].cangoto[i] >= 0){
            for(j = 0; j < partslen; j++){
                if(lastids[j] == parts[nowid].cangoto[i]){
                    break;
                }
            }
            if(j == partslen){
                for(j = 0; j < partslen; j++){
                    mylastids[j] = lastids[j];
                }
                j = 0;
                while(mylastids[j] != -1){
                    j++;
                }
                mylastids[j] = nowid;
                rec(parts[nowid].cangoto[i], mylastids, parts);
            }
        }
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
 
//узел очереди
typedef struct node {
    const void*  ptr;
    struct node* next;
} node_t;
 
//очередь(FIFO) для обхода дерева в ширину
typedef struct {
    node_t* head;
    node_t* tail;
} queue_t;
void  queue_init(queue_t* q);
int   queue_push(queue_t* q, const void* ptr);
void  queue_pop(queue_t* q);
const void* queue_front(queue_t* q);
int   queue_empty(queue_t* q);
 
//двоичное дерево поиска
typedef struct tree {
    int  key;
    struct tree* left;
    struct tree* right;
} tree_t;
tree_t* tree_insert(tree_t** tr, int key);
void    tree_clear(tree_t* tr);
 
//обход дерева в ширину
void tree_out_width(FILE* _out, const tree_t* tr){
    const tree_t* p;
    queue_t q;
    queue_init(&q);
 
    queue_push(&q, tr);
    while(! queue_empty(&q)){
        p = (const tree_t*)queue_front(&q);
        queue_pop(&q);
        //выводим
        fprintf(_out, "%d ",p->key);
        
        if(p->left != NULL)
            queue_push(&q, p->left);
        if(p->right != NULL)
            queue_push(&q, p->right);
    }
}
 
int main(void){
    int     i;
    tree_t* tr = NULL;
    for(i = 0; i < 20; ++i)
        tree_insert(&tr, rand() % 10);
 
    tree_out_width(stdout, tr);
    tree_clear(tr);
    return 0;
}
 
//вставка
tree_t* tree_insert(tree_t** tr, int key){
    tree_t* p = *tr;
    while(p != NULL){
        if(key == p->key)//дубликаты откидываем
            return p;
        else if(key < p->key){
            tr = &p->left;
            p  = p->left;
        } else {
            tr = &p->right;
            p  = p->right;
        }
    }
 
    p = (tree_t*)malloc(sizeof(tree_t));
    if(p != NULL){
        p->key  = key;
        p->left = p->right = NULL;
        *tr = p;
    }
    return p;
}
 
//удаление всех
void tree_clear(tree_t* tr){
    if(tr != NULL){
        if(tr->left != NULL)
            tree_clear(tr->left);
        if(tr->right != NULL)
            tree_clear(tr->right);
        free(tr);
    }
}
 
//-----------------------------------------
void  queue_init(queue_t* q){ q->head = q->tail = NULL; }
int   queue_empty(queue_t* q) { return (q->head == NULL); }
const void* queue_front(queue_t* q) { return q->head->ptr; }
 
//добавление в очередь
int queue_push(queue_t* q, const void* ptr){
    node_t* p = (node_t*)malloc(sizeof(node_t));
    if(p != NULL){
        p->ptr  = ptr;
        p->next = NULL;
        if(q->head == NULL)
            q->head = q->tail = p;
        else {
            q->tail->next = p;
            q->tail = p;
        }
    }
    return (p != NULL);
}
 
//удаление из очереди
void queue_pop(queue_t* q){
    node_t* t;
    if(q->head != NULL){
        t       = q->head;
        q->head = q->head->next;
        free(t);
        if(q->head == NULL)
            q->tail = NULL;
    }
}