Динамічні структури даних

{

go_for_lustok_2(rt->left);

go_for_lustok_2(rt->right);

if ( ((rt->left == NULL) & (rt->right == NULL)) & (rt->data!=root->data) ) {

 

second_rule(&rt);

 

}

 

}

return;

}

 

template <class T>  

void BinaryTree<T>::go_for_lustok_1(TreeElement *rt) {

if (rt != NULL) // доки не кінець дерева

{

go_for_lustok_1(rt->left);

go_for_lustok_1(rt->right);

if ( ((rt->left == NULL) & (rt->right == NULL)) & (rt->data!=root->data) ) {

 

if (rt->data.length()>1){

first_rule(&rt);

}

 

  }

}

return;

}

 

//функція запису  слів в масив

template <class T>

void BinaryTree<T>::input_words(int count)

{

int i;

for (i=0;i<count;i++) {

cout << "A[" << i+1 << "]=";

cin >> A[i];

}

}

 

template <class T>  

void BinaryTree<T>::check_comb(TreeElement *rt, int stan) {//перевіряє всі можливі комбінації //підслів

int i; 

string vuz;

if(stan!=0)

{

comb = "";

for(i=0;i<count;i++) tmp[i] = A[i];

}

 

 

if (rt!=NULL) {

if ( (rt->left==NULL) & (rt->go_l!=1) ) {//ДРУГА УМОВА ВІДКИДАЄ ЗАЙВІ ВУЗЛИ, ПО ЯКИХ ХОДИЛИ

vuz = "0";

//шукаємо чи є  вузол в масиві

for (i=0;i<count;i++) {

if ( (rt->data==tmp[i]) & (comb!="0") ) {

vuz = tmp[i];

tmp[i] = "";

}

}

 

if (vuz!="0") {

if (comb=="") comb = comb + vuz; //якщо перший елемент, то не потрібно риски

else

comb = comb +"-" + vuz;

 

} else comb = "0";

 

 

 

}

 

if ((rt->left==NULL) & (rt->right==NULL)) {

find_db_vuzol(rt); //ШУКАЄМО НАЙБЛИЖЧИЙ “РОЗДВОЄНИЙ” ВУЗОЛ І ВІДМІЧАЄМО ТЕ, ЩО МИ //ВІДВІДАЛИ ОДНУ З ГІЛОК

 

//Починаємо пошук  нової комбінації

if (comb!="0") cout << comb << endl;

check_comb(root,1);

}

if (rt->go_l!=1) check_comb(rt->left,0);

if (rt->go_r!=1) check_comb(rt->right,0);

}

 

}

 

template <class T>  

void BinaryTree<T>::find_db_vuzol(TreeElement *rt) {//в якості параметра отримуємо листок

 

if ( (rt->left!=NULL) & (rt->right!=NULL) )  {//якщо подівйний

//Якщо в лівому  вузлі ще нне були, то помічаємо,  що були

if (rt->go_l!=1) rt->go_l = 1;

else {

rt->go_r=1;

}

//якщо дабл вузол  і має 2 одиниці то до його  батька не потрібно йти по  нову комбінацію

if ( (rt->go_l==1) & (rt->go_r==1) & (rt!=root) ) {

find_db_vuzol(rt->parent);

}

 

} else {

find_db_vuzol(rt->parent);

}

 

}

 

 

template <class T>

void BinaryTree<T>::Reverse_way(TreeElement *rt) // послідовність листків дерева при проходженні його у зворотньому порядку

{

if (rt)

{

Reverse_way(LeftSon(rt));

Reverse_way(RightSon(rt));,

if ( rt->right!=NULL & rt->left!=NULL) cout << rt->parent->data;

cout << rt->data << " ";

}

}

 

template <class T>

void BinaryTree<T>::second_rule(TreeElement **rt) { 

if ((*rt)->parent->right!=(*rt)) {//якщо я правий нащадок, то мені не можна розподілятись

TreeElement *add = new TreeElement; // виділення пам"яті під ел.

add->data = ((*rt)->parent)->data.substr((*rt)->data.length(),((*rt)->parent)->data.length()); // заносим в інформаційне поле

add->left = add->right = NULL; // занулюєм Вказівники на наступні ел.

add->parent = *rt;

add->plv = 0;

add->go_r=0;

(*rt)->right = add;  // з"єднуєм з деревом

} 

 

}

 

