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

Groups > pl.comp.programming > #28542

Re: Szukanie najdłuższego ciągu w drzewie

Show all headers | View raw

W dniu 07.05.2016 o 11:44, Borneq pisze:
> Może redukować drzewo?
> http://i.imgur.com/sRfoI9o.png

Przykład nierekurencyjnego ze stosem znalezienia najlepszej/najdłuższej 
ściężki. Tylko że ten stos będzie zbytnio rósł?
#include "stdafx.h"
#include <stack>
#include "exception.h"
#include "Node.h"

//http://i.imgur.com/7XGaVEL.png
void makeSample0()
{
	CNode* node0 = CNode::AddRoot("0");
	CNode* node1 = node0->Add("1");
	CNode* node2 = node0->Add("2");
	CNode* node3 = node0->Add("3");
	node1->Add("4");
	node1->Add("5");
	CNode* node6 = node2->Add("6");
	node3->Add("7");
	CNode* node8 = node3->Add("8");
	CNode* node9 = node6->Add("9");
	node8->Add("12");
	CNode* node10 = node9->Add("10");
	node9->Add("11");
	node10->Add("13");
	CNode* node14 = node10->Add("14");
	node14->Add("15");
}


//Traverse tree depth-first search, pre-order, stack instead of recursion
void TreverseTree(CNode *startNode)
{
	if (startNode == NULL) throw new Exception("root == NULL");
	stack<int> treeStack;
	CNode *node = startNode;
	int nr = 0;
	while (true)
	{
		if (node->height!=0)
			throw new Exception("error");
		node->height = treeStack.size();
		cout << node->label.c_str() << " " << node->height << endl;
		while (nr >= node->childs.size())
		{
			if (treeStack.size() == 0) return;
			nr = treeStack.top();
			treeStack.pop();
			node = node->parent;
			nr++;
		}
		treeStack.push(nr);
		node = node->childs[nr];
		nr = 0;
	}
}

int main()
{
	makeSample0();
	TreverseTree(CNode::root);
     return 0;
}


--------------------------------
Node.h:
#pragma once
#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

class CNode
{
public:
	CNode();
	~CNode();
	static CNode* AddRoot(string label);
	CNode* Add(string label);
	int height;
	CNode* parent;
	vector<CNode*> childs;
	static CNode* root;
	string label;
};


--------------------------------
Node.cpp:
#include "Node.h"

CNode* CNode::root = NULL;

CNode::CNode()
{
	height = 0;
}


CNode::~CNode()
{
}

CNode* CNode::AddRoot(string label)
{
	root = new CNode();
	root->label = label;
	root->parent = NULL;
	root->height = 0;
	return root;
}

CNode * CNode::Add(string label)
{
	CNode *elem = new CNode();
	elem->label = label;
	elem->parent = this;
	childs.push_back(elem);
	return elem;
}

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 07:59 +0200
  Re: Szukanie najdłuższego ciągu w drzewie "M.M." <mmarszik@gmail.com> - 2016-05-06 23:34 -0700
    Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 11:24 +0200
      Re: Szukanie najdłuższego ciągu w drzewie "M.M." <mmarszik@gmail.com> - 2016-05-07 04:32 -0700
        Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 14:36 +0200
    Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 11:27 +0200
      Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 11:44 +0200
        Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 13:13 +0200
        Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 13:15 +0200
      Re: Szukanie najdłuższego ciągu w drzewie bartekltg <bartekltg@gmail.com> - 2016-05-08 07:15 -0700

csiph-web