Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #31486 > unrolled thread

Jak usunąć najlepiej element z drzewa ?

Started byBorneq <borneq@antyspam.hidden.pl>
First post2018-03-15 01:57 +0100
Last post2018-03-15 13:48 +0100
Articles 17 — 3 participants

Back to article view | Back to pl.comp.programming

Contents

  Jak usunąć najlepiej element z drzewa ? Borneq <borneq@antyspam.hidden.pl> - 2018-03-15 01:57 +0100
    Re: Jak usunąć najlepiej element z drzewa ? Tomasz Kaczanowski <kaczus@poczta.onet.pl> - 2018-03-15 08:10 +0100
      Re: Jak usunąć najlepiej element z drzewa ? Borneq <borneq@antyspam.hidden.pl> - 2018-03-15 11:35 +0100
        Re: Jak usunąć najlepiej element z drzewa ? Tomasz Kaczanowski <kaczus@poczta.onet.pl> - 2018-03-15 12:30 +0100
          Re: Jak usunąć najlepiej element z drzewa ? Borneq <borneq@antyspam.hidden.pl> - 2018-03-15 14:17 +0100
            Re: Jak usunąć najlepiej element z drzewa ? Tomasz Kaczanowski <kaczus@poczta.onet.pl> - 2018-03-15 14:24 +0100
              Re: Jak usunąć najlepiej element z drzewa ? Borneq <borneq@antyspam.hidden.pl> - 2018-03-15 14:54 +0100
                Re: Jak usunąć najlepiej element z drzewa ? "M.M." <mmarszik@gmail.com> - 2018-03-15 10:43 -0700
                  Re: Jak usunąć najlepiej element z drzewa ? Borneq <borneq@antyspam.hidden.pl> - 2018-03-15 19:31 +0100
                    Re: Jak usunąć najlepiej element z drzewa ? "M.M." <mmarszik@gmail.com> - 2018-03-15 14:15 -0700
                      Re: Jak usunąć najlepiej element z drzewa ? Borneq <borneq@antyspam.hidden.pl> - 2018-03-15 22:41 +0100
                        Re: Jak usunąć najlepiej element z drzewa ? "M.M." <mmarszik@gmail.com> - 2018-03-15 15:00 -0700
                          Re: Jak usunąć najlepiej element z drzewa ? Borneq <borneq@antyspam.hidden.pl> - 2018-03-15 23:46 +0100
                            Re: Jak usunąć najlepiej element z drzewa ? Borneq <borneq@antyspam.hidden.pl> - 2018-03-16 00:07 +0100
                            Re: Jak usunąć najlepiej element z drzewa ? "M.M." <mmarszik@gmail.com> - 2018-03-16 06:26 -0700
    Re: Jak usunąć najlepiej element z drzewa ? "M.M." <mmarszik@gmail.com> - 2018-03-15 05:34 -0700
      Re: Jak usunąć najlepiej element z drzewa ? Tomasz Kaczanowski <kaczus@poczta.onet.pl> - 2018-03-15 13:48 +0100

#31486 — Jak usunąć najlepiej element z drzewa ?

FromBorneq <borneq@antyspam.hidden.pl>
Date2018-03-15 01:57 +0100
SubjectJak usunąć najlepiej element z drzewa ?
Message-ID<p8cgcv$bd7$1@node1.news.atman.pl>
podczas gdy nie można wołać a.remove() a co najwyżej usuwać dzieci tego 
węzła.

kod:
#include <memory>
#include <string>
#include <vector>
#include <assert.h>

using namespace std;

class Node
{
	vector<shared_ptr<Node>> childs;
	Node* parent = nullptr;//not shared_ptr! because of memory leaks of 
circular dependency
	int level = 0;
public:
	string name;
	Node(string name)
	{
		this->name = name;
	}
	~Node()
	{
		printf("delete %s\n",name.c_str());
	}
	shared_ptr<Node> clone()
	{
		shared_ptr<Node> result = make_shared<Node>(name+"a");
		return result;
	}
	void erase()
	{
		printf("erase from %s\n", name.c_str());
		childs.clear();
	}
	void Add(shared_ptr<Node> node)
	{
		shared_ptr<Node> clone = node->clone();
		childs.push_back(clone);
		clone->parent = this;
		clone->level = level+1;
		for (size_t i = 0; i<node->childs.size(); i++)
			clone->Add(node->childs[i]);
	}
	shared_ptr<Node>& at(int index)
	{
		return childs[index];
	}
	void print()
	{
		for (int i = 0; i<level; i++)
			printf("  ");
		printf("%s->",name.c_str());
		if (parent) printf("%s", parent->name.c_str());
		printf("\n");
		for (size_t i=0; i<childs.size(); i++)
			childs[i]->print();
	}
};

