• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Drzewo binarne, suma kluczy

Object Storage Arubacloud
0 głosów
530 wizyt
pytanie zadane 7 czerwca 2017 w C i C++ przez teusiek Początkujący (280 p.)

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

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;
}

 

2 odpowiedzi

+1 głos
odpowiedź 7 czerwca 2017 przez Żyrosławw Bywalec (2,300 p.)
wybrane 10 czerwca 2017 przez teusiek
 
Najlepsza

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);
    }
}

 

komentarz 8 czerwca 2017 przez teusiek Początkujący (280 p.)

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);

   }
}

 

komentarz 8 czerwca 2017 przez Żyrosławw Bywalec (2,300 p.)

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

komentarz 8 czerwca 2017 przez Żyrosławw Bywalec (2,300 p.)

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

komentarz 8 czerwca 2017 przez teusiek Początkujący (280 p.)

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;
}

 

komentarz 8 czerwca 2017 przez Żyrosławw Bywalec (2,300 p.)
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

komentarz 9 czerwca 2017 przez teusiek Początkujący (280 p.)
edycja 10 czerwca 2017 przez teusiek
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!
0 głosów
odpowiedź 7 czerwca 2017 przez criss Mędrzec (172,590 p.)
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).
komentarz 7 czerwca 2017 przez Żyrosławw Bywalec (2,300 p.)
a co z taką sytuacją?

      5
    4   6
  3
2

Trzeba sprawdzać lewy i prawy węzeł
komentarz 7 czerwca 2017 przez criss Mędrzec (172,590 p.)
Hm, faktycznie, nie pomyślałem i tym.

Podobne pytania

0 głosów
3 odpowiedzi 270 wizyt
pytanie zadane 22 kwietnia 2017 w C i C++ przez teusiek Początkujący (280 p.)
0 głosów
0 odpowiedzi 109 wizyt
pytanie zadane 1 lutego 2019 w C i C++ przez gorgonkowa Obywatel (1,810 p.)
+1 głos
3 odpowiedzi 762 wizyt
pytanie zadane 26 lutego 2018 w C i C++ przez Kurczak Użytkownik (940 p.)

92,558 zapytań

141,407 odpowiedzi

319,569 komentarzy

61,945 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...