Drzewo binarne, suma kluczy

Question

Witam! Nie najlepiej radzę sobie z programowaniem więc proszę o cierpliwość

Mam za zadanie napisać funkcję, która znajdzie w drzewie ścieżkę o maksymalnej sumie kluczy i zwróci tę wartość jako wynik. Zostawiam moje nieudolne próby poniżej. Z góry dzięki!

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

typedef int ElType;

typedef struct Tree {
    ElType key;
    struct Tree *left;
    struct Tree *right;
} Tree;


Tree* InsertBST(Tree* t,int k)
{
    if (t == NULL) {
        Tree* w = (Tree*) malloc(sizeof(Tree));
        w->key = k;
        w->left = NULL;
        w->right = NULL;
        return w;
    }

    if (k <= t->key)
        t->left = InsertBST(t->left, k);
    else
        t->right = InsertBST(t->right, k);

    return t;
}

int NumberOfLeaves(Tree* t)
{
    if (t == NULL)
        return 0;

    if (t->left == NULL && t->right == NULL)
        return 1;

    return NumberOfLeaves(t->left) + NumberOfLeaves(t->right);
}


#define SCREEN_HEIGHT  100
#define SCREEN_WIDTH    80

typedef struct {
    int numberOfLines;
    char screen[SCREEN_HEIGHT][SCREEN_WIDTH+2]; // 100 linii, ka¿da linia ma 80 znaków plus \n i \0
} TreeDisplay;

/*
#define DOWN                    179
#define RIGHT_DOWN              191
#define DOWN_LEFT_AND_RIGHT     193
#define LEFT_DOWN               218
#define DASH                    196
*/

#define DOWN                    '|'
#define RIGHT_DOWN              '.'
#define DOWN_LEFT_AND_RIGHT     '^'
#define LEFT_DOWN               '.'
#define DASH                    '-'

    /* To find code for special characters:
    for (i = 0; i < 256; i++) {
        printf("%d:%c,\t", i, i);
        if (i % 5 == 0 && i > 0)
            printf("\n");
    }
    */

void WriteSymbolToTreeDisplay(TreeDisplay* td, char c, int row, int col)
{
    td->screen[row][col] = c;

    if (row+1 > td->numberOfLines)
        td->numberOfLines = row+1;
}

void WriteKeyToTreeDisplay(TreeDisplay* td, int key, int row, int col)
{
    if (key >= 1000)
        td->screen[row][col-1] = td->screen[row][col] = td->screen[row][col+1] = '.'; // za duza wartosc
    else if (key >= 100) {
        td->screen[row][col-1] = (key / 100) + '0';
        td->screen[row][col] = ((key / 10) % 10) + '0';
        td->screen[row][col+1] = (key % 10) + '0';
    }
    else if (key >= 10) {
        td->screen[row][col] = (key / 10) + '0';
        td->screen[row][col+1] = (key % 10) + '0';
    }
    else if (key >= 0)
        td->screen[row][col] = key + '0';
    else {
        td->screen[row][col] = '-';
        td->screen[row][col+1] = 'X';
    }

    if (row+1 > td->numberOfLines)
        td->numberOfLines = row+1;
}

int UpdateTreeDisplay(TreeDisplay* td, Tree* t, int depth, int left, int right)
// wypisz drzewo t do ekranu td w obszarze: pionowo od depth do SCREEN_HEIGHT, a poziomowo od left do right;
// funkcja zwraca pozimowa pozycje korzenia drzewa
{
    if (t == NULL)
        return -1;

    int left_width = NumberOfLeaves(t->left);
    int right_width = NumberOfLeaves(t->right);

    if (left_width + right_width == 0) {
        int middle = (left+right)/2;
        WriteKeyToTreeDisplay(td, t->key, depth, middle);
        return middle;
    }

    if (left_width == 0) {
        int middle = UpdateTreeDisplay(td, t->right, depth+2, left, right);
        WriteKeyToTreeDisplay(td, t->key, depth, middle);
        WriteSymbolToTreeDisplay(td, DOWN, depth+1, middle);
        return middle;
    }

    if (right_width == 0) {
        int middle = UpdateTreeDisplay(td, t->left, depth+2, left, right);
        WriteKeyToTreeDisplay(td, t->key, depth, middle);
        WriteSymbolToTreeDisplay(td, DOWN, depth+1, middle);
        return middle;
    }

    int k = (right - left - 2) / (left_width + right_width);
    int l = UpdateTreeDisplay(td, t->left, depth+2, left, left + left_width*k - 1);
    int r = UpdateTreeDisplay(td, t->right, depth+2, left + left_width*k + 1, right-1);

    int middle = (l+r)/2;
    WriteKeyToTreeDisplay(td, t->key, depth, middle);

    WriteSymbolToTreeDisplay(td, DOWN_LEFT_AND_RIGHT, depth+1, middle);
    WriteSymbolToTreeDisplay(td, LEFT_DOWN, depth+1, l);
    WriteSymbolToTreeDisplay(td, RIGHT_DOWN, depth+1, r);

    int i;
    for (i = l+1; i < middle; i++)
        WriteSymbolToTreeDisplay(td, DASH, depth+1, i);
    for (i = middle+1; i < r; i++)
        WriteSymbolToTreeDisplay(td, DASH, depth+1, i);

    return middle;
}