int main()
{
	shared_ptr<Node>root,rootB;
	root = make_shared<Node>("1");
	root->Add(make_shared<Node>("2"));
	root->Add(make_shared<Node>("3"));
	root->at(0)->Add(make_shared<Node>("4"));
	root->at(0)->Add(make_shared<Node>("5"));
	root->at(1)->Add(make_shared<Node>("6"));
	root->at(1)->Add(make_shared<Node>("7"));

	rootB = make_shared<Node>("1b");
	rootB->Add(make_shared<Node>("2b"));
	rootB->Add(make_shared<Node>("3b"));
	rootB->at(0)->Add(make_shared<Node>("4b"));
	rootB->at(0)->Add(make_shared<Node>("5b"));
	rootB->at(1)->Add(make_shared<Node>("6b"));
	rootB->at(1)->Add(make_shared<Node>("7b"));
//	node->Add(root);
	//root->print();printf("\n");
	//rootB->print(); printf("\n");
	root->at(0)->Add(rootB);
	rootB = nullptr;
	//rootB->at(0)->Add(rootB);//tu cykl?
	root->print();
	root->at(0)->erase();
	root->print();
     return 0;
}

[toc] | [next] | [standalone]

#31487

FromTomasz Kaczanowski <kaczus@poczta.onet.pl>
Date2018-03-15 08:10 +0100
Message-ID<p8d69b$p3b$1@node2.news.atman.pl>
In reply to#31486
W dniu 2018-03-15 o 01:57, Borneq pisze:
> podczas gdy nie można wołać a.remove() a co najwyżej usuwać dzieci tego 
> węzła.

Przecież sa sobie odpowiadasz "Usunąć element z drzewa", a nie usunąć 
samego siebie. Można to na kilka sposobów, w roocie dać root.remove(a), 
albo root.remove(indeks) (bo widzę, indeksami jakimiś tez się 
posługujesz). Które, czy oba, zależy od zastosowań.

-- 
http://kaczus.ppa.pl

[toc] | [prev] | [next] | [standalone]

#31488

FromBorneq <borneq@antyspam.hidden.pl>
Date2018-03-15 11:35 +0100
Message-ID<p8dia4$4c4$1@node2.news.atman.pl>
In reply to#31487
W dniu 15.03.2018 o 08:10, Tomasz Kaczanowski pisze:
> Przecież sa sobie odpowiadasz "Usunąć element z drzewa", a nie usunąć 
> samego siebie. Można to na kilka sposobów, w roocie dać root.remove(a), 
> albo root.remove(indeks) (bo widzę, indeksami jakimiś tez się 
> posługujesz). Które, czy oba, zależy od zastosowań.
> 

root.remove(a) nie, bo a może nie być bezpośrednim dzieckiem roota.
Jak chcę wołać 'a muszę zrobić a->parent.remove(a).
Problem gdy chcę usunąć roota. Myślałem również aby element składał się 
ze stałej części i zmiennej (dla polimorfizmu), stała byłaby nadpisywana 
a zmienna wymieniana - dla podmiany elementu na poddrzewo, ale to 
działałoby tylko dla wymiany a nie usuwania. Choć można zrobić i to i 
to, podmiana by podmieniała część zmienną, usuwanie usuwało by 
a->parent.remove(a) a dla roota tylko ustawiało by część zmienną na nullptr.

[toc] | [prev] | [next] | [standalone]

#31489

