Какие структуры данных для реализации дерева с двухлистным типом?

Question

Какие структуры данных для реализации дерева с двухлистным типом?

Привет, какие структуры данных будут лучше и проще реализовать дерево с двумя листовыми типами, например, лист, который содержит int и лист, который содержит указатель на функцию. Мне это нужно для генетического программирования.

Я делаю это самостоятельно, но боюсь, что это плохая идея.

node.h

#ifndef NODE_H
#define NODE_H

#include <iostream>
#include <stdio.h>

typedef int(* func) (int, int);

using namespace std;

class node
{
private:
node * left, * right, *parent;
int i;
int type; //0 - term, 1 - func

public:
node(node* parent,node* left,node* right, int i, int type);
~node();

void changeLeft(node* left);
void changeRight(node* right);
void changeParent(node* parent);
node* getLeft();
node* getRight();
node* getParent();
int getI();

virtual func getFunction(){return 0;}
virtual int getTerminal(){return 1;}

void show();
};

#endif // NODE_H

tree.h

#ifndef TREE_H
#define TREE_H

#include <vector>
#include <cstdio>
#include <iostream>

#include "node.h"#include "nodefunc.h"#include "nodeterm.h"#include "functionset.h"#include "terminalset.h"
using namespace std;

enum typeInit
{
GROW_INIT,
FULL_INIT
};

enum typeNode
{
TERMINAL_NODE,
FUNCTION_NODE
};

class tree
{
public:
vector <node*> nodes;
int depth;
int counterNodes;

private:
node* root;
public:
tree(int depth);
~tree();

public:
void initialize(typeInit type);
void show();
node* getRoot();
int run();

private:
void initializeGrow(functionSet functions, terminalSet terminals, node* subroot, int depth);
int initializeFull(functionSet functions, terminalSet terminals, node* subroot, int depth);
int showSubtree(node* subtree, int depth);
int runSubtree(node* subtree, int depth);
};

#endif // TREE_H

1

c++genetic-programming stl

Решение

Другие решения

Используйте трехадресный код: https://en.wikipedia.org/wiki/Three-address_code.
С этим гораздо проще работать.

Посмотрите на реализацию варианта линейного генетического программирования под названием Multi-Expression Program, который использует его: http://www.mepx.org

0

Источник

Accepted Answer

Вы можете развивать свою идею, используя теговое объединение:

enum typeNode {TERMINAL_NODE, FUNCTION_NODE};

class node
{
union
{
int i;
func f;
};

typeNode type;

// ...
};

Только один из типов может быть использован одновременно type Поле явно указывает, какой из них используется.

По этому пути вы также можете использовать повышение :: вариант на месте анонимного союза.

Другой подход использует symbol базовый класс:

class symbol
{
public:
virtual int eval(int [] = nullptr) = 0;

// ...
};

class terminal : public symbol
{
public:
virtual int eval(int []) override;
{
return i;
}

// ...

private:
int i;
};

class function1 : public symbol
{
public:
virtual int eval(int params[]) override;
{
return f(params[0], params[1]);
}

// ...

private:
func f;
}

и node класс это что-то вроде:

class node
{
node *left, *right, *parent;
symbol *s;

// ...
};

Так как function класс не имеет состояния, вам нужно передать некоторые параметры eval функция. Это раздражает, но помогает сохранить простые части генетической программы (например, построение дерева, рекомбинация дерева …).

1