Cześć, napisałem własną implementację drzewa binarnego za pomocą struktury. Prosiłbym o obiektywną ocenę mojej wersji, chciałbym się dowiedzieć który fragment wykonałem niezbyt elegancko, czy funkcje typu void nie powinny jednak być typu "węzeł" (node), ogólnie jestem otwarty na wszelkie uwagi, gdyż sposób wypracowałem praktycznie samodzielnie, a nie chcę uczyć się złych nawyków.
Kod:
#include "stdafx.h"
#include <iostream>
using namespace std;
typedef struct node //pretty obvious part
{
int value;
node *left;
node *right;
} node;
typedef struct tree //root is the very first element of our tree, current stands for currently used element
{
node *root;
node *current;
} tree;
void initialize(struct tree *t) //Making initial tree
{
t->root = NULL;
t->current = NULL;
}
void addValue(struct tree *t, int value)
{
if (t->root == NULL) //If working on initial tree
{
t->root = new node; //dynamic memory allocation
t->root->value = value; //passing the value
t->root->left = NULL; //as we've just initialized our tree, it's a lonely parent
t->root->right = NULL;
}
else //Tree's not empty!
{
bool placed = false; //Just so we know whether placing's finished or not
while (placed == false)
{
while (value >= t->current->value && placed ==false) //Keep going along right branch if inserted value is bigger than or equal to the actual
{
if (t->current->right != NULL) //If right branch is not empty
t->current = t->current->right; //go along right branch
else //RIGHT BRANCH IS EMPTY!
{
t->current->right = new node; //Dynamic memory allocation, for parrent to be
t->current = t->current->right;
t->current->value = value;
t->current->right = NULL;
t->current->left = NULL;
placed = true; //Placing part's done.
}
}
while (value < t->current->value) //Analogically if value is smaller than current
{
if (t->current->left != NULL)
t->current = t->current->left;
else
{
t->current->left = new node;
t->current = t->current->left;
t->current->value = value;
t->current->right = NULL;
t->current->left = NULL;
placed = true;
}
}
}
}
t->current = t->root; //Next time, we would like to add a value, we have to start process from the root
}
void print(struct tree *t) //Simple printing function
{
char dir;
if (t->current == t->root) //First use of our function - we don't want to double-print our current parent
{
cout << "Root "<<t->root->value << endl;
cout << " ------------Instruction Manual------------ " << endl;
cout << "'a' or 'l' to go to left branch" << endl;
cout << "'d' or 'r' to go to right branch" << endl;
dir = getchar();
}
while (dir != EOF)
{
if(dir!='\n') //We're confirming our choice with enter, so let's prevent printing twice
if ((dir == 'a' || dir == 'l') && t->current->left != NULL) //'a' or 'l' - go to the left branch if it's not empty!
{
t->current = t->current->left;
cout << t->current->value << endl;
}
else if ((dir == 'd' || dir == 'r') && t->current->right != NULL) //'d' or 'r' - go to the right branch if it's not empty!
{
t->current = t->current->right;
cout << t->current->value << endl;
}
else //Let's hope no forbidden button's been pressed ^^. If there's no element in that branch let's make user aware of that.
cout << "No more elements!" << endl;
dir = getchar();
}
}
int main()
{
/*Just an example*/
char c;
tree tree1;
initialize(&tree1);
addValue(&tree1, 10);
addValue(&tree1, 6);
addValue(&tree1, 14);
addValue(&tree1, 5);
addValue(&tree1, 8);
addValue(&tree1, 11);
addValue(&tree1, 18);
addValue(&tree1, 12);
addValue(&tree1, 7);
addValue(&tree1, 121);
addValue(&tree1, 2);
addValue(&tree1, 13);
addValue(&tree1, 11);
print(&tree1);
getchar();
}