Drzewo binarne - uzupełnianie.

maci3k90

2010-01-02T14:34:14+01:00

Rejestracja: dni
Ostatnio: dni

0

Witam wszystkich forumowiczów, bo to mój pierwszy post ;) Mam nadzieję, że ktoś znajdzie chwilkę i mi pomoże. Ogólnie drzewo binarne jest dla mnie niezrozumiałe, bez sensu i nie wiem w ogóle po co ono komu ?!

Mam takie oto zadanie:

Utworzyć strukturę pozwalającą przechować elementy drzewa binarnego.
Napisać funkcję tworzącą drzewo binarne z podanego ciągu 10 liczb.
Napisać funkcję wyszukującą zadany element w danym drzewie binarnym (argumentami są: wskaźnik na korzeń drzewa, wartość szukanego elementu). Funkcja powinna zwracać wskaźnik na dany element drzewa, lub w przypadku nie znalezienia takiego elementu w drzewie – wartość NULL.

I to co zrobiłem:

cw2.cpp

Kopiuj

#include "cw2.h"

void Initialize()
{
root=new PROGRAM;
root->liczba=0;
root->wl=NULL;
root->wp=NULL;  
current=root;
}

PROGRAM Pobierz(PROGRAM *element)
{
float tab[10];
printf("Podaj 10 liczb: ");
}

int main()
{
    Initialize();
    Pobierz();
    getch();
}

cw2.h

Kopiuj

#ifndef __CW2_H
#define __CW2_H
#include <stdio.h>
#include <conio.h>
#include <string.h>

struct PROGRAM
{
       float liczba;
       PROGRAM *wl;
       PROGRAM *wp;
};

PROGRAM *root;
PROGRAM *current;

#endif

No i właśnie. W ogóle to zadanie wg. mnie bez sensu, no ale trudno.
Jak przeszukać takie drzewo znalazłem w internecie. Ale jak je uzupełnić tymi liczbami nie mam pojęcia ;) proszę o pomoc ! ;)

Ermes

2010-01-02T14:44:02+01:00

Rejestracja: dni
Ostatnio: dni

0

też robię drzewo binarne, tylko że robię dodatkowo jeszcze klasę i template, ale zasada ta sama, u mnie metoda dodająca jednego liścia w odpowiedni sposób do drzewa wygląda tak:

kazdy liść, ma lewego i prawego syna oraz rodzica, (left, rigth, parent) u ciebie będzie jakby sam klucz (key - twoja "liczba") bo masz tylko liczby, a je da się łatwo porównać

Kopiuj

template<class K, class V>
    	void BSTreeAVL<K,V>::Add(const K& key,const V& value)
    	{
    	    Node** nd = &main_node;
    	    Node* np = 0;

    	    while(*nd != 0)
    	    {
    			if ((*nd)->getKey() == key) return;
    			if (key < (*nd)->getKey())
    			{
    				np = *nd;
    				nd = (*nd)->getLeft();
    			}
    			else
    			{
    				np = *nd;
    				nd = (*nd)->getRight();
    			}
    	    }

    	    *nd = new Node(key, value, np); // Node(k, v, parent)
    	    ++count;
    	}

zajrzyj na temat, http://4programmers.net/Forum/viewtopic.php?id=154033 tam wpisałem część kodu, może Ci to pomoże, jeśli będziesz miał więcej pytań pytaj ;)

maci3k90

2010-01-02T15:30:48+01:00

Rejestracja: dni
Ostatnio: dni

0

Mógłbyś wkleić jeszcze ciała funkcji GetRight, GetLEft i GetKey?? Z góry dzięki ;)

Ermes

2010-01-02T16:54:35+01:00

Rejestracja: dni
Ostatnio: dni

0

te funkcje nic nie robią poza tym, że zwracają wskaźniki do synów, albo rodzica, czy tam wartość klucza, to są takie funkcje dostępu do tego co jest w Nodzie :) u ciebie to będzie po prostu node->lewy jak do zwykłego pola itp.

tak wygląda cały Node:

Kopiuj

 template<class K, class V>
	class Node
	{
	    public:
		Node(K k, V v);
		Node(K k, V v, Node* p);
		Node(Node& n);
		Node& operator= (const Node& n);
		~Node();

		inline K getKey() const { return key; }
		inline V getValue() const { return value; }
		inline void setKey(K key) { this->key = key; }
		inline void setValue(V value) { this->value = value; }

		inline int getBalance() const { return balance; }
		inline Node** getLeft() { return &left; }
		inline Node** getRight() { return &right; }
		inline Node** getParent() { return &parent; }

		inline void setBalance(int balance) { this->balance = balance; }
		inline void setLeft(Node *left) { this->left = left; }
		inline void setRight(Node *right) { this->right = right; }
		inline void setParent(Node *parent) { this->parent = parent; }

	    private:
		Node();
		Node* left;
		Node* right;
		Node* parent;

		K key;
		V value;

		int balance;
	};