Binární vyhledávací strom (insert) – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Binární vyhledávací strom (insert) – C / C++ – Fórum – Programujte.comBinární vyhledávací strom (insert) – C / C++ – Fórum – Programujte.com

 

Toto vlákno bylo označeno za vyřešené — příspěvek s řešením.
Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Siggi0
Návštěvník
7. 4. 2015   #1
-
0
-

   

typedef struct Node {
    int key;
    struct Node* parent;
    struct Node* left;
    struct Node* right;
} Node;

typedef struct BinarySearchTree {
    Node* root;
} BinarySearchTree;

// nahoře je předdefinované
// dole napsané mnou

Node *createNode(int key){
    Node *newNode = malloc(sizeof(Node));	// vytvoření nového prvku v BVS
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Node *insertNodes(Node *node, int key){
    if(node == NULL){                                   //empty tree, add new node
        node = createNode(key);
	return node;
    }else if(key <= node->key){
        node->left = insertNodes(node->left, key);      // insert new node to left
	return node;
    }else{
        node->right = insertNodes(node->right, key);    // insert new node to right
	return node;
    }
}

void insertNode(BinarySearchTree *tree, int key) {	// předefinované
    insertNodes(tree->root, key);			// pro zjednodušení
/* nenastala žádná změna a nevím proč */
}

// v mainu

tree->root = NULL;

    insertNode(tree, 3);
			// tady nenastala žádná změna .. tree->root stále nulový
    if ((tree->root == NULL) || (tree->root->key != 3)) {
        printf("NOK - chybne vkladani do prazdneho stromu\n");
Nahlásit jako SPAM
IP: 46.229.123.–
Reklama
Reklama
Lorin0
Návštěvník
7. 4. 2015   #2
-
0
-

   

Node *insertNodes(Node **node, int key){ // << Zde změna
    if( *node == NULL ){ // << Zde změna
        node = createNode(key);
	return node;
    }else { // << Pro úklid a můj duševní klid
	if(key <= node->key){
        	node->left = insertNodes(node->left, key);
		return node;
	}else{
        	node->right = insertNodes(node->right, key);
		return node;
	}
    }
}

void insertNode( BinarySearchTree *tree, int key ) {
    insertNodes( &tree->root, key); // << Zde změna
}

// mělo by to fakčit
Nahlásit jako SPAM
IP: 89.190.72.–
ondrej39+1
Věrný člen
7. 4. 2015   #3
-
0
-

#2 Lorin
Asi by nebylo úplně od věci nahradit rekurzivní volání klasickým iteračním cyklem.

Nahlásit jako SPAM
IP: 213.226.234.–
Inject all the dependencies!
Siggi0
Návštěvník
7. 4. 2015   #4
-
0
-

#2 Lorin
K té rekurzi jsem se ani nedostal, protože to neprochází přes první test a to vkládání prvku do prázdného stromu. Změnil jsem to podle tebe a už mi to ani nevypíše nic, hned mi spadne program.

Dvakrát pointer a volání přímo &tree->root dělá humbuk.
Při pointer na pointer ** pak ztracím prvky ze struktury.

Když jsem tak pozoroval videa na YT, jakto pracuje, tak to mají podobné jako já. Ale po volání insertNodes( tree->root, key); se neprojeví změna, a ikdyž tam dám přímo adresu &, tak spadně program.

Nahlásit jako SPAM
IP: 46.229.123.–
Siggi0
Návštěvník
7. 4. 2015   #5
-
0
-

Pokud pomůže celý kód, aby jste se v tom zorientovali. Na delete funkci nekoukejte, je rozpracovaná a nedodělaná.

http://pastebin.com/VcqWq5Uk

Nahlásit jako SPAM
IP: 46.229.123.–
Řešení
Lorin0
Návštěvník
7. 4. 2015   #6
-
+1
-
Zajímavé
Vyřešeno Nejlepší odpověď

 Omlouvám se, chtělo to dodatečné úpravy.

#include <cstdio>
#include <cstdlib>

typedef struct Node {
    int key;
    struct Node* parent;
    struct Node* left;
    struct Node* right;
} Node;

typedef struct BinarySearchTree {
    Node* root;
} BinarySearchTree;

// nahoře je předdefinované
// dole napsané mnou

Node *createNode(int key){
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Node *insertNodes(Node **node, int key){
    if( *node == NULL){
      *node = createNode(key);
	    return *node;
    } else {
      if( key <= (*node)->key){
        (*node)->left = insertNodes( &((*node)->left), key);
        return *node;
      } else {
        (*node)->right = insertNodes( &((*node)->right), key); 
        return *node;
      }
    }
}

void insertNode(BinarySearchTree *tree, int key) {
    insertNodes( &tree->root, key);
}

int main () {
  BinarySearchTree *tree = (BinarySearchTree*)malloc(sizeof(BinarySearchTree));
  tree->root = NULL;
  insertNode( tree, 3);

  if ((tree->root == NULL) || (tree->root->key != 3)) {
    printf("NOK - chybne vkladani do prazdneho stromu\n");
  } else {
    printf("Pointer: %p, Key: %i", tree->root, tree->root->key);
  }
}
 

Vyprázdnění paměti nechávám na vás ;)

Nahlásit jako SPAM
IP: 89.190.72.–
Siggi0
Návštěvník
7. 4. 2015   #7
-
0
-

Takhle mi už to funguje, můžeš mi to polopatě vysvětlit? :)

Nahlásit jako SPAM
IP: 46.229.123.–
Lorin0
Návštěvník
8. 4. 2015   #8
-
+1
-
Zajímavé

Pokud budu vycházet z původního zápisu funkce insertNodes:

insertNodes( Node* node, int key ) { 
    // něco dělá
}

//volání
insertNodes( tree->root, 3 )

znamená to, že zavoláním funkce insertNodes vytváříš novou proměnnou node, která bude ukazovat na to, na co ukazuje root.

Jestliže root už nějaký obsah měl (ukazoval na platnou strukturu Node) pak změnou proměnné node

node->key = 11;

dosáhneš změny i v tree->root->key.

Pokud ale root, potažmo node bude obsahovat NULL, přiřazením nějaké hodnoty do node už nezměníš to, kam ukazuje root. Po ukončení platnosti funkce insertNodes se proměnná node smaže a ty o data přijdeš.

V jiném případě, kdy bys do funkce chtěl dostat proměnnou, kterou ve funkci chceš měnit (bez toho abys ji musel vracet, například proto, že návratovou hodnotu chceš použít jako indikaci (ne)zdaru) použil bys ukazatel:

int cislo = 10;
foo( int * i ) {
	// neco dela
}
foo( &cislo );

Root ale už ukazatel je, jednoduché doplnění ampersandu do volání funkce insertNodes( &root->child, 3) bude mít za následek chybovou hlášku:

main.cpp:23:22: error: cannot convert 'Node**' to 'Node*' for argument '1' to 'Node *insertNodes(Node*, int)'

Což už tě samo navádí k tomu, že potřebuješ ukazatel na ukazatel.

insertNodes(Node **node, int key) {
	// něco dělá
}

// Volání
insertNodes( &tree->root, key);

Tím vytvoříš po volání funkce proměnnou, která ukazuje na root. K root se dostaneš pomocí *node. Editací této proměnné upravuješ zároveň proměnnou root. Proto ti po zániku lokální proměnné node zůstanou všechna data v pořádku až do smazání tree->root.

Whew, jestli jsi to dočetl až sem, máš u mě palec hore!

Nahlásit jako SPAM
IP: 89.190.72.–
Siggi0
Návštěvník
8. 4. 2015   #9
-
0
-

#8 Lorin
Děkuji moc za vysvětlení :). Už je mi to jasnější. 