FromTomasz Kaczanowski <kaczus@poczta.onet.pl>
Date2018-03-15 12:30 +0100
Message-ID<p8dlhd$eah$1@node1.news.atman.pl>
In reply to#31488
W dniu 2018-03-15 o 11:35, Borneq pisze:
> W dniu 15.03.2018 o 08:10, Tomasz Kaczanowski pisze:
>> Przecież sa sobie odpowiadasz "Usunąć element z drzewa", a nie usunąć 
>> samego siebie. Można to na kilka sposobów, w roocie dać 
>> root.remove(a), albo root.remove(indeks) (bo widzę, indeksami jakimiś 
>> tez się posługujesz). Które, czy oba, zależy od zastosowań.
>>
> 
> root.remove(a) nie, bo a może nie być bezpośrednim dzieckiem roota.
> Jak chcę wołać 'a muszę zrobić a->parent.remove(a).
> Problem gdy chcę usunąć roota. Myślałem również aby element składał się 
> ze stałej części i zmiennej (dla polimorfizmu), stała byłaby nadpisywana 
> a zmienna wymieniana - dla podmiany elementu na poddrzewo, ale to 
> działałoby tylko dla wymiany a nie usuwania. Choć można zrobić i to i 
> to, podmiana by podmieniała część zmienną, usuwanie usuwało by 
> a->parent.remove(a) a dla roota tylko ustawiało by część zmienną na 
> nullptr.

Zrob kontener i w nim odpowiednie metody.

-- 
http://kaczus.ppa.pl

[toc] | [prev] | [next] | [standalone]

#31492

FromBorneq <borneq@antyspam.hidden.pl>
Date2018-03-15 14:17 +0100
Message-ID<p8drp1$d3l$1@node2.news.atman.pl>
In reply to#31489
W dniu 15.03.2018 o 12:30, Tomasz Kaczanowski pisze:
> Zrob kontener i w nim odpowiednie metody.

Kontener w sensie, że na najwyższym poziomie będzie miał roota?

[toc] | [prev] | [next] | [standalone]

#31493

FromTomasz Kaczanowski <kaczus@poczta.onet.pl>
Date2018-03-15 14:24 +0100
Message-ID<p8ds7o$l09$1@node1.news.atman.pl>
In reply to#31492
W dniu 2018-03-15 o 14:17, Borneq pisze:
> W dniu 15.03.2018 o 12:30, Tomasz Kaczanowski pisze:
>> Zrob kontener i w nim odpowiednie metody.
> 
> Kontener w sensie, że na najwyższym poziomie będzie miał roota?
> 
> 
Ze na najwyższym poziomie będzie obiekt zarządzający całością. Taki 
podział na container i nodes. Można dzięki temu uzyskać tez szybszy 
dostęp do obiektów, bo możesz sobie pamiętać roota, ostatni i aktualny, 
co czasami może przyspieszyć wyszukiwanie choćby. Natomiast usuwanie 
roota, to ustawienie jako roota kolejnego elementu itd...

-- 
http://kaczus.ppa.pl

[toc] | [prev] | [next] | [standalone]

#31494

FromBorneq <borneq@antyspam.hidden.pl>
Date2018-03-15 14:54 +0100
Message-ID<p8dtuu$f4c$1@node2.news.atman.pl>
In reply to#31493
W dniu 15.03.2018 o 14:24, Tomasz Kaczanowski pisze:
> W dniu 2018-03-15 o 14:17, Borneq pisze:
>> W dniu 15.03.2018 o 12:30, Tomasz Kaczanowski pisze:
>>> Zrob kontener i w nim odpowiednie metody.
>>
>> Kontener w sensie, że na najwyższym poziomie będzie miał roota?

Robię teraz dziedziczenie:
mam klonowanie:
	shared_ptr<Node> clone()
	{
		shared_ptr<Node> result = make_shared<Node>();
		result->member1 = member1;
		result->member2 = member2;
		return result;
	}

Teraz mam: class Num: Node
mógłbym zrobić:
	shared_ptr<Node> clone()
	{
		shared_ptr<Num> result = make_shared<Num>(parameter);
		result->member1 = member1;
		result->member2 = member2;
		result->member3 = member3;
		return result;
	}

ale powtarza mi się kod z member1 i member2 czy można zrobić jakąś 
fabrykę klas , nawet zrezygnować z parameter i zamiast
		shared_ptr<Num> result = make_shared<Num>();
zrobić konstruktor wirtualny i

shared_ptr<Node> result = make_shared<TypJakoParametr>();
?

[toc] | [prev] | [next] | [standalone]

#31495

