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

Drzewo binarne

Object Storage Arubacloud
0 głosów
271 wizyt
pytanie zadane 22 kwietnia 2017 w C i C++ przez teusiek Początkujący (280 p.)
edycja 23 kwietnia 2017 przez teusiek

Witam, mam problem ze stworzeniem funkcji która będzie wyświetlać klucze na ścieżce od wierzchołka o danym kluczu (który będę wprowadzać z klawiatury) aż do korzenia. Poniżej załączam kod. Z góry dziękuje za pomoc!

#include <stdio.h>
#include <stdlib.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);
}

Tree* DeleteMaxOfBST(Tree* t, ElType *deleted_value)
{
    // zakladam, ze drzewo t jest nie puste,
    // ale na wszelki przypadek ...
    if (t == NULL) {
        *deleted_value = -1;
        return NULL;
    }

    if (t->right == NULL) {
        *deleted_value = t->key;
        Tree* w = t->left;
        free(t);
        return w;
    }

    t->right = DeleteMaxOfBST(t->right, deleted_value);
    return t;
}

Tree* DeleteNodeOfBST(Tree* t, int k)
{
    if (t == NULL) return NULL;

    if (k < t->key) {
        t->left = DeleteNodeOfBST(t->left, k);
        return t;
    }
    else if (k > t->key) {
        t->right = DeleteNodeOfBST(t->right, k);
        return t;
    }
    else if (t->left == NULL) {
        Tree* w = t->right;
        free(t);
        return w;
    }
    else {
        ElType max_left;
        t->left = DeleteMaxOfBST(t->left, &max_left);
        t->key = max_left;
        return t;
    }
}

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

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

}


int main()
{

    int i;
    srand (time(NULL));

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

    DisplayTree(t);

    int x;
    printf("(1) Usun dany klucz\n");
    printf("(2) Wyświetl klucze na ścieżce od wierzchołka o danym kluczu do korzenia\n");
    printf("(3) Konczy program")
    printf("Wybierz numer operacji ktora chcesz wykonac: \n");

    scanf("%d", &x);

    if(x==1)
    {
        ElType a;
        printf("Podaj klucz elementu do usuniecia: ");
        scanf("%d", &a);

        if (a == -1)
            return;

        t = DeleteNodeOfBST(t, a);

        printf("Po usunieciu %d:\n", a);
        DisplayTree(t);
    };
    if(x==2)
    {
        
    }

    return 0;
}

 

komentarz 23 kwietnia 2017 przez niezalogowany
A na czym polega ten problem?
komentarz 23 kwietnia 2017 przez teusiek Początkujący (280 p.)

Chyba nie wszystko działa poprawnie bo zdarza się ze czasami wyświetla się o jeden element za dużo. Do tego nie wiem jak odwrócić te elementy żeby wyświetlały sie w odwrotnej kolejności. To jest ta funkcja:

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

 

3 odpowiedzi

0 głosów
odpowiedź 25 kwietnia 2017 przez mokrowski Mędrzec (156,140 p.)
wybrane 3 czerwca 2017 przez teusiek
 
Najlepsza
#include <stdio.h>
#include <stdlib.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);
}

Tree* DeleteMaxOfBST(Tree* t, ElType* deleted_value) {
    // zakladam, ze drzewo t jest nie puste,
    // ale na wszelki przypadek ...
    if(t == NULL) {
        *deleted_value = -1;
        return NULL;
    }

    if(t->right == NULL) {
        *deleted_value = t->key;
        Tree* w = t->left;
        free(t);
        return w;
    }

    t->right = DeleteMaxOfBST(t->right, deleted_value);
    return t;
}

Tree* DeleteNodeOfBST(Tree* t, int k) {
    if(t == NULL) { return NULL; }

    if(k < t->key) {
        t->left = DeleteNodeOfBST(t->left, k);
        return t;
    } else if(k > t->key) {
        t->right = DeleteNodeOfBST(t->right, k);
        return t;
    } else if(t->left == NULL) {
        Tree* w = t->right;
        free(t);
        return w;
    } else {
        ElType max_left;
        t->left = DeleteMaxOfBST(t->left, &max_left);
        t->key = max_left;
        return t;
    }
}

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

void DisplayTrack(Tree* t, int k) { 
    struct Tree *next = t;
    if(t == NULL) {
        return;
    }
    if(t->left != NULL || t->right != NULL) {
        next = t->key > k ? t->left: t->right;
        DisplayTrack(next, k);
        printf(" %d", t->key);
    } else if(t->key != k) {
        printf("W tej ścieźce poszukiwań nie znaleziono wartości: ");
        printf("%d", next->key);
    } else {
        printf("%d", k);
    }
}


int main() {
    int i;
    srand(time(NULL));
    Tree* t = NULL;

    for(i = 0; i < 20; i++)
    { t = InsertBST(t, rand() % 1000); }

    DisplayTree(t);
    int x;
    printf("(1) Usun dany klucz\n");
    printf("(2) Wyświetl klucze na ścieżce od wierzchołka o danym kluczu do korzenia\n");
    printf("(3) Konczy program");
    printf("Wybierz numer operacji ktora chcesz wykonac: \n");
    scanf("%d", &x);

    if(x == 1) {
        ElType a;
        printf("Podaj klucz elementu do usuniecia: ");
        scanf("%d", &a);

        if(a == -1)
        { return EXIT_FAILURE; }

        t = DeleteNodeOfBST(t, a);
        printf("Po usunieciu %d:\n", a);
        DisplayTree(t);
    };

    if(x == 2) {
        int key;
        printf("Podaj klucz elementu do kótórego ścieżkę chcesz uzyskać: ");
        scanf("%d", &key);
        DisplayTrack(t, key);
        putchar('\n');
    }

    return EXIT_SUCCESS;
}

 

0 głosów
odpowiedź 24 kwietnia 2017 przez Wiciorny Ekspert (271,710 p.)

Jeśli nadal potrzebujesz pomocy, jutro posiedze nad tym chwilę popołudniem i dam znać ;] ! laugh

0 głosów
odpowiedź 25 kwietnia 2017 przez Marcin_N_97 Stary wyjadacz (10,290 p.)
Nie przeglądałem Twojego kodu, ale z tego co widzę to mogę Ci poradzić, byś poczytał o przejściach pre-order, post-order oraz in-order. Lekko modyfikując je możesz otrzymać to co ma realizować funkcja z tym komentarzem: "/*Ta funkcja ma wyświetlać klucze na ścieżce od wierzchołka o danym kluczu do korzenia*/".

Jeżeli nadal będziesz miał z tym problem oraz @Wiciorny nie znajdzie czasu by Ci pomóc to napisz jak najdokładnie w czym leży problem, który chcesz rozwiązać, a w weekend przysiądę nad tym ;)

Podobne pytania

0 głosów
2 odpowiedzi 558 wizyt
pytanie zadane 7 czerwca 2017 w C i C++ przez teusiek Początkujący (280 p.)
0 głosów
0 odpowiedzi 112 wizyt
pytanie zadane 1 lutego 2019 w C i C++ przez gorgonkowa Obywatel (1,810 p.)
+1 głos
3 odpowiedzi 782 wizyt
pytanie zadane 26 lutego 2018 w C i C++ przez Kurczak Użytkownik (940 p.)

92,666 zapytań

141,564 odpowiedzi

320,022 komentarzy

62,033 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

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!

...