binarytree.cpp - master - wonguk/Laboratory_work_5

binarytree.cpp
440 строк11 KB
wonguk
update: binarytree.cpp
19 фев 2026, 17:09
19 фев 2026, 17:091a794fb
#include "binarytree.h"
#include <iostream>
#include <queue>
#include <cstdio>
#include <string>
using namespace std;


// Конструктор
BinaryTree::BinaryTree() : root(nullptr) {}

// Добавление элемента
bool BinaryTree::insert(const EmployeeData&	data){
	if (search(data.id) != nullptr){
		return false;
	}
	
	root = insertRecursive(root, data);
	return true;
}

TreeNode* BinaryTree::insertRecursive(TreeNode* node, const EmployeeData& data){
	if(node == nullptr){
		TreeNode* newNode = new TreeNode;
		newNode->data = data;
		newNode->left = nullptr;
		newNode->right = nullptr;
		return newNode;
	}
	
	if(data.id < node->data.id){
		node->left = insertRecursive(node->left, data);
	} else {
		node->right = insertRecursive(node->right, data);
	}
	
	return node;
}

// Поиск элемента по ключу
TreeNode* BinaryTree::search(int id){
	return searchRecursive(root, id);
}

TreeNode* BinaryTree::searchRecursive(TreeNode* node, int id){
	if(node == nullptr || node->data.id == id){
		return node;
	}
	
	if (id < node->data.id){
		return searchRecursive(node->left, id);
	} else {
		return searchRecursive(node->right, id);
	}
}

// Удаление элемента по ключу
bool BinaryTree::remove(int id){
	if (search(id) == nullptr){
		return false;
	}
	
	root = removeRecursive(root, id);
	return true;
}

TreeNode* BinaryTree::removeRecursive(TreeNode* node, int id){
	if (node == nullptr){
		return nullptr;
	}
	
	if (id < node->data.id){
		node->left = removeRecursive(node->left, id);
	} else if (id > node->data.id){
		node->right = removeRecursive(node->right, id);
	} else {
		// Найден узел для удаления
		if (node->right == nullptr && node->left == nullptr){
			// Узел без потомков
			delete node;
			return nullptr;
		} else if(node->left == nullptr){
			// Узел с одним правым потомком
			TreeNode* temp = node->right;
			delete node;
			return temp;
		} else if(node->right == nullptr){
			// Узел с одним левым потомком
			TreeNode* temp = node->left;
			delete node;
			return temp; 
		} else {
			// Узел с двумя потомками
			TreeNode* minRight = findMin(node->right);
            node->data = minRight->data;
			node->right = removeRecursive(node->right, minRight->data.id);
		}
	}
	return node;
} 

TreeNode* BinaryTree::findMin(TreeNode* node){
	while (node->left != nullptr){
		node = node->left;
	}
	return node;
}

// Удалить все элементы, у которых "специальность" совпадает с заданным значением специальности.
int BinaryTree::removeBySpecialty(std::string specialty){
	int count = 0;
	count = removeBySpecialtyRecursive(root, specialty);
	return count;
}

int BinaryTree::removeBySpecialtyRecursive(TreeNode*& node, std::string specialty){
	if(node == nullptr){
		return 0;
	}
	int count = 0;
	
	// Проверяем левое поддерево
	count += removeBySpecialtyRecursive(node->left, specialty);
	
	// Проверяем правое поддерево
	count += removeBySpecialtyRecursive(node->right, specialty);
	
	// Проверяем текущий узел
	if(node->data.specialty == specialty){
		int id = node->data.id;
		node = removeRecursive(node, id);
		count++;
	}
	
	return count;
}

// А1: Вывод элементов с заданным стажем и специальностью
void BinaryTree::printByExperienceAndSpecialty(int minExp, int maxExp, const string& specialty){
	cout << "\nExperience from " << minExp << " to " << maxExp
		 << " and specialty '" << specialty << "':" << endl;
	cout << "===================================" << endl;
	
	int found = 0;
	printByExperienceAndSpecialtyRecursive(root, minExp, maxExp, specialty, found);
	
	if (found == 0){
		cout << "These employees not founded" << endl;
	}
}

