Binarne drzewo przeszukiwań. Metoda inOrder.

0

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

Do wypisania drzewa potrzebujesz 3 rzeczy:

  • go left
  • go right
  • print node

W zależności od tego w jakiej kolejności je wykonasz możesz uzyskać 3 standardowe metody przechodzenia drzewa: pre order, in order i post order. Mamy więc funkcję

void printTree(Node* node){
}

Zobacz co się dzieje w takich 3 sytuacjach:

//pre order
void printTree(Node* node){
    if(node!=NULL){
        cout<<node->key;
        printTree(node->left);
        printTree(node->right);
    }
}
//in order
void printTree(Node* node){
    if(node!=NULL){
        printTree(node->left);
        cout<<node->key;
        printTree(node->right);
    }
}
//post order
void printTree(Node* node){
    if(node!=NULL){
        printTree(node->left);
        printTree(node->right);
        cout<<node->key;
    }
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1