From"M.M." <mmarszik@gmail.com>
Date2018-03-15 10:43 -0700
Message-ID<97991863-74a4-4dd9-b540-b93401f9f2a0@googlegroups.com>
In reply to#31494
On Thursday, March 15, 2018 at 2:54:39 PM UTC+1, Borneq wrote:
> W dniu 15.03.2018 o 14:24, Tomasz Kaczanowski pisze:
> > W dniu 2018-03-15 o 14:17, Borneq pisze:
> >> W dniu 15.03.2018 o 12:30, Tomasz Kaczanowski pisze:
> >>> Zrob kontener i w nim odpowiednie metody.
> >>
> >> Kontener w sensie, że na najwyższym poziomie będzie miał roota?
> 
> Robię teraz dziedziczenie:
> mam klonowanie:
> 	shared_ptr<Node> clone()
> 	{
> 		shared_ptr<Node> result = make_shared<Node>();
> 		result->member1 = member1;
> 		result->member2 = member2;
> 		return result;
> 	}
> 
> Teraz mam: class Num: Node
> mógłbym zrobić:
> 	shared_ptr<Node> clone()
> 	{
> 		shared_ptr<Num> result = make_shared<Num>(parameter);
> 		result->member1 = member1;
> 		result->member2 = member2;
> 		result->member3 = member3;
> 		return result;
> 	}
> 
> ale powtarza mi się kod z member1 i member2 czy można zrobić jakąś 
> fabrykę klas , nawet zrezygnować z parameter i zamiast
> 		shared_ptr<Num> result = make_shared<Num>();
> zrobić konstruktor wirtualny i
> 
> shared_ptr<Node> result = make_shared<TypJakoParametr>();
> ?

Jakich cech brakuje Ci w standardowych implementacjach drzew, że
implementujesz po swojemu?

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#31496

FromBorneq <borneq@antyspam.hidden.pl>
Date2018-03-15 19:31 +0100
Message-ID<p8ee5g$6h9$1@node1.news.atman.pl>
In reply to#31495
W dniu 15.03.2018 o 18:43, M.M. pisze:
> Jakich cech brakuje Ci w standardowych implementacjach drzew, że
> implementujesz po swojemu?

Elementy różnych typów, podmiana elementu na podgałąź

[toc] | [prev] | [next] | [standalone]

#31498

From"M.M." <mmarszik@gmail.com>
Date2018-03-15 14:15 -0700
Message-ID<9be05610-85b3-4627-ac5e-1ebc28edf588@googlegroups.com>
In reply to#31496
On Thursday, March 15, 2018 at 7:31:14 PM UTC+1, Borneq wrote:
> W dniu 15.03.2018 o 18:43, M.M. pisze:
> > Jakich cech brakuje Ci w standardowych implementacjach drzew, że
> > implementujesz po swojemu?
> 
> Elementy różnych typów, 
Np. jakich typów?

> podmiana elementu na podgałąź

Potrzebujesz drzewa z wyważaniem czy bez?

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#31499

FromBorneq <borneq@antyspam.hidden.pl>
Date2018-03-15 22:41 +0100
Message-ID<p8epa1$hic$1@node1.news.atman.pl>
In reply to#31498
W dniu 15.03.2018 o 22:15, M.M. pisze:
> Np. jakich typów?
> 
>> podmiana elementu na podgałąź
> 
> Potrzebujesz drzewa z wyważaniem czy bez?

To zupełnie co innego niż AVL, drzewa czerwono-czarne,itp.
Drzewa bez wyważania, coś takiego jak AST do trzymania wyrażeń 
arytmetycznych, zwykle Lisp czy Closure się do tego nadaje.
Na przykład teraz zobaczyłem że źle zrobiłem klonowanie: teraz jak 
podczepiam poddrzewko to wchodzi wgłąb niego i klonuje w razie potrzeby. 
Może być zapętlenie gdy do drzewa w pewnym miejscu podczepiam całe 
drzewo. Radzę sobie przez ustawienie znacznika, i w ten sposób przerywam 
z błędem. Ale nie chcę przerywać z błędem tylko nie klonować w razie 
potrzeby po jednym, tylko najpierw sklonować całe drzewko (obiekty 
różnych typów,kopiowanie danych ale linki dzieci-ojciec odpowiednio się 
zmienią na nowe obiekty) a potem je podczepić.

[toc] | [prev] | [next] | [standalone]

#31500

