В бинарном дереве найти длину (число ветвей) пути от корня до ближайшей вершины - C (СИ)

Узнай цену своей работы

Формулировка задачи:

В заданном непустом бинарном дереве найти длину (число ветвей) пути от корня до ближайшей вершины со значением, равным заданному. Использовать алгоритм обратного обхода. Надеюсь, сможете помочь, собственно, с написанием алгоритма для нахождения длины пути. Все остальное написала, но здесь- я в тупике, было несколько идей, но что-то пошло не так. Заранее благодарна
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
struct btree {
    btree() :e(), l(), r() {}
    int e;
    btree *l, *r;
};
 
struct list {
    btree *z;
    list *next;
};
typedef list stack;
 
stack *iinput(btree *x, stack *head) {//добавление элемента в стек
    stack *s;
    s = new list;
    s->z = x;
    s->next = head;
    head = s;
    return head;
}
 
btree *gget(stack **head) {//взятие элемента из стека
    btree *x = (*head)->z;
    stack *g = (*head)->next;
    *head = NULL;
    *head = g;
    return x;
}
 
void add(btree **t, int value){//ввод дерева
    if (*t == NULL) {
        *t = new btree;
        (*t)->e = value;
    }
    else  {
        btree *t2 = *t;
        while (t2 != NULL)  {
            if (t2->e < value)  { //Направо 
                if (t2->r == NULL)  {
                    t2->r = new btree;
                    t2->r->e = value;
                    t2 = NULL;  }
                else  {
                    t2 = t2->r; }   }
            else{ //Налево 
                if (t2->l == NULL)  {
                    t2->l = new btree;
                    t2->l->e = value;
                    t2 = NULL;  }
                else  {
                    t2 = t2->l;
}}}}}
 
void obh(btree *d) {//вычисление длины пути до ближайшей вершины с подходящим значением
    stack *S = NULL; int F = 1, x;
    printf("zadaite zna4enie  \n");
    scanf("%d", &x);
    while (F){
        while (d != NULL) {
            S = iinput(d, S);
            d = d->l;
        } 
        if (S != NULL) { 
            d = gget(&S);
 
//добавить действия
 
            d = d->r;
        }
        else F = 0;
    }
    printf("dlina puti= %d \n", p);
}
 
int main(){
    int x;
    btree *T = NULL;
    printf("vvedite derevo \n");
    while ((_kbhit() == 0) && (_getch() != 27)) {
        scanf("%d", &x);
        add(&T, x);
    }
    printf("okon4en vvod dereva \n");
    obh(T);
    _getch();
}

Решение задачи: «В бинарном дереве найти длину (число ветвей) пути от корня до ближайшей вершины»

textual
Листинг программы
#include <limits.h>
 
int path_length(btree* root, int needed) {
    if ( ! root ) // значение не найдено
        return INT_MIN;
    if ( root->e == needed )
        return 0;
    return 1 + path_length( ( (root->e > needed ) ? root->l : root->r), needed);
}
 
/*...*/
// где-то в программе 
int len, needed;
btree* root;
//...
if ( ( len = path_length(root, needed) ) < 0 )
  // не найдено
else
  // в len длина пути

Объяснение кода листинга программы

Представленный код - это рекурсивная функция, которая использует бинарное дерево для поиска пути от корня до ближайшей вершины, удовлетворяющей определенному условию (в данном случае, когда значение равно needed). Вот список, объясняющий, что происходит в коде:

  1. *int path_length(btree root, int needed)** - это функция, которая принимает два аргумента: root, который является узлом в бинарном дереве, и needed, которое является значением, которое мы ищем.
  2. if ( ! root ) - проверка, является ли root пустым. Если это так, функция возвращает INT_MIN, что означает, что путь не найден.
  3. if ( root->e == needed ) - проверка, равно ли значение в узле root требуемому значению needed. Если это так, функция возвращает 0, что означает, что путь найден.
  4. return 1 + path_length( ( (root->e > needed ) ? root->l : root->r), needed); - рекурсивный вызов функции path_length для левого или правого поддерева (в зависимости от того, больше ли значение в текущем узле, чем needed). Это продолжается, пока не будет найдено совпадение или пока не будет достигнут корень дерева.
  5. В другом месте программы, функция вызывается с помощью len = path_length(root, needed). Если значение len меньше нуля, это означает, что путь не найден. В противном случае, len содержит длину пути.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

12   голосов , оценка 3.917 из 5
Похожие ответы