void DisplayTree(Tree* t)
{
    TreeDisplay TD;
    TD.numberOfLines = 0;
    int i, j;
    for (i = 0; i < SCREEN_HEIGHT; i++) {
        for (j = 0; j < SCREEN_WIDTH; j++)
            TD.screen[i][j] = ' '; // spacja
        TD.screen[i][SCREEN_WIDTH] = '\n';
        TD.screen[i][SCREEN_WIDTH+1] = '\0';
    }

    UpdateTreeDisplay(&TD, t, 0, 1, SCREEN_WIDTH - 1);

    for (i = 0; i < TD.numberOfLines; i++)
        printf("%s", TD.screen[i]);
    printf("\n");
}

int DisplayTrack(Tree* t, int k) /*Ta funkcja ma wyświetlać klucze na ścieżce od wierzchołka o danym kluczu do korzenia*/
{
    if (t == NULL) return NULL;
    if (t->left == NULL && t->right==NULL);
    printf("%d, ", t->key);
    if (k < t->key)
    {
        t->left = DisplayTrack(t->left, k);
        return t;
    }
    else if (k > t->key)
    {
        t->right = DisplayTrack(t->right, k);
        return t;
    }
    else if (t->left == NULL) {
        Tree* w = t->right;
        free(t);
        return w;
    }
}

int Sciezka(Tree* t) /*Ta funkcja ma znajdować ścieżkę o maksymalnej sumie kluczy i zwracać te sumę*/
{
    int k;
    if(t == NULL)
    return 0;
    if(t->left == NULL && t->right == NULL)
    return t->key;
    if (k < t->key)
    {
        t->left = Sciezka(t->left);
        return t->key;
    }
    else if (k > t->key)
    {
        t->right = Sciezka(t->right);
        return t->key;
    }
}

int main()
{
    printf("____________________________________________________________________________\n");

    int i;
    srand (time(NULL));

    Tree* t = NULL;
    for (i = 0; i < 20; i++)
        t = InsertBST(t, rand() % 1000);

    DisplayTree(t);

    int x;
 do{
    printf("\n____________________________________________________________________________\n");
    printf("(1) Najwieksza suma kluczy\n");
    printf("(2) Wyswietl klucze na sciezce od wierzcholka o danym kluczu do korzenia\n");
    printf("(3) Konczy program\n");
    printf("Wybierz numer operacji ktora chcesz wykonac: ");

    scanf("%d", &x);


        if(x==1)
        {
            
        };
        if(x==2)
        {
            ElType b;
            printf("Podaj klucz elementu: ");
            scanf("%d", &b);

            printf("Sciezka: ");
            t = DisplayTrack(t, b);
        }
        if(x==3)
        {
            printf("Zakonczono dzialanie programu\n");
            return ;
        }
    }while(x<4);
    return 0;
}

 

Answer 1

Nie chce mi się zagłębiać w ten twój kod, ale taka funkcja wygląda mniej więcej tak:

 

void maxPath(tree *root, int current_sum, int *max_sum)
{
    if(root)
    {
        current_sum += tree->key;
        if(max_sum < current_sum) *max_sum = current_sum;
        
        maxPath(root->left, current_sum, max_sum);
        maxPath(root->right, current_sum, max_sum);
    }
}

 

Comments

Chyba nadal coś źle robię :/ Poza tym mam problem później dostać się do tej funkcji z programu głównego, bo tam zmienne sumy obecnej i maksymalnej nie są zadeklarowane. Tak teraz wygląda ta funkcja,

int maxPath(Tree* t, int current_sum, int *max_sum)
{
    if(t == NULL)
    return 0;
    if(t->left == NULL && t->right == NULL)
    {
        current_sum = current_sum + t->key;
        max_sum = current_sum;
        return max_sum;
    }
   if(t->left != NULL || t->right != NULL)
   {
       current_sum = current_sum + t->key;
       if(max_sum < current_sum)
       max_sum = current_sum;
       maxPath(t->left, current_sum, max_sum);
       maxPath(t->right, current_sum, max_sum);

   }
}

 

