Форум АНТИЧАТ

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)
-   С/С++, C#, Delphi, .NET, Asm (https://forum.antichat.xyz/forumdisplay.php?f=24)
-   -   Как выращивают бинарные деревья. (https://forum.antichat.xyz/showthread.php?t=67147)

ph0en1x 12.04.2008 17:08
Как выращивают бинарные деревья.
 
Собственно хотелось бы разобраться как оно создается и как с ним работать.
Я в общих чертах представляю себе что это такое, а как оно выглядит в коде не знаю,
поиск вразумительных результатов не дал:(

Forcer 12.04.2008 18:56
Цитата:
поиск вразумительных результатов не дал
что-то не верится )) структуры данных - одна из самых популярных тем в программировании. google -> бинарные деревья. Первая же ссылка:
Бинарные деревья

desTiny 12.04.2008 19:11
лови и от меня привет:
http://algolist.manual.ru/ds/btree.php

reversys 12.04.2008 22:12
А если всё-же решишь не писать уже миллион раз написанное, то стандартная библиотека шаблонов (STL) и в часности контейнер set тебе в помощь.

ph0en1x 13.04.2008 12:21
А есть какой нибудь робочий пример?
Исходник программы с использованием дерева?

вот нашол по одному из линков которые вы оставили:
Код:
/* binary search tree */

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

typedef int T;                  /* type of item to be stored */
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

typedef struct Node_ {
    struct Node_ *left;        /* left child */
    struct Node_ *right;        /* right child */
    struct Node_ *parent;      /* parent */
    T data;                    /* data stored in node */
} Node;

Node *root = NULL;              /* root of binary tree */

Node *insertNode(T data) {
  Node *x, *current, *parent;

  /***********************************************
    *  allocate node for data and insert in tree  *
    ***********************************************/

    /* find x's parent */
    current = root;
    parent = 0;
    while (current) {
        if (compEQ(data, current->data)) return (current);
        parent = current;
        current = compLT(data, current->data) ?
            current->left : current->right;
    }

    /* setup new node */
    if ((x = malloc (sizeof(*x))) == 0) {
        fprintf (stderr, "insufficient memory (insertNode)\n");
        exit(1);
    }
    x->data = data;
    x->parent = parent;
    x->left = NULL;
    x->right = NULL;

    /* insert x in tree */
    if(parent)
        if(compLT(x->data, parent->data))
            parent->left = x;
        else
            parent->right = x;
    else
        root = x;

    return(x);
}

void deleteNode(Node *z) {
    Node *x, *y;

  /*****************************
    *  delete node z from tree  *
    *****************************/

    /* y will be removed from the parent chain */
    if (!z || z == NULL) return;

    /* find tree successor */
    if (z->left == NULL || z->right == NULL)
        y = z;
    else {
        y = z->right;
        while (y->left != NULL) y = y->left;
    }

    /* x is y's only child */
    if (y->left != NULL)
        x = y->left;
    else
        x = y->right;

    /* remove y from the parent chain */
    if (x) x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        root = x;

    /* y is the node we're removing */
    /* z is the data we're removing */
    /* if z and y are not the same, replace z with y. */
    if (y != z) {
        y->left = z->left;
        if (y->left) y->left->parent = y;
        y->right = z->right;
        if (y->right) y->right->parent = y;
        y->parent = z->parent;
        if (z->parent)
            if (z == z->parent->left)
                z->parent->left = y;
            else
                z->parent->right = y;
        else
            root = y;
        free (z);
    } else {
        free (y);
    }
}

Node *findNode(T data) {

  /*******************************
    *  find node containing data  *
    *******************************/

    Node *current = root;
    while(current != NULL)
        if(compEQ(data, current->data))
            return (current);
        else
            current = compLT(data, current->data) ?
                current->left : current->right;
    return(0);
}

int main(int argc, char **argv) {
    int i, *a, maxnum, random;

    /* command-line:
    *
    *  bin maxnum random
    *
    *  bin 5000        // 5000 sequential
    *  bin 2000 r      // 2000 random
    *
    */
    maxnum = atoi(argv[1]);
    random = argc > 2;

    if ((a = malloc(maxnum * sizeof(*a))) == 0) {
        fprintf (stderr, "insufficient memory (a)\n");
        exit(1);
    }

    if (random) { /* random */
        /* fill "a" with unique random numbers */
        for (i = 0; i < maxnum; i++) a[i] = rand();
        printf ("ran bt, %d items\n", maxnum);
    } else {
        for (i=0; i<maxnum; i++) a[i] = i;
        printf ("seq bt, %d items\n", maxnum);
    }


    for (i = 0; i < maxnum; i++) {
        insertNode(a[i]);
    }

    for (i = maxnum-1; i >= 0; i--) {
        findNode(a[i]);
    }

    for (i = maxnum-1; i >= 0; i--) {
        deleteNode(findNode(a[i]));
    }
    return 0;
}
но компилятор ругается:
Код:
main.cpp:37: error: invalid conversion from `void*' to `Node*'
main.cpp:144: error: invalid conversion from `void*' to `int*'
исправить не получилось никак может подскажите что-нибудь?

desTiny 13.04.2008 17:35
Цитата:
Цитата:
Операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в дереве.

reversys 14.04.2008 03:40
рабочий пример (msdn)

Код:
#include <set>
#include <iostream>

using namespace std ;

typedef set<int> SET_INT;

void truefalse(int x)
{
  cout << (x?"True":"False") << endl;
}

int main() {
  SET_INT s1;
  cout << "s1.insert(5)" << endl;
  s1.insert(5);
  cout << "s1.insert(8)" << endl;
  s1.insert(8);
  cout << "s1.insert(12)" << endl;
  s1.insert(12);

  SET_INT::iterator it;
  cout << "it=find(8)" << endl;
  it=s1.find(8);
  cout << "it!=s1.end() returned ";
  truefalse(it!=s1.end());  //  True

  cout << "it=find(6)" << endl;
  it=s1.find(6);
  cout << "it!=s1.end() returned ";
  truefalse(it!=s1.end());  // False
}

KSoniX 14.04.2008 12:55
ph0en1x
Цитата:
вот нашол по одному из линков которые вы оставили: код
в 37 строке будет так

Цитата:
if ((x = (Node*)malloc (sizeof(*x))) == 0) {
а в 144 строке будет так

Цитата:
if ((a = (int*)malloc(maxnum * sizeof(*a))) == 0) {
если я не ошибаюсь то все должно компилируется


Время: 19:32