К сожалению моя прога не прошла тесты, но в чем именно ошибки естественно не показывает)) У меня такое подозрение, что глючит прогу именно на удалении узла... Так что, помогите, кто может и кому не лень потратить время на бедную студентку) Подскажите, есть ли вооще в моей функции ошибка и если есть, тогде)
а вот то, что здесь используется...если надо)
Зарание спасиьбо)
p.s. Забыла как делать код в окнах с вертикальным скролам, может напомните?)))
р.р.s А еще, если не сложно, можете придумать какие-нибудь тесты посложнее, а то я не могу вылавить ошибки, потому что все мои тетсты прога проходит...а в системе нет...
задание:
Найти такой путь максимальной длины между вершинами дерева, у которого сумма ключей конечных вершин минимальна. Удалить (правым удалением) корневую вершину этого пути.
Код:
void Del(int key)
{
Element* E= Find(key);//ищим, есть ли такой элемент
if(E==NULL)
return;
else
{
if(E->left==NULL&&E->right==NULL)//если нет сыновей узла(лист), просто его отрезаем
{
if(E!=root)//если это не корень
{
if(E==E->p->left)//если это левый сын
E->p->left=NULL;//то у предка зануляем ссылку на левого сына
else
E->p->right=NULL;//иначе на правого
}
else root=NULL;//если это был корень,то тазуляем его
}
if(E->left==NULL&&E->right!=NULL)//если у удаляемого узла есть правй сын, но нет левого
{
if(E!=root)//если это не корень
{
E->p->right=E->right;// правым сыном у предка делаем правого сына //удаляемого узла...т.е. как бы вырезаем его просто..
}
else//если это был корень
{
root=E->right;// вместо корня ставим его правого сына
}
}
if(E->left!=NULL&&E->right==NULL)// если есть только левый
{
if(E!=root)//если не корень
E->p->left=E->left;// вырезаем его
else // если корень
{
root=E->left;//делаем корнем его единственног сына
}
}
if(E->left!=NULL&&E->right!=NULL)// если есть и правый и левый сын
{
Element* E1= new Element();//создаем новый элемент
E1=E->right;// спускаемся на 1 узел вправо
while(E1->left!=NULL)// а потом до конца в лево...ну так походу по алгоритму //правого удаления
E1=E1->left;
int i=E1->key;//берем ключ у найденой вершины
Del(i);//удаляем ее
E->key=i;// у у той, которую надо удалить, заменяем ключ...ну это место того, //чтобы на ее место поставить найденую)
}
}
}а вот то, что здесь используется...если надо)
Код:
struct Element
{
int key;// ключ узла
int depth;//глубина узла
Element *p;//предок
Element *left;//левый сын
Element *right;// правый сын
Element(int k)
{
key=k;
depth=-1;
left= right=p=NULL;
}
Element()
{
key=0;
depth=-1;
left= right=p=NULL;
}
};
Element* Find(int k)
{
Element *x=root;
while (x!=NULL)
{
if(x->key==k)
return x;
else
{
if(x->key>k)
x=x->left;
if(x->key<k)
x=x->right;
}
}
return x;
}Зарание спасиьбо)
p.s. Забыла как делать код в окнах с вертикальным скролам, может напомните?)))
р.р.s А еще, если не сложно, можете придумать какие-нибудь тесты посложнее, а то я не могу вылавить ошибки, потому что все мои тетсты прога проходит...а в системе нет...
задание:
Найти такой путь максимальной длины между вершинами дерева, у которого сумма ключей конечных вершин минимальна. Удалить (правым удалением) корневую вершину этого пути.