void BinaryTree::printByExperienceAndSpecialtyRecursive(TreeNode* node, int minExp, int maxExp,
														const string& specialty, int& found){
	if (node != nullptr){
		printByExperienceAndSpecialtyRecursive(node->left, minExp, maxExp, specialty, found);
		
		if (node->data.experience >= minExp &&
			node->data.experience <= maxExp &&
			node->data.specialty == specialty){
				printEmployee(node->data);
				found++;
			}
		printByExperienceAndSpecialtyRecursive(node->right, minExp, maxExp, specialty, found);
	}
}

// А2: Вывод фамилий и окладов
void BinaryTree::printNamesAndSalaries() const{
	cout << "\nAll colleagues's names and salary: " << endl;
	cout << "==================================" << endl;
	printNamesAndSalariesRecursive(root);
}

void BinaryTree::printNamesAndSalariesRecursive(TreeNode* node) const{
	if (node != nullptr){
		printNamesAndSalariesRecursive(node->left);
		
		cout << node->data.fullName << ": "
			 << node->data.salary << "ruble" << endl;
		
		printNamesAndSalariesRecursive(node->right);
	}
}

// А2: Средний оклад для заданного стажа
double BinaryTree::averageSalaryForExperience(int targetExp){
	double totalSalary = 0.0;
	int count = 0;
	
	averageSalaryForExperienceRecursive(root, targetExp, totalSalary, count);
	
	if (count > 0){
		return totalSalary / count;
	}
	return 0.0;
}

void BinaryTree::averageSalaryForExperienceRecursive(TreeNode* node, int targetExp,
													 double& totalSalary, int& count){
	if (node != nullptr){
		averageSalaryForExperienceRecursive(node->left, targetExp, totalSalary, count);
		
		if (node->data.experience == targetExp){
			totalSalary += node->data.salary;
			count++;
		}
		
		averageSalaryForExperienceRecursive(node->right, targetExp, totalSalary, count);
	}
}

// А4: Удаление дубликатов по фамилии и табельному номеру
int BinaryTree::removeDuplicates(){
	int removedCount = 0;
	removedCount = removeDuplicatesRecursive(root);
	return removedCount;
}

int BinaryTree::removeDuplicatesRecursive(TreeNode*& node){
	if (node == nullptr){
		return 0;
	}
	
	int removedCount = 0;
	removedCount += removeDuplicatesRecursive(node->left);
	
	if (hasDuplicateBefore(node->data)){
		int idToRemove = node->data.id;
		
		node = removeRecursive(node, idToRemove);
		removedCount++;
		
		removedCount += removeDuplicatesRecursive(node);
	} else {
		removedCount += removeDuplicatesRecursive(node->right);
	}
	return removedCount;
}

// Проверка, есть ли дубликат этого элемента в дереве
bool BinaryTree::hasDuplicateBefore(const EmployeeData& data)  {
	return hasDuplicateBeforeRecursive(root, data, false);
}

//bool BinaryTree::hasDuplicateBeforeRecursive(TreeNode* node, const EmployeeData& data, bool foundSelf) {
	if (node == nullptr) return false;
	
	if (hasDuplicateBeforeRecursive(node->left, data, foundSelf)) {
		return true;
	}
	
	if (node->data.fullName == data.fullName){
		if (node->data.id == data.id){
			foundSelf = true;
		} else if (!foundSelf){
			return true;
		}
	}
	return false;
}


// Обход дерева в ширину и печать элементов
void BinaryTree::breadFirstTraversal(){
	if (root == nullptr){
		cout << "Tree empty." << endl;
		return;
	}
	
	queue<TreeNode*> q;
	q.push(root);
	
	cout << "Breadth-First Search(BFS):" << endl;
	int level = 1;
	
	while(!q.empty()){
		int levelSize = q.size();
		cout << "\nLevel" << level++ << ":" << endl;
		
		for (int i = 0; i < levelSize; i++){
			TreeNode* current = q.front();
			q.pop();
			
			printEmployee(current->data);
			
			if(current->left != nullptr){
				q.push(current->left);
			}
			if (current->right != nullptr){
				q.push(current->right);
			}
		}
	}
	
}