From"M.M." <mmarszik@gmail.com>
Date2018-03-15 15:00 -0700
Message-ID<14fb90d6-a809-4343-bf08-c7798fb725c5@googlegroups.com>
In reply to#31499
On Thursday, March 15, 2018 at 10:41:22 PM UTC+1, Borneq wrote:
> W dniu 15.03.2018 o 22:15, M.M. pisze:
> > Np. jakich typów?
> > 
> >> podmiana elementu na podgałąź
> > 
> > Potrzebujesz drzewa z wyważaniem czy bez?
> 
> To zupełnie co innego niż AVL, drzewa czerwono-czarne,itp.
> Drzewa bez wyważania, coś takiego jak AST do trzymania wyrażeń 
> arytmetycznych, zwykle Lisp czy Closure się do tego nadaje.
> Na przykład teraz zobaczyłem że źle zrobiłem klonowanie: teraz jak 
> podczepiam poddrzewko to wchodzi wgłąb niego i klonuje w razie potrzeby. 
> Może być zapętlenie gdy do drzewa w pewnym miejscu podczepiam całe 
> drzewo. Radzę sobie przez ustawienie znacznika, i w ten sposób przerywam 
> z błędem. Ale nie chcę przerywać z błędem tylko nie klonować w razie 
> potrzeby po jednym, tylko najpierw sklonować całe drzewko (obiekty 
> różnych typów,kopiowanie danych ale linki dzieci-ojciec odpowiednio się 
> zmienią na nowe obiekty) a potem je podczepić.

Jest to na tyle łatwe, że można szybko samemu zrobić. Moja implementacja 
drzewek czerwono czarnych trochę czasu mi zajęła, ale ma kilka dodatkowych
bajerów, no i samo wyważanie wymaga trochę wysiłku.

Wracając do pierwszego pytania, jak usuwać węzeł. Usuwa się po prostu,
przez zwolnienie pamięci. Ale jeśli węzeł ma dzieci, to nie można ich
zgubić. Co zrobić z dziećmi? Zależy od zastosowania.

Hmmm a po co usuwasz węzeł w drzewie do reprezentacji wyrażeń 
arytmetycznych?

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#31502

FromBorneq <borneq@antyspam.hidden.pl>
Date2018-03-15 23:46 +0100
Message-ID<p8et3h$la0$1@node1.news.atman.pl>
In reply to#31500
W dniu 15.03.2018 o 23:00, M.M. pisze:
> Hmmm a po co usuwasz węzeł w drzewie do reprezentacji wyrażeń
> arytmetycznych?

Po to by zastąpić zmienną całym wyrażeniem.
Coś takiego:
ma symbolicznie robić operację postawiania:
na przykład gdy liczymy pierwiastek z n to ze wzoru (wybierając x 
początkowe)
x:= (x+n/x)/2
druga iteracja, podstawiamy wszędzie gdzie x całe wyrażenie:
otrzymujemy ((x+n/x)/2+n/((x+n/x)/2))/2
możemy dalej
(((x+n/x)/2+n/((x+n/x)/2))/2+n/(((x+n/x)/2+n/((x+n/x)/2))/2))/2

Działa już klonowanie (można podczepić całe drzewko do swojej podgałęzi, 
jeszcze nie mam tu replace- jest innej wersji , gdzie nie działało 
klonowanie), trzeba dorobić dziedziczenie:
#include <memory>
#include <string>
#include <vector>
#include <assert.h>

using namespace std;

class Node
{
	vector<shared_ptr<Node>> childs;
	Node* parent = nullptr;//not shared_ptr! because of memory leaks of 
circular dependency
	int level = 0;
public:
	string name;
	Node(string name)
	{
		this->name = name;
	}
	~Node()
	{
		printf("delete %s\n",name.c_str());
	}
	shared_ptr<Node> cloneOne()
	{
		shared_ptr<Node> result = make_shared<Node>(name+"a");
		return result;
	}

	shared_ptr<Node> cloneTree()
	{
		shared_ptr<Node> newElem = cloneOne();
		for (size_t i = 0; i<childs.size(); i++)
		{
			shared_ptr<Node> subElem = childs[i]->cloneTree();
			newElem->AddOneChild(subElem);
		}
		return newElem;
	}

	void erase()
	{
		printf("erase from %s\n", name.c_str());
		childs.clear();
	}
	void deleteChild(int index)
	{
		printf("delete child %d from %s - %s\n", index, name.c_str(), 
childs[index]->name.c_str());
		childs.erase(childs.begin()+index);
	}

	void setLevel(int level)
	{
		this->level = level;
		for (size_t i = 0; i<childs.size(); i++)
			childs[i]->setLevel(level+1);
	}

