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