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

Dokonalý binární vyhledávací strom v C++ – C / C++ – Fórum – Programujte.comDokonalý binární vyhledávací strom v C++ – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Tommy95
~ Anonymní uživatel
1 příspěvek
28. 4. 2016   #1
-
0
-

Ahoj, potřebuji poradit jak vytvořit dokonalý binární vyhledávací strom/ nebo aspoň vyvážený. Hlavní problém mám s vytvořením rotací.

Můj kód: 

Tree.h

#ifndef _TREE_H_
#define _TREE_H_

#include <iostream>
#include <string>

using namespace std;

class Tree
{
private:

	class Node
	{
	public:
		string value;
		string value_in;
		Node* left;
		Node* right;

		Node(string);
	};

	Node* root;

	void internalInsertValue(string, Node*&);

	bool internalFindValue(string, Node*&);

	void internalPrintSorted(bool, Node*&);

	int internalGetLHeight(int, Node*);

	int internalGetRHeight(int, Node*);

	void internalRotateLeftOnce(Node*);

	void internalRotateRightOnce(Node*);

public:
	Tree(void) { this->root = NULL; }
	void insertValue(string);

	bool findValue(string);

	void printSorted(bool);

	int getLHeight(void);

	int getRHeight(void);

	void rotateLeftOnce();

	void rotateRightOnce();

};
#endif

Tree.cpp
#include "Tree.h"

#include <iostream>
#include <string>

using namespace std;


Tree::Node::Node(string value)
{
	this->value = value;
	this->left = this->right = NULL;
}

void Tree::insertValue(string value)
{
	internalInsertValue(value, this->root);

	return;
}

void Tree::internalInsertValue(string value, Node*& root)
{
	if (root == NULL) {
		root = new Node(value);
		return;
	}

	if (root->value == value) {
		return;
	}

	if (root->value > value) {
		internalInsertValue(value, root->left);
		return;
	}

	internalInsertValue(value, root->right);
	return;

}

bool Tree::findValue(string value)
{
	return(internalFindValue(value, this->root));
}

bool Tree::internalFindValue(string value, Node*& root)
{
	if (root == NULL)
		return(false);

	if (root->value == value)
		return(true);

	if (value < root->value)
		return(internalFindValue(value, root->left));

	return(internalFindValue(value, root->right));
}

void Tree::printSorted(bool desc)
{
	internalPrintSorted(desc, this->root);
	return;
}

void Tree::internalPrintSorted(bool desc, Node*& root)
{
	if (root == NULL)
		return;

	if (!desc)
	{
		internalPrintSorted(desc, root->left);
		cout << root->value << " ";
		internalPrintSorted(desc, root->right);
	}
	else
	{
		internalPrintSorted(desc, root->right);
		cout << root->value << " ";
		internalPrintSorted(desc, root->left);
	}

	return;
}

int Tree::getLHeight(void)
{
	return(internalGetLHeight(-1, this->root));
}

int Tree::internalGetLHeight(int h, Node* root)
{
	if (root == NULL)
		return(h);

	int lHeight = internalGetLHeight(h + 1, root->left);
	
	return(lHeight);
}

int Tree::getRHeight(void)
{
	return(internalGetRHeight(-1, this->root));
}

int Tree::internalGetRHeight(int h, Node* root)
{
	if (root == NULL)
		return(h);

	int rHeight = internalGetRHeight(h + 1, root->right);

	return(rHeight);
}

void Tree::rotateLeftOnce()
{
	if (getLHeight() < getRHeight())
	return(internalRotateLeftOnce(this->root));
}

void Tree::internalRotateLeftOnce(Node* root)
{
	Node*otherNode;
	otherNode = root->left;
	root->left = otherNode->right;
	otherNode->right = root;
	root = otherNode;
	return;
}

Main.cpp
#include "Tree.h"

#include <iostream>
#include<string>

using namespace std;

int main()
{
	Tree t;

	t.insertValue("acl");
	t.insertValue("aspx");
	t.insertValue("css3");
	t.insertValue("odbc");
	t.insertValue("postgre");
	t.insertValue("php5");
	t.insertValue("wysiwyg");
	
	t.printSorted(false);

	cout << "vyskaL" <<t.getLHeight() << endl;
	cout << "vyskaR" << t.getRHeight() << endl;
	
	system("pause");
	return(0);

}

Děkuji za rady

Nahlásit jako SPAM
IP: 193.165.24.–
Reklama
Reklama
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, 238 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ý