template <class T>

void BinaryTree<T>::first_rule(TreeElement **rt) { 

 

  if((*rt)->plv<(*rt)->data.length()-1) {

TreeElement *add = new TreeElement; // виділення пам"яті під ел.

add->data = (*rt)->data.substr(0,(*rt)->plv+1); // заносим в інформаційне поле

add->left = add->right = NULL; // занулюєм Вказівники на наступні ел.

add->parent = *rt;

add->plv = (*rt)->plv++;

add->go_l=0;

(*rt)->left = add;  // з"єднуєм з деревом

 

 

TreeElement *add1 = new TreeElement; // виділення пам"яті під ел.

add1->data = (*rt)->data; // заносим в інформаційне поле

add1->left = add1->right = NULL; // занулюєм Вказівники на наступні ел.

add1->plv = (*rt)->plv++;

add1->parent = *rt;

add1->go_r=0;

(*rt)->right = add1;  // з"єднуєм з деревом

 

 

first_rule(&(*rt)->right); //рекурсія з вказівником на правого нащадка

 

  }

 

}

 

template <class T>

bool BinaryTree<T>::Add(TreeElement **rt, T item) // додавання ел. в БД

{

if (*rt == NULL) // якщо корінь

{

TreeElement *add = new TreeElement; // виділення пам"яті під ел.

add->data = item; // заносим в інформаційне поле

add->left = add->right = NULL; // занулюєм Вказівники на наступні ел.

add->plv = root->plv++;

*rt = add;  // з"єднуєм з деревом

}

else

{

if (item < ((*rt)->data))

Add(&((*rt)->left), item); // переходим на наступний лівий

else

Add(&((*rt)->right), item); // переходим на наступний правий

}

return true;

}

template <class T>

void BinaryTree<T>::Del_Help(TreeElement **root_ptr, TreeElement **del_node_ptr) // допоміжна ф-я для Delete

{

if (LeftSon(*root_ptr)) // якщо лівий ел. != NULL

Del_Help(&((*root_ptr)->left), del_node_ptr); // виконуєм цю ф-ю для наступного лівого ел.

else // в іншому випадку

{

(*del_node_ptr)->data = (*root_ptr)->data; // заміщуєм інформаційне поле

*del_node_ptr = *root_ptr; // присвоюєм адресу для видалення

*root_ptr = RightSon(*root_ptr); // підтягуєм нижній елемент

}

}

template <class T>

bool BinaryTree<T>::Delete(TreeElement **rt, T item) // видалення заданого ел.

{

TreeElement *del;

if (*rt) // якщо не кінець дерева

if (item < (*rt)->data)

Delete(&((*rt)->left), item); // проходим на лівий

else  if (item > (*rt)->data)

Delete(&((*rt)->right), item); // проходим на правий

else

{

del = *rt; // зберігаєм адресу елемента для видалення

if (!del->right) // якшо немає правого елемента

*rt = LeftSon(del); // ставим замість ньго лівий

else if (! LeftSon(del)) // якшо немає лівого елемента

*rt = RightSon(del); // ставим замість ньго правий

else  // якщо є 2 елементи

if (! LeftSon(del))

*rt = RightSon(del);

else

Del_Help(&del->right, &del); // виклик допоміжної ф-ї

delete del; // видаляєм вузол

}

return true;

}

template <class T>

void BinaryTree<T>::PrintTree(TreeElement *rt, int k, int i)

{

char c;

if (rt != NULL) // доки не кінець дерева

{

cout << endl;

for (c = 1; c <= 40 + i; c++)

cout << " "; // відступ

cout << rt->data; // вивід інф. поля

// рекурсивний виклик  ф-й

PrintTree(rt->left, k/2, i-k);

PrintTree(rt->right, k/2, i+k);

}

return;

}