|
Читайте также: |
Удаление узла производится только тогда, когда узел не пустой и его левый и правый сыновья уже удалены.
Команда root=NULL имеет смысл только когда удаляется корень дерева.
3.4. Операции с идеально сбалансированными деревьями
Построение дерева
Рассмотрим подпрограмму create (int number, tree *&root), которая используется для формирования идеально сбалансированного дерева. Она имеет два формальных параметра: number – количество узлов в формируемом дереве; root – указатель на корень дерева. Первый узел полагается корнем формируемого дерева, после чего определяется количество узлов в левом поддереве numberLeft = number/2, количество узлов в правом поддереве numberRight = number- numberLeft -1. Далее numberLeft узлов рекурсивно заносится в левое поддерево текущего узла, оставшиеся numberRight узлов рекурсивно заносятся в правое поддерево текущего узла. Таким образом, для каждого узла количество узлов в левом поддереве отличается от количества узлов в правом поддереве не больше чем на единицу.
void create (int number, tree *&root)
{int a;
if (number>0)
{
root=new tree;
cin>>a;
root->inf=a;
root->left=root->right=NULL;
int numberLeft=number/2, numberRight=number-numberLeft-1;
create(numberLeft, root->left);
create(numberRight, root->right); }
}
Пример 7. Если во входном файле указать количество узлов 10, а затем перечислить те же самые узлы, что и в примере 3 (10, 7, 25, 31, 18, 6, 3, 12, 22, 8), то получим дерево, представленное на рис. 3.6.
Рис. 3.6. Идеально сбалансированное дерево
Поиск по дереву
Для реализации поиска элемента в идеально сбалансированном дереве можно использовать модификацию любого вида обхода дерева. В следующем листинге будет приведена модификация прямого обхода:
void search (int x, tree *root)
{if (root) // если дерево не пустое
if (x==root->inf) /* и значение узла равно x, то выводим сообщение об успешности поиска и выходим из подпрограммы */
{ cout<<"search is successful";return; }
else {search(x, root->left); // иначе обходим левое и правое поддеревья
search(x, root->right);
}
}
Удаление дерева
Операция удаления идеально сбалансированного дерева ничем не отличается от удаления дерева двоичного поиска (см. 3.2. Операции с деревьями двоичного поиска).
3.3. Решение практических задач с использованием деревьев
1. В файле input.txt хранится последовательность целых чисел. Построить по этой последовательности дерево двоичного поиска и вывести в файл output.txt листья этого дерева.
_____________________________prim1.cpp_______________________________
#include <fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
struct tree
{
int inf;
tree *left, *right;
};
tree *root;
void add (int x, tree *&root)
{if (!root)
{
root=new tree;
root->inf=x;
root->left=root->right=NULL;
}
else if (x<root->inf)
add(x,root->left);
else
if (x>root->inf)
add(x,root->right);
}
void deleteTree(tree *&root)
{ if (root)
{deleteTree(root->left);
deleteTree(root->right);
delete root;
root=NULL;}
}
void printList(tree *root)
{if (root) //если узел не пустой
{ /* и если у узла отсутствуют левое и правое поддеревья, то узел является листом и мы его распечатываем*/
if (root->left==NULL && root->right==NULL) out<<root->inf<<"\t";
else {printList(root->left); printList(root->right);} //иначе выполняем обход узла
}
}
int main()
{
int x;
while (!in.eof())
{
in>>x;
add(x,root);
}
printList(root);
deleteTree(root);
in.close();
}
_____________________________input.txt_________________________________
10 7 25 31 18 6 3 12 22 8
_____________________________output.txt________________________________
3 8 12 22 31
Замечание. Во входном файле были приведены данные, соответствующие примеру 3.
2. В файле input.txt в первой строке записано N, во второй строке – последовательность из N целых чисел. Построить по этой последовательности идеально сбалансированное дерево и вывести в файл output.txt высоту этого дерева.
_____________________________prim2.cpp_______________________________
#include <fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
struct tree
{
int inf;
tree *left, *right;
};
tree *root;
void deleteTree(tree *&root)
{ if (root) // если узел дерева не пуст, то
{deleteTree(root->left); // обходим левое и
deleteTree(root->right); // правое поддеревья этого узла
delete root; // после чего удаляем сам узел
root=NULL;}
}
void create (int number, tree *&root)
{int a;
if (number>0)
{
root=new tree;
in>>a;
root->inf=a;
root->left=root->right=NULL;
int numberLeft=number/2, numberRight=number-numberLeft-1;
create(numberLeft, root->left);
create(numberRight, root->right); }
}
void heightTree(tree *root, int &heightNode, int &height)
{if (root) // если текущий узел не пустой
{if (heightNode>height) // и высота текущего узла больше высоты дерева, то
height=heightNode; // полагаем в качестве высоты дерева высоту текущего узла
heightNode++; // в любом случае увеличиваем высоту текущего узла на 1 и
heightTree(root->left, heightNode, height); // обходим левое и правое его поддеревья
heightTree(root->right, heightNode, height);
heightNode--; // после обхода узла высоту текущего узла уменьшаем на 1
}
/* если попали в пустой узел, то завершаем рекурсию и высоту узла уменьшаем на 1 */
else heightNode--;
}
void printList(tree *root)
{if (root) //если узел не пустой
{ /* и если у узла отсутствуют левое и правое поддеревья, то узел является листом и мы его распечатываем*/
if (root->left==NULL && root->right==NULL) out<<root->inf<<"\t";
else {printList(root->left); printList(root->right);} //иначе выполняем обход узла
}
}
int main()
{int n;
in>>n;
create(n,root);
int currentHeight=0,resultHeight=0; //инициализируем данные, необходимые для работы подпрограммы
heightTree(root,currentHeight,resultHeight); // вызываем функцию, подсчитывающую высоту дерева
out<<resultHeight<<endl; // выводим высоту дерева в выходной файл
deleteTree(root);
in.close();
}
_____________________________input.txt_________________________________
10 7 25 31 18 6 3 12 22 8
_____________________________output.txt________________________________
Замечание. Во входном файле были приведены данные, соответствующие примеру 7.
3. В файле input.txt хранится последовательность целых чисел. Построить по этой последовательности дерево двоичного поиска и вывести в файл output.txt путь из вершины a в вершину b этого дерева (если путь не существует, то вывести сообщение об этом).
_____________________________prim3.cpp_______________________________
#include <fstream>
#include <queue>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
struct tree
{
int inf;
tree *left, *right;
};
tree *root;
void add (int x, tree *&root)
{if (!root)
{
root=new tree;
root->inf=x;
root->left=root->right=NULL;
}
else if (x<root->inf)
add(x,root->left);
else
if (x>root->inf)
add(x,root->right);
}
void deleteTree(tree *&root)
{ if (root)
{deleteTree(root->left);
deleteTree(root->right);
delete root;
root=NULL;}
}
// Функция возвращает указатель на узел в дереве root, имеющий значение value
tree * searchNode (tree *root, int value)
{
if (!root) // если узел пустой, то узел со значением value в дереве не встречается
return NULL; // и мы возвращаем пустой указатель,
else
if (value<root->inf) // иначе если значение value меньше значения узла,
searchNode(root->left,value); // то спускаемся по левому поддереву,
else
if (value>root->inf) // иначе если значение value больше значения узла,
searchNode(root->right, value); // то спускаемся по правому поддереву,
// иначе заданный узел найден, и мы возвращаем указатель на него
else
return root;
}
/* Рекурсивная функция, определяющая путь от заданного узла до узла со значением value. Формальные параметры: currentNode – указатель на заданный узел дерева; value – значение узла, путь до которого нужно найти; q- очередь, в которую будет записываться путь. */
void way(tree *currentNode, int value, queue<int> &q)
{
if (!currentNode) // если узел пустой, то узел со значением value в дереве не встречается
while (!q.empty())
{
q.pop();
}
// и мы удаляем последовательность узлов пути из очереди,
else
{
q.push(currentNode->inf); // иначе помещаем текущий узел в очередь
if (value<currentNode->inf) // и если значение value меньше значения узла,
way(currentNode->left, value, q); // то спускаемся по левому поддереву,
else
if (value>currentNode->inf) // иначе если значение value больше значения узла,
way(currentNode->right, value, q); // то спускаемся по правому поддереву,
// иначе значение узла равно value и мы завершаем рекурсию
}
}
int main()
{
int x,firstValue,secondValue;
in>>firstValue;
in>>secondValue;
while (!in.eof())
{
in>>x;
add(x,root);
}
queue <int>q;
tree *firstNode=searchNode(root, firstValue);
tree *secondNode=searchNode(root, secondValue);
if (!firstNode) // если указатель пустой, то узел со значением а в дереве нет
out<<"вершина со значением" << firstValue<<" в дереве отсутствует";
else if (!secondNode) // если указатель пустой, то узел со значением b в дереве нет
out<<"вершина со значением" << secondValue<<" в дереве отсутствует";
else { /* в противном случае вызываем функцию, записывающую путь от узла rА до узла со значение b в очередь */
way(firstNode,secondValue,q);
/* если очередь не пуста, то мы нашли путь от узла со значением а
до узла со значением b и выводим его из очереди, в противном
случае путь отсутствует */
if (!q.empty())
while (!q.empty())
{
x=q.front();
q.pop();
out<<x<<"\t";
}
else out<< "путь отсутствует";
}
deleteTree(root);
in.close();
}
_____________________________input.txt________________________________
7 3
10 7 25 31 18 6 3 12 22 8
_______output.txt____________
7 6 3
_____________________________input.txt________________________________
7 31
10 7 25 31 18 6 3 12 22 8
_______output.txt____________
путь отсутствует
Замечание. Во входном файле были приведены данные, соответствующие примеру 3.
Никифорак М.В.
СЕРЕДНЬОВІЧНА ДЕРЖАВА І ПРАВО ФРАНЦІЇ
Методичні матеріали до семінарського заняття
з історії держави і права зарубіжних країн
Чернівці
“Рута”
УДК: 34 (4/9)(09)(073)
ББК: 67.2(4/8)я7
Н-627
Друкується за ухвалою редакційно-видавничої ради Чернівецького національного університету імені Юрія Федьковича
Рецензенти: Меленко С.Г., кандидат юридичних наук, доцент
Савчук С.В., кандидат юридичних наук, доцент
Відповідальний за випуск: Меленко С.Г., кандидат юридичних наук, доцент
Дата добавления: 2014-12-20; просмотров: 96 | Поможем написать вашу работу | Нарушение авторских прав |