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

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

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

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

#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.

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

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

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!

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

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

#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.

#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.

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.

#13 Lorin
http://pastebin.com/i0R4ycdB .. u funkce deleteNode, je tam menší komentář

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

#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.