//	обход дерева в глубину и печать элементов, прямой, симметричный (по возраста-нию и убыванию) и обратный.
void BinaryTree::preOrderTraversal() {
	cout << "Direct bypass (pre-order): " << endl;
	preOrderRecursive(root);
	cout << endl;
}

void BinaryTree::preOrderRecursive(TreeNode* node){
	if (node != nullptr){
		cout << node->data.id << " ";
		preOrderRecursive(node->left);
		preOrderRecursive(node->right);
	}
}

void BinaryTree::inOrderTraversal(){
	cout << "InOrder-increase" << endl;
	inOrderRecursive(root);
	cout << endl;
}

void BinaryTree::inOrderRecursive(TreeNode* node){
	if (node != nullptr){
		inOrderRecursive(node->left);
		cout << node->data.id << " ";
		inOrderRecursive(node->right);
	}
}

void BinaryTree::inOrderTraversalDesc(){
	cout << "InOrder-decrease" << endl;
	inOrderRecursiveDesc(root);
	cout << endl;
}

void BinaryTree::inOrderRecursiveDesc(TreeNode* node){
	if(node != nullptr){
		inOrderRecursiveDesc(node->right);
		cout << node->data.id << " ";
		inOrderRecursiveDesc(node->left);
	}
}

void BinaryTree::postOrderTraversal(){
		cout << "Post-Order" << endl;
		postOrderRecursive(root);
		cout << endl;
}

void BinaryTree::postOrderRecursive(TreeNode* node){
	if (node != nullptr){
		postOrderRecursive(node->left);
		postOrderRecursive(node->right);
		cout << node->data.id << " ";
	}
}

bool BinaryTree::saveToFile(const string& filename){
	FILE* file = fopen(filename.c_str(), "w");  
	if (file == nullptr){
		return false;
	}
	saveRecursive(root, file);
	fclose(file);
	return true;
}

void BinaryTree::saveRecursive(TreeNode* node, FILE* file){
	if (node != nullptr){
		fprintf(file, "%d|%s|%d|%.2f|%s\n",
						node->data.id,
						node->data.fullName.c_str(),
						node->data.experience,
						node->data.salary,
						node->data.specialty.c_str());
		saveRecursive(node->left, file);
		saveRecursive(node->right, file);
	}
}

bool BinaryTree::loadFromFile(const string& filename){
	clear();
	
	FILE* file = fopen(filename.c_str(), "r");
	if (file == nullptr){
		return false;
	}
	
	char line[256];
	while (fgets(line, sizeof(line), file)){
		line[strcspn(line, "\n")] = 0;
		
		EmployeeData emp;
		char* token = strtok(line, "|");
		if (token) emp.id = atoi(token);
		
		token = strtok(nullptr, "|");
		if (token) emp.fullName = token;
		
		token = strtok(nullptr, "|");
		if (token) emp.experience = atoi(token);
		
		token = strtok(nullptr, "|");
		if (token) emp.salary = atof(token);
		
		token = strtok(nullptr, "|");
		if (token) emp.specialty = token;
		
		insert(emp);
	}
	
	fclose(file);
	return true;
}

bool BinaryTree::isEmpty(){
	return root == nullptr;
}

void BinaryTree::clear(){
	clearRecursive(root);
		root = nullptr;
}

void BinaryTree::clearRecursive(TreeNode* node){
	if (node != nullptr){
		clearRecursive(node->left);
		clearRecursive(node->right);
		delete node;
	}
}

 Подсчет количества элементов
int BinaryTree::count() const{
	return countRecursive(root);
}

int BinaryTree::countRecursive(TreeNode* node){
	if (node == nullptr){
		return 0;
	}
	
	return 1 + countRecursive(node->left) + countRecursive(node->right);
}