---

ok, a po co to:

   if(t->left != NULL || t->right != NULL)
   {

przecież czy drzewo istnieje sprawdzamy już tutaj:

if(t == NULL)

    return 0;

 

max_path to wskaźnik. Zanim coś do niego przypiszesz trzeba go wyłuskać.

Zmienną max_path sb robisz na przykład w mainie, a do funkcji podajesz jej adres

---

Masz tutaj "podręcznikowy" przykład:

#include <iostream>

using namespace std;

struct tree
{
    int key;
    tree *left;
    tree *right;
};

tree *insert(tree *root, int key)
{
    if(root)
    {
        if(root->key > key) root->right =  insert(root->right, key);
        else root->left = insert(root->left, key);
    }
    else
    {
        root = new tree;
        root->key = key;

        root->left = NULL;
        root->right = NULL;
    }
    return root;
}

void maxPath(tree *root, int current_sum, int *max_sum)
{
    if(root)
    {
        current_sum += root->key;

        if(*max_sum < current_sum) *max_sum = current_sum;

        maxPath(root->left, current_sum, max_sum);
        maxPath(root->right, current_sum, max_sum);
    }
}

void deleteTree(tree *root)
{
    if(root)
    {
        deleteTree(root->left);
        deleteTree(root->right);

        delete root;
    }
}

int main()
{
    int tab[5] = {5,6,4,3,2};
    tree *root = NULL;

    for(int i = 0; i < 5; i++) root = insert(root, tab[i]);

    int max_path = 0;
    maxPath(root, 0, &max_path);

    cout<<max_path<<endl;

    deleteTree(root);

    return 0;
}

Przeanalizuj go, pomyśl jak działa rekurencja i napisz sobie funkcje jeszcze raz. Jakby co to pytaj

---

Przykład jest świetny ale jest w C++ i trochę się różni w kilku miejscach od C (np alokacja pamięci) więc przepisałem go na C. Odziwo zwracany wynik nie jest poprawny a co gorsza jest dokładnie taki sam jak ten, który otrzymywałem z kodem dwa komentarze wcześniej. Mianowicie zwraca mi: 6356704 Nie mam pojęcia dlaczego :(

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef int ElType;

typedef struct tree{
    ElType key;
    struct tree *left;
    struct tree *right;
} tree;

tree *insert(tree *root, int key)
{
    if(root != NULL)
    {
        if(root->key > key) root->right =  insert(root->right, key);
        else root->left = insert(root->left, key);
    }
    else
    {
        tree *root = (tree*) malloc(sizeof(tree));
        root->key = key;

        root->left = NULL;
        root->right = NULL;
    }
    return root;
}

void maxPath(tree *root, int current_sum, int *max_sum)
{
    if(root != NULL)
    {
        current_sum += root->key;

        if(*max_sum < current_sum) *max_sum = current_sum;

        maxPath(root->left, current_sum, max_sum);
        maxPath(root->right, current_sum, max_sum);
    }
}

void deleteTree(tree *root)
{
    if(root)
    {
        deleteTree(root->left);
        deleteTree(root->right);

        free(root);
    }
}

int main()
{
    int tab[5] = {10,6,4,3,2};
    tree *root = NULL;
    int i;

    for( i = 0; i < 5; i++)
    root = insert(root, tab[i]);

    int max_path = 0;
    maxPath(root, 0, &max_path);
    printf("%d",&max_path);


    deleteTree(root);

    return 0;
}

 

---

printf("%d",&max_path);

zamien na po prostu max_path. Ten operator - & sprawia że podajesz nie wartość zmiennej a jej adres. Poza tym wszystko jest chyba ok

---

Niestety chyba nie jest ok :/ Bo zwraca mi za każdym razem wynik 0

 

EDIT

Już znalazłem błąd. Przy alokacji pamięci nie zwróciłem wskażnika w odpowiednim miejscu. Chyba wszystko działa. Dzięki!

Answer 2

Zdaje że w drzewie binarnym każdy węzeł ma po swojej prawej stronie  (w sensie piętro niżej idąc w prawo) większy element, a po lewej mniejszy. Więc wystarczy ze od korzenia będziesz się poruszał cały czas w prawo. Chyba ze nie ma węzła po prawej stronie - wtedy w lewo. Az do momentu gdy trafisz na tzw. liść  (węzeł na ostatniej warstwie).

Comments

a co z taką sytuacją?

      5
    4   6
  3
2

Trzeba sprawdzać lewy i prawy węzeł

---

Hm, faktycznie, nie pomyślałem i tym.