Максимальный путь дерева

Question

Пожалуйста, помогите. Нужно создать двоичное дерево и вывести вывести самый длинный путь этого дерева. Я сделал добавление элементов к дереву и вывод дерева на экран, но не знаю как дальше.

#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
struct TNode
{
    int info; 
    struct TNode* left, * right;
};
typedef struct TNode Node;
void push(Node** t, int a)
{
    if (*t == NULL) 
    {
        *t = (Node*)malloc(sizeof(Node)); 
        (*t)->info = a;
        (*t)->left = (*t)->right = NULL; 
            return;
    }
    
    if (a > (*t)->info) push(&((*t)->right), a); 
    else push(&((*t)->left), a); 
}
 
void showTree(Node* t)
{
    if (t == NULL) return;
    showTree(t->left); 
    printf("%i ", t->info); 
    showTree(t->right); 
}
int main()
{
    Node* tree = NULL;
    int n; 
    int s; 
    printf("Enter number of items ");
    scanf("%i", &n);
    for (int i = 0; i < n; ++i)
    {
        printf("Enter information ");
        scanf("%i", &s); 
        push(&tree, s); 
    }
    printf("Tree\n");
    showTree(tree);
    return 0;
}

Answer 1

Сделайте процедуру обхода подобно вашей showtree, и передавайте на следующий уровень рекурсии глубину узла.

void walkTree(Node* t, int level)
  {
   if (t == NULL) return;
   walkTree(t->left, level + 1); 
   if (level > maxlevel) maxlevel = level;
   walkTree(t->right, level + 1); 
  }

Где-нибудь запомните наибольшую глубину, и при повторном обходе найдите этот узел с наибольшей глубиной, и возвращайтесь к корню, выводя всё по пути

БЛОГ НА HUSL

Максимальный путь дерева

Ответы (1 шт):