tree.h
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct elTreeB
{
char data[5];
int cnt;
struct elTreeB* left;
struct elTreeB* right;
struct elTreeB* parent;
};
typedef struct elTreeB wTreeB;
typedef wTreeB* node;
void printTree(node T, int deep);
void addEl(node* T,char* var, node p);
node* findEl(node* T, char* var);
node* maxT(node* T);
node* minT(node* T);
void delEl(node* T,char* var);
void prevAndNext(node T, char* var, node** prev, node** next);
main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"
int main()
{
node head = 0;
node head_2 = 0;
node* minMax = 0;
node* prev,* next = 0;
node* szuk = 0;
char var[5];
int choice;
while(1)
{
system("cls");
printf("-------- Drzewo Pierwsze --------\n ");
printTree(head, 0);
printf("-------- Drzewo Drugie --------\n ");
printTree(head_2, 0);
printf("\n1.Dodaj do pierwszego drzewa\n");
printf("2.Usun\n");
printf("3.Szukaj\n");
printf("4.Wyznacz min\n");
printf("5.Wyznacz max\n");
printf("6.Wyznacz poprzednika i nastepnika\n\n");
printf("Zadanie 16\n");
printf("7.Dodaj do drugiego drzewa\n");
printf("8.Porównanie drzew\n");
printf("0.Wyjdz z programu\n\n");
scanf("%i", &choice);
switch(choice)
{
case 0: return 0;
break;
case 1: printf("Podaj wartosc:");
scanf("%s", var);
addEl(&head, var, 0);
break;
case 2: printf("Podaj wartosc:");
scanf("%s", var);
delEl(&head, var);
break;
case 3: printf("Podaj wartosc:");
scanf("%s", var);
szuk = findEl(&head, var);
if (szuk)
printf("\nZnaleziono: %s\n", (*szuk)->data);
else
printf("\nNie znaleziono\n");
system("pause");
break;
case 4: minMax = minT(&head);
printf("\nMinimalny: %s\n", (*minMax)->data);
system("pause");
break;
case 5: minMax = maxT(&head);
printf("\nMaksymalny: %s\n", (*minMax)->data);
system("pause");
break;
case 6:
printf("Podaj wartosc:");
scanf("%s", var);
szuk = findEl(&head, var);
if (szuk)
printf("\nZnaleziono: %s\n", (*szuk)->data);
else
printf("\nNie znaleziono\n");
prevAndNext(head, (*szuk)->data, &prev, &next);
if (prev)
printf("\n Poprzednik: %s\n", (*prev)->data);
else
printf("Nie znaleziono poprzednika\n");
if (next)
printf("\n Nastepnik: %s\n", (*next)->data);
else
printf("Nie znaleziono nastepnika\n");
system("pause");
break;
case 7:printf("Podaj wartosc:");
scanf("%s", var);
addEl(&head_2, var, 0);
break;
case 8: if(compare(head, head_2, 0))
printf("\nDrzewa roznia sie!\n");
else
printf("\nDrzewa sa takie same\n");
system("pause");
break;
}
}
return 0;
}
tree.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"
int i;
// Wyswietlanie Drzewa
void printTree(node T, int deep)
{
if (T == NULL)
return;
printTree(T->left, deep+1);
for(i=0; i < deep; i++)
printf("---");
printf("%s\n", T->data);
printTree(T->right, deep+1);
}
// dodanie elementu do drzewa
void addEl(node* T,char* var, node p)
{
if (*T == 0) {
*T = malloc(sizeof(wTreeB));
if (*T) {
strcpy((*T)->data, var);
(*T)->cnt = 1;
(*T)->left = 0;
(*T)->right = 0;
(*T)->parent = p;
}
}
else if (strcmp(var,(*T)->data) < 0) {
addEl(&(*T)->left, var, *T);
}
else if (strcmp(var, (*T)->data) > 0) {
addEl(&(*T)->right, var, *T);
}
else {
(*T)->cnt++;
}
}
// Znalezienie elementu
node* findEl(node* T, char* var)
{
if (*T == 0)
return 0;
if (strcmp( var, (*T)->data) == 0)
return T;
if (strcmp( var, (*T)->data) > 0)
return findEl(&(*T)->right, var);
else
return findEl(&(*T)->left, var);
}
node* maxT(node* T)
{
while((*T)->right != 0)
T = &(*T)->right;
return T;
}
node* minT(node* T)
{
while((*T)->left != 0)
T = &(*T)->left;
return T;
}
// Usuniecie Elementu
void delEl(node* T, char* var)
{
node* toDel, us;
if (*T == 0)
return;
T = findEl(T, var);
if (T == 0)
return;
if ( (*T)->cnt > 1 ){
(*T)->cnt--;
return;
}
if ((*T)->left == 0 || (*T)->right == 0) {
toDel = T;
if ((*toDel)->right)
(*toDel)->right->parent = (*toDel)->parent;
else if ((*toDel)->left)
(*toDel)->left->parent = (*toDel)->parent;
}
else{
toDel = maxT(&(*T)->left);
free((*T)->data);
strcpy((*T)->data, (*toDel)->data);
(*T)->cnt = (*toDel)->cnt;
}
us = *toDel;
if ((*toDel)->left == 0)
*toDel = (*toDel)->right;
else
*toDel = (*toDel)->left;
free(us);
}
// Wyszukanie poprzednika i nastepnika
void prevAndNext(node T, char* var, node** prev, node** next)
{
node* El = findEl(&T, var);
if (El == 0) {
*prev = 0;
*next = 0;
return;
}
//poprzedni element
if ((*El)->left != 0) {
*prev = maxT(&(*El)->left);
}
else {
*prev = El;
while (**prev != 0 && strcmp((**prev)->data, (*El)->data) >= 0) {
*prev = &(**prev)->parent;
}
}
//następny element
if ((*El)->right != 0) {
*next = minT(&(*El)->right);
}
else {
*next = El;
while (**next != 0 && strcmp((**next)->data, (*El)->data) <= 0) {
*next = &(**next)->parent;
}
}
}
// sprawdzanie drzew
int compare(node A, node B, int X)
{
if (A == NULL || B == NULL)
{
if ((A == NULL && B) || (B == NULL && A))
X = 1;
return X;
}
X = compare(A->left, B->left, X);
if (strcmp(A->data, B->data) != 0)
X = 1;
X = compare(A->right, B->right, X);
return X;
}