Witam.
Napisałem sobie z pomocą książki moje drzewko. Niestety nie ma tam metody wyświetlającej w kolejności od najmniejszego do największego, jest jako zadanie domowe :/ No więc chciałem sobie je napisać ale kombinuje i nic nie mogę wymyślić, może ktoś pomoże. Tak wygląda co napisałem:
#include <iostream>
#include <cstdlib>
using namespace std;
struct Node
{
int key;
Node *leftChild;
Node *rightChild;
};
Node* insert (Node *node, int key){
if(node == NULL){ // jeśli nie mam drzewa
Node* newNode = new Node; // tworze nowe
newNode->leftChild = NULL; // przypisuję lewemu wartosc null
newNode->rightChild = NULL; // przypisuję prawemu wartosc null
newNode->key = key; //przypisuję wartosc do wezla
return newNode; // zwracam nowe drzewo
}
if(key < node->key){ // drzewo istenie. Sprawdzam wartosc wezla i dodaje na lewo albo prawo
node->leftChild = insert( node->leftChild, key ); // dodaję na lewo
}
else{
node->rightChild = insert( node->rightChild, key );
}
return node; // zwracam nowe drzewo
}
Node *search (Node *node, int key){
if ( node == NULL ){ // jeśli drzewo jest puste to nie ma czego zwrócić
return NULL;
}
else if ( key == node->key ){ // Jesli znajdziemy key konczymy
return node;
}// W przeciwnym razie probujemy szukac w lewym albo prawym poddrzewie
else if ( key < node->key ){
return search( node->leftChild, key );
}
else{
return search( node->rightChild, key );
}
}
void delTree (Node *node){
if ( node != NULL ){ // jeśli drzwo istnieje
delTree( node->leftChild ); // zniszcz lewego syna
delTree( node->rightChild ); // zniszcz prawego syna
delete node; //siebie
}
}
Node* delMaxNode (Node* node, Node* maxNode){
if( node == NULL ){
return NULL;
}
if( node == maxNode ){
return maxNode->leftChild;
}
node->rightChild = delMaxNode( node->rightChild, maxNode );
return node;
}
Node* searchMax(Node* node){
if( node == NULL ){
return NULL;
}
if( node->rightChild == NULL ){
return node;
}
return searchMax( node->rightChild );
}
Node* deleteNode(Node* node, int key){
if( node == NULL ){
return NULL;
}
if( node->key == key ){// jeśli usuniemy węzeł to sprawdzamy jego synow
if( node->leftChild == NULL ){
Node* rightTree = node->rightChild;
delete node;
return rightTree;
}
if( node->rightChild == NULL ){
Node* leftTree = node->leftChild;
delete node;
return leftTree;
}
Node* maxNode = searchMax( node->leftChild ); // jeśli nie usunelismy wezła to szukamy maxymalnego z lewewego poddrzewa
maxNode->leftChild = delMaxNode( node->leftChild, maxNode ); // pozniej musimy usunac maksymalny
maxNode->rightChild = node->rightChild;
delete node;
return maxNode;
}
else if( key < node->key ){ // jeśli nie usunelismy wezla z synami to przechodzimy do nich
node->leftChild = deleteNode( node->leftChild, key );
}
else{
node->rightChild = deleteNode( node->rightChild, key );
}
return node;
}
Node* inOrder(Node* node){
if (node == NULL){
return NULL;
}
}
int main (){
int choose = 0;
int key = 0;
Node *w_Tree = NULL;
while(true){
cout << "Co chcesz zrobic?\n\n1. Dodac wezel\n2. Usunac wezel\n3. Zniszczyc drzewo\n4. Sprawdzic, czy wezel znajduje sie w drzewie\n5. Wyjsc z programu\n";
cin >> choose;
switch (choose){
case 1:
cout << "Podaj wartosc: ";
cin >> key;
w_Tree = insert(w_Tree, key);
cout << "\nWartosc " << key << " dodano do drzewa\n\n";
break;
case 2:
cout << "Podaj wartosc do usunięcia: ";
cin >> key;
w_Tree = deleteNode(w_Tree, key);
cout << "\nWartosc " << key << " usunieta z drzewa\n\n";
break;
case 3:
delTree(w_Tree);
w_Tree = NULL;
cout << "\nDrzewo zniszczone\n\n";
break;
case 4:{
cout << "Podaj wartosc do sprawdzenia: ";
cin >> key;
Node* searchNode = search(w_Tree, key);
if (searchNode != NULL){
cout << "\nZnaleziono wezel\n\n";
}
else{
cout << "\nNie znaleziono wezla\n\n";
}
}
break;
case 5:
return 0;
default:
cout << "Niepoprawne dane wejsciowe...\n\n";
}
}
}