	void AddOneChild(shared_ptr<Node> node)
	{
		childs.push_back(node);
		node->parent = this;
	}

	void AddTree(shared_ptr<Node> node)
	{
		shared_ptr<Node> clone = node->cloneTree();
		AddOneChild(clone);
		clone->setLevel(level+1);
	}
	shared_ptr<Node>& at(int index)
	{
		return childs[index];
	}
	void print()
	{
		for (int i = 0; i<level; i++)
			printf("  ");
		printf("%s->",name.c_str());
		if (parent) printf("%s", parent->name.c_str());
		printf("\n");
		for (size_t i=0; i<childs.size(); i++)
			childs[i]->print();
	}
};

int main()
{
	shared_ptr<Node>root,rootB;
	root = make_shared<Node>("1");
	root->AddTree(make_shared<Node>("2"));
	root->AddTree(make_shared<Node>("3"));
	root->at(0)->AddTree(make_shared<Node>("4"));
	root->at(0)->AddTree(make_shared<Node>("5"));
	root->at(1)->AddTree(make_shared<Node>("6"));
	root->at(1)->AddTree(make_shared<Node>("7"));
	root->at(1)->AddTree(root);
	root->print();
	return 0;
}

[toc] | [prev] | [next] | [standalone]

#31503

FromBorneq <borneq@antyspam.hidden.pl>
Date2018-03-16 00:07 +0100
Message-ID<p8eubi$mal$1@node1.news.atman.pl>
In reply to#31502
Replace:
nie można najpierw usuwać a potem dodawać , bo w międzyczasie zmieniłoby 
się drzewo. Trzeba sklonować, potem usunąć i wstawić.
         void InsertOneChild(int index, shared_ptr<Node> node)
	{
		childs.insert(childs.begin() + index, node);
		node->parent = this;
	}

         void ReplaceChild(int index, shared_ptr<Node> subtree)
	{
		shared_ptr<Node> clone = subtree->cloneTree();
		deleteChild(index);
		InsertOneChild(index, clone);
		clone->setLevel(level + 1);
	}


int main()
{
	shared_ptr<Node>root,rootB;
	root = make_shared<Node>("1");
	root->AddTree(make_shared<Node>("2"));
	root->AddTree(make_shared<Node>("3"));
	root->at(0)->AddTree(make_shared<Node>("4"));
	root->at(0)->AddTree(make_shared<Node>("5"));
	root->at(1)->AddTree(make_shared<Node>("6"));
	root->at(1)->AddTree(make_shared<Node>("7"));
	root->print();
	root->ReplaceChild(0,root);
	root->print();
     return 0;
}

[toc] | [prev] | [next] | [standalone]

#31506

From"M.M." <mmarszik@gmail.com>
Date2018-03-16 06:26 -0700
Message-ID<ba0c5575-c254-4cbd-b5a0-edea80c880a8@googlegroups.com>
In reply to#31502
On Thursday, March 15, 2018 at 11:46:10 PM UTC+1, Borneq wrote:
> W dniu 15.03.2018 o 23:00, M.M. pisze:
> > Hmmm a po co usuwasz węzeł w drzewie do reprezentacji wyrażeń
> > arytmetycznych?
> 
> Po to by zastąpić zmienną całym wyrażeniem.

Zastanów się, czy na stosie tego nie można zrobić. Bo jeśli się da, to
zaoszczędzisz sobie mnóstwa pracy. Rozumiesz... notacja polska, albo
jeszcze lepiej odwrotna notacja polska pana Łukasiewicza, ze stosu 
zdejmujesz operandy, potem operator, wykonujesz operację i wyniki 
wrzucasz znowu na stos i tak w kółko aż na stosie zostanie wynik.

Pozdrawiam


