• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

poprzednik i następnik-drzewa BST

VPS Starter Arubacloud
0 głosów
737 wizyt
pytanie zadane 23 maja 2018 w C i C++ przez szalonydywan Nowicjusz (140 p.)
edycja 26 maja 2018 przez szalonydywan

Witam.

Mam za zadanie napisać funkcję 'Delete' która usunie następnik węzła x jeżeli spełniony jest warunek 'war', w przeciwnym wypadku usuwa poprzednik węzła x. Z pomocą napisałem funkcję wyszukującą następnik i poprzednik, mam też funkcję usuwającą poprzednik ale nie wiem dalej jak to zaimplementwać z tym warunkiem 'war'.

struct node
{
    node *left, *right, *up;
    int val;
}*root = NULL;
 
node *poprzednik(node *T)
{
    if (!T)
        cout << "BRAK ELEMENTU"<<endl;
    if (T->left)
        return max(T->left);
    node *p = T->parent;
    while ((p) && (T == p->left))
    {
        T = p;
        p = p->parent;
    }
    return p;
}
 
node *nastepnik(node *T)
{
    if (!T)
        cout << "BRAK ELEMENTU"<<endl;
    if (T->right)
        return min(T->right);
    node* p = T->parent;
    while ((p) && (T = p->right))
    {
        T = p;
        p = p->parent;
    }
    return p;
}
 
void delete(node*&root, int k) {
    node*usuwacz = nastepnik(w);
    if (usuwacz)
    {
        if ((usuwacz->left) && (usuwacz->right))
        {
            node*pre = poprzednik(usuwacz); 
            usuwacz->val = pre->val;
            if (pre->up->left == pre) 
                pre->up->left = pre->left; 
            else
                pre->up->right = pre->left;
            delete pre;
        }
        else 
        {
            node* poddrzewo = usuwacz->left ? usuwacz->left : usuwacz->right;
 
            if (usuwacz->up) 
            {
                if (usuwacz->up->left == usuwacz) 
                    usuwacz->up->left = poddrzewo; 
                else
                    usuwacz->up->right = poddrzewo;
 
                if (poddrzewo) 
                    poddrzewo->up = usuwacz->up;
            }
            else 
            {
                poddrzewo->up = NULL;
                root = poddrzewo;
            }
            delete usuwacz;
        }
    }
    }

 

komentarz 4 czerwca 2018 przez szalonydywan Nowicjusz (140 p.)

A jeszcze jedno pytanie, takie usuwanie jest dobre?


remove(node* root , node* z){
node* y;
if(z->left∧z->right) y = next(z); 
else y = z;
node* x;
if(y->left) x = y->left; 
else x = y->right;
if(x) x->parent = y->parent; 
if(y->parent) { 
if(y = y->parent ->left)
y->parent ->left = x;
else
y->parent ->right = x;
}
else  root = x; 
if(y!=z) 
z->val = y->val;
delete y;
}

 

komentarz 4 czerwca 2018 przez j23 Mędrzec (194,920 p.)

Linia 1: Wskaźnik root powinien być referencją: node* &root.

Linia 10: w warunku masz =, a powinno być ==

 

Formatuj kod!

komentarz 4 czerwca 2018 przez szalonydywan Nowicjusz (140 p.)
edycja 4 czerwca 2018 przez szalonydywan

Mam tez problem bo w funkcji usunWezel mam za mało argumentów i nie wiem gdzie je dodac

void remove(node* root)
{
	
	
	if (cond(root->val))
		usunWezel(nastepnik(root));
	else usunWezel(poprzednik(root));

 

komentarz 4 czerwca 2018 przez j23 Mędrzec (194,920 p.)

A skąd ja mam wiedzieć, o jakie argumenty chodzi? I jak ma się ta remove z tą poprzednią (z niesformatowanym kodem)?

komentarz 4 czerwca 2018 przez szalonydywan Nowicjusz (140 p.)
#include <iostream>

using namespace std;

struct node
{
	node *left, *right, *parent;
	int val;
}*root = nullptr;

node* push(node* r, int v)
{
	if (r->val == v) return r;
	else if (v > r->val)
	{
		if (r->right == nullptr)
		{
			r->right = new node();
			r->right->val = v;
			r->right->parent = r;
			return r->right;
		}
		else return push(r->right, v);
	}
	else
	{
		if (r->left == nullptr)
		{
			r->left = new node();
			r->left->val = v;
			r->left->parent = r;
			return r->left;
		}
		else return push(r->left, v);
	}
}
node* min(node*root) {
	node*p= root;
	while (p->left) p = p->left;
	return p;
}

node* max(node*root) {
	node*p = root;
	while (p->right) p = p->right;
	return p;
}

 node*poprzednik(node*p) {
	if (!p)
		cout << "Brak elementu";
	if (p->left != NULL) //jezeli jest lewe poddrzewo
		return max(p->left);//najwiekszy na lewo

	node*w = p->parent; //brak lewego poddrzewa
	while ((w) && p == w->left) //cofamy sie do góry
	{
		p = w;
		w = w->parent;
	}
	return w;
}

node*nastepnik(node*p) {
	if (!p)
		cout << "Brak elementu";
	if (p->right)//jezeli jest prawe poddrzewo
		return min(p->right);//najmniejszy na prawo
	node*w = p->parent; // brak prawego poddrzewa
	while ((w) && (p = w->right))//cofamy się do góry
	{
		p = w;
		w = w->parent;
	}
	return w;
	}





void usunWezel(node*&root, node* p) {
	node* y;
	if ((z->left)&&(z->right)) y = nastepnik(p);
	else y = p;
	node* x;
	if (y->left) x = y->left;
	else x = y->right;
	if (x) x->parent = y->parent;
	if (y->parent) {
		if (y = y->parent->left)
			y->parent->left = x;
		else
			y->parent->right = x;
	}
	else  root = x;
	if (y != p)
		p->val = y->val;
	delete y;
}

bool cond(int x)
{
	return (x < 10);
}
void remove(node* root)
{
	
	
	if (cond(root->val))
		usunWezel(nastepnik(root));
	else usunWezel(poprzednik(root));
}





void inorder(node *root)
{
	if (!root)return;
	if (root->left)
		inorder(root->left);
	cout << root->val << " ";
	if (root->right)
		inorder(root->right);
}
int main()
{
	
	
	root = new node();
	root->val = 7;
	push(root,7);
	push(root, 1);
	push(root, 0);
	
	push(root, 3);
	push(root, 2);
	push(root, 5);
	push(root, 4);
	push(root, 6);
	push(root, 9);
	push(root, 8);
	push(root, 11);
	
	inorder(root);
	cout << endl;
	cout << nastepnik(root->right)->val<<endl;
	cout << poprzednik(root->right)->val<<endl;

	remove(root);
	inorder(root);
	delete root;
	system("PAUSE");
	return 0;
}


 

1 odpowiedź

+1 głos
odpowiedź 4 czerwca 2018 przez j23 Mędrzec (194,920 p.)

Zgaduje, że obecny kod usunWezel nie jest twój:

void remove(node* &root)
{
	if (cond(root->val)) 
		usunWezel(root, nastepnik(root));
	else usunWezel(root, poprzednik(root));
}

 

Podobne pytania

0 głosów
1 odpowiedź 266 wizyt
0 głosów
1 odpowiedź 303 wizyt
pytanie zadane 4 lutego 2020 w C i C++ przez Kate1243 Nowicjusz (120 p.)
0 głosów
1 odpowiedź 676 wizyt
pytanie zadane 2 kwietnia 2019 w C i C++ przez Zielony12 Nowicjusz (200 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...