Как выращивают бинарные деревья.

[ph0en1x]

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

[Forcer]

поиск вразумительных результатов не дал
что-то не верится )) структуры данных - одна из самых популярных тем в программировании. google -> бинарные деревья. Первая же ссылка:
Бинарные деревья (http://trubetskoy1.narod.ru/alg/bintree.html)

[desTiny]

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

[reversys]

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

[ph0en1x]

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

вот нашол по одному из линков которые вы оставили:
/* 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]

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

[reversys]

рабочий пример (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]

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

if ((x = (Node*)malloc (sizeof(*x))) == 0) {

а в 144 строке будет так

if ((a = (int*)malloc(maxnum * sizeof(*a))) == 0) {

если я не ошибаюсь то все должно компилируется