Nahlásit jako SPAM
IP: 46.229.123.–
Siggi0
Návštěvník
8. 4. 2015   #10
-
0
-

Jestli mohu ještě dotaz, ale ohledně smazání.
Při dvou potomků, mi hází error. viz koment. 

Node *deleteNodes(Node *node, int value){
    if(node == NULL){                                               // if tree is empty, return node
        return node;
    }else if(value < (node)->key){                                  // searching node keys below root
        (node)->left = deleteNodes(((node)->left), value);
    }else if(value > node->key){                                    // searching node keys above root
        node->right = deleteNodes(node->right, value);
    }else{                                                          // founded
        if(node->left == NULL || node->right == NULL){              // nodes haven't left and right child
            free(node);
            node = NULL;
        }else if(node->left == NULL){                               // nodes have only one child
            Node *temp = node;
            node = node->right;
            free(temp);
        }else if(node->right == NULL){
            Node *temp = node;
            node = node->left;
            free(temp);
        }else{                                                      // nodes have two children
            Node *temp = findMin(node->right);
            node->key = temp->key; 
/* tady mi padá program, při změně klíče kořene na nejnižší pravého podstromu 
jinak se zdá, že by to mělo fungovat a nebo taky ne */
            node->right = deleteNodes(node->right, temp->key);
        }
    }
    return node;
}