> Coś takiego:
> ma symbolicznie robić operację postawiania:
> na przykład gdy liczymy pierwiastek z n to ze wzoru (wybierając x 
> początkowe)
> x:= (x+n/x)/2
> druga iteracja, podstawiamy wszędzie gdzie x całe wyrażenie:
> otrzymujemy ((x+n/x)/2+n/((x+n/x)/2))/2
> możemy dalej
> (((x+n/x)/2+n/((x+n/x)/2))/2+n/(((x+n/x)/2+n/((x+n/x)/2))/2))/2
> 
> Działa już klonowanie (można podczepić całe drzewko do swojej podgałęzi, 
> jeszcze nie mam tu replace- jest innej wersji , gdzie nie działało 
> klonowanie), trzeba dorobić dziedziczenie:
> #include <memory>
> #include <string>
> #include <vector>
> #include <assert.h>
> 
> using namespace std;
> 
> class Node
> {
> 	vector<shared_ptr<Node>> childs;
> 	Node* parent = nullptr;//not shared_ptr! because of memory leaks of 
> circular dependency
> 	int level = 0;
> public:
> 	string name;
> 	Node(string name)
> 	{
> 		this->name = name;
> 	}
> 	~Node()
> 	{
> 		printf("delete %s\n",name.c_str());
> 	}
> 	shared_ptr<Node> cloneOne()
> 	{
> 		shared_ptr<Node> result = make_shared<Node>(name+"a");
> 		return result;
> 	}
> 
> 	shared_ptr<Node> cloneTree()
> 	{
> 		shared_ptr<Node> newElem = cloneOne();
> 		for (size_t i = 0; i<childs.size(); i++)
> 		{
> 			shared_ptr<Node> subElem = childs[i]->cloneTree();
> 			newElem->AddOneChild(subElem);
> 		}
> 		return newElem;
> 	}
> 
> 	void erase()
> 	{
> 		printf("erase from %s\n", name.c_str());
> 		childs.clear();
> 	}
> 	void deleteChild(int index)
> 	{
> 		printf("delete child %d from %s - %s\n", index, name.c_str(), 
> childs[index]->name.c_str());
> 		childs.erase(childs.begin()+index);
> 	}
> 
> 	void setLevel(int level)
> 	{
> 		this->level = level;
> 		for (size_t i = 0; i<childs.size(); i++)
> 			childs[i]->setLevel(level+1);
> 	}
> 
> 	void AddOneChild(shared_ptr<Node> node)
> 	{
> 		childs.push_back(node);
> 		node->parent = this;
> 	}
> 
> 	void AddTree(shared_ptr<Node> node)
> 	{
> 		shared_ptr<Node> clone = node->cloneTree();
> 		AddOneChild(clone);
> 		clone->setLevel(level+1);
> 	}
> 	shared_ptr<Node>& at(int index)
> 	{
> 		return childs[index];
> 	}
> 	void print()
> 	{
> 		for (int i = 0; i<level; i++)
> 			printf("  ");
> 		printf("%s->",name.c_str());
> 		if (parent) printf("%s", parent->name.c_str());
> 		printf("\n");
> 		for (size_t i=0; i<childs.size(); i++)
> 			childs[i]->print();
> 	}
> };
> 
> int main()
> {
> 	shared_ptr<Node>root,rootB;
> 	root = make_shared<Node>("1");
> 	root->AddTree(make_shared<Node>("2"));
> 	root->AddTree(make_shared<Node>("3"));
> 	root->at(0)->AddTree(make_shared<Node>("4"));
> 	root->at(0)->AddTree(make_shared<Node>("5"));
> 	root->at(1)->AddTree(make_shared<Node>("6"));
> 	root->at(1)->AddTree(make_shared<Node>("7"));
> 	root->at(1)->AddTree(root);
> 	root->print();
> 	return 0;
> }

[toc] | [prev] | [next] | [standalone]

#31490

From"M.M." <mmarszik@gmail.com>
Date2018-03-15 05:34 -0700
Message-ID<aec79fbe-24e2-42c6-8935-0d1b620eb88c@googlegroups.com>
In reply to#31486
On Thursday, March 15, 2018 at 1:57:04 AM UTC+1, Borneq wrote:
> podczas gdy nie można wołać a.remove() a co najwyżej usuwać dzieci tego 
> węzła.

Dlaczego nie można?

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#31491

FromTomasz Kaczanowski <kaczus@poczta.onet.pl>
Date2018-03-15 13:48 +0100
Message-ID<p8dq4c$iq8$1@node1.news.atman.pl>
In reply to#31490
W dniu 2018-03-15 o 13:34, M.M. pisze:
> On Thursday, March 15, 2018 at 1:57:04 AM UTC+1, Borneq wrote:
>> podczas gdy nie można wołać a.remove() a co najwyżej usuwać dzieci tego
>> węzła.
> 
> Dlaczego nie można?

bo pewnie wewnątrz metody musialby delete this wykonać...

-- 
http://kaczus.ppa.pl

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web