Генерация бинарного дерева

Я очень новичок в древовидных структурах данных. Я знаю, как работает вся структура, но не уверен, как подойти к случайной генерации.

Например, чтобы создать бинарное дерево с глубиной 3, вы, по сути, собираете части вместе одну за другой. то есть:

root = Node()
root.leftChild = Node()
root.rightChild = Node()
root.leftChild.leftChild = 'left'
root.rightChild.rightChild = 'right'

Вышеупомянутое не работает, когда я хочу случайным образом создавать структуры двоичного дерева, которые по-разному различаются между собой. Под случайным созданием древовидной структуры я подразумеваю случайное создание типа узла, случайное назначение дочернего элемента или его отсутствие, но конечный результат всегда будет иметь глубину N.

Есть ли у кого-нибудь предложения о том, как подойти к этому? Я хотел бы увидеть какой-нибудь псевдокод/алгоритм или что-то в этом роде.

Спасибо


random algorithm tree genetic-programming
person user1234440    schedule 24.01.2015    source источник
comment
возможный дубликат функции вставки в случайное двоичное дерево   -  person Stefan Ch    schedule 24.01.2015
comment
Если вы хотите сгенерировать n-уровневое дерево, просто убедитесь, что у вас есть хотя бы один узел, индекс которого idxMax находится в диапазоне от 2^(n-1) + 1 до 2^n, и, следовательно, дерево должно иметь idxMax / 2, idxMax / 4 ... idxMax / (2^log(idxMax) узел.   -  person pwwpche    schedule 24.01.2015
comment
Есть ли какие-нибудь алгоритмы, на которые вы можете мне указать для генерации случайных двоичных деревьев?   -  person user1234440    schedule 24.01.2015
comment
@ user1234440 Здесь у вас есть псевдокод из Полевого руководства по генетическому программированию, Поли, Лэнгдон, Макфи wklej.org/id /1798250   -  person    schedule 17.09.2015

Ответы (1)


arrow_upward
0
arrow_downward

Я написал простую программу, чтобы проиллюстрировать свой метод. Программа сгенерирует структуру, подобную бинарной куче, и ее будет просто преобразовать в вашу структуру.

#include <iostream>
#include <time.h>
using namespace std;

int main(){

    int maxDepth;    //The max depth of the tree
    int totalNodes;   //The least number of nodes in the tree.
    int realTotalNodes = 0;  //The real number of nodes in the tree.
    cin >> maxDepth >> totalNodes;

    srand(time(NULL));
    int indexMax = (1 << maxDepth) - 1 ;        //Max index of the nodes in the n-depth binary tree.
    bool* nodes = new bool[indexMax + 1];
    memset(nodes, 0, indexMax + 1);
    int lastMax = indexMax, lastMin =1 << (maxDepth - 1);       //Min and Max index of nodes at n-th level

    //First, promise that the tree will be n-level high.
    //That is, create a path from root to n-th level. 

    int lastIndex = (rand() % lastMin) + lastMin;       //Generate a node that is at n-th level.
    while(lastIndex > 0){       //Create its parent, grand-parent, grand-grand-parent...
            nodes[lastIndex] = true;
            realTotalNodes++;
            lastIndex = lastIndex / 2;
            totalNodes--;

    }

    while(totalNodes > 0){
        int currentIndex = rand() % indexMax;       //Randomly generate the leaves in the tree
        totalNodes--;
        while(currentIndex > 0){        //Create its parents...
            if(nodes[currentIndex] == true){    //If some parent exists, then its grand-parents have already been created. 
                break;
            }
            nodes[currentIndex] = true;
            realTotalNodes++;
            currentIndex = currentIndex / 2;
            totalNodes--;
        }
    }

    //Print these stuff.
    int level = 2;
    for(int i = 1 ; i < indexMax ; i++){
        if(nodes[i]){
            cout << i << "\t";
        }
        if(i == level - 1){
            cout << endl;
            level = level * 2;
        }
    }

    return 0;
}
person pwwpche    schedule 24.01.2015