void deleteNode(BinarySearchTree *tree, Node *node) {
    deleteNodes(tree->root, node->key);
}
Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
8. 4. 2015   #11
-
0
-

#10 Siggi
Sigii, jen k zamyšlení. Když hodláš něco ze stromu smazat, úplně první, co bys měl udělat, je podívat se, zda se mazaný prvek ve stromu vůbec nachází. Pokud tam není, tak logicky nic mazat nemusíš, protože stejně nic nesmažeš.

Pokud se hledaný prvek != NULL, tedy ve stromě existovat bude, můžeš si ho přiřadit do pomocného, dočasného pointeru a teprve poté začít něco mazat.

Nahlásit jako SPAM
IP: 213.226.234.–
Inject all the dependencies!
Siggi0
Návštěvník
8. 4. 2015   #12
-
0
-

#11 ondrej39
Ale já tam mám hledání klíče, jestli se vyskytuje ve stromě. To jsou ty dvě rekurze na začátku, jedna hledá od vrcholu doprava a druhá doleva. Jenom tam nemám přesně napsané, že když se nebude vyskytovat, tak by mělo udělat to a to. Ale děkuji za připomínku. 

Jde o to, že s těma dvou synama je to řešené tak, že se najde minimální prvek v pravém podstromě, (dále kámen úrazu) vezme se klíč kořene a přepíše se na klíč nahrazeného kořene. Když tam dám natvrdo jakkékoliv číslo kromě 4, tak to funguje. Smaže se nejmenší prvek v pravém podstromu, nahradí kořen a spojí se uzly. Ale jak tam dám 4, tak program hned spadne. Bude v tom asi prkotina, ale já nevidím souvislost.

Nahlásit jako SPAM
IP: 46.229.123.–
Lorin0
Návštěvník
9. 4. 2015   #13
-
0
-

Sice to není řešení tvého problému, ale ty podmínky ve funkci deleteNodes máš nějaké divné. Hoď zase celý kód na pastebin, prosím.

Nahlásit jako SPAM
IP: 89.190.72.–
Siggi0
Návštěvník
9. 4. 2015   #14
-
0
-
Nahlásit jako SPAM
IP: 46.229.123.–
Lorin0
Návštěvník
9. 4. 2015   #15
-
0
-

Než jsem se dostal k nějakým opravám, jen jsem přepsal podmínky ve funkci deleteNodes. Pokud máš dobře napsané ty testy, pak byl zakopaný pudl právě zde. Nic nepadá, ve výpisu je OK. I dosazení 4 funguje.

Node *deleteNodes(Node *node, int value){
	// Pokud je node prázdný
	if( node != NULL ) {
		
		// Pokud je hodnota nodu větší než předaná hodnota		      
		if ( value < node->key ) {
		        node->left = deleteNodes(node->left, value);

		// Pokud je hdonota menší než předaná hodnota
		} else if ( value > node->key ) {
		        node->right = deleteNodes(node->right, value);

		// Pokud je hodnota nodu shodná s předanou hodnotou
		} else {
		
			// Pokud nod nemá právého ani levého potomka
			if( node->left == NULL && node->right == NULL){              
		            free(node);
        		    node = NULL;
			
			// Pokud má potomka napravo
			} else if( node->left == NULL){                               
		            Node *temp = node;
		            node = node->right;
		            free(temp);

			// Pokud má potomka nalevo
		        } else if(node->right == NULL){
		            Node *temp = node;
		            node = node->left;
		            free(temp);
			
			// Pokud má dva potomky
			} else {
				Node *temp = findMin(node->right);
			        node->key = temp->key;
			        node->right = deleteNodes(node->right, temp->key);
        		}
      		}
    	}
    	return node;
}
Nahlásit jako SPAM
IP: 89.190.72.–
Siggi0
Návštěvník
9. 4. 2015   #16
-
0
-

#15 Lorin
Já se na to vykašlu :D, už vidím tu chybu, kde mi to padalo, ať už to bylo napsáno původně a nebo podle tebe :D :).

na řádku 102: if(node->left == NULL && node->right == NULL) jsem já místo && měl jsem || a proto mi to padalo. :)

Děkuji, za ochotu a žes na to kouknul.

Nahlásit jako SPAM
IP: 46.229.123.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 87 hostů

Podobná vlákna

Binární strom — založil garamond

Binární strom — založil Tomáš

Binární strom — založil Michaela

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý