C ++ двоичное дерево с минимальной кучей - PullRequest
Новая
       31

C ++ двоичное дерево с минимальной кучей

0 голосов
/ 12 мая 2018

Я пытаюсь сделать минимальную кучу в дереве, однако я новичок здесь, и у меня уже есть две недели, теперь я возвращаюсь назад с указателями и адресами,

, поэтому я делаюструктура, подобная этой: 

struct node{
    int data;
    node* left;
    node* right;
};

и затем функция вставки, подобная этой: 

void Insert(int dataii){
    node* new_node = new node();
    new_node->data = dataii;
    new_node->left = new_node->right = NULL;
}

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

Я думаю использовать массив для хранения номеров new_nodes в массиве [0], а затем в массиве [1] и т. Д., Связывая их с доблестью new_node-> data и address.

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

После того, как у каждого родителя будет максимум два ребенка, и всегда при вставке они идут изслева направо.

Если кто-нибудь может дать мне хорошую идею, как идти вперед, спасибо.Tiago

1 Ответ

0 голосов
/ 12 мая 2018

Это должно помочь вам. 

#include<iostream>

using namespace std;

class Node{
public:
    int data;
    Node *left, *right;

    Node(int data);
    ~Node();
    int count();
    void insert(Node *n);
    void print(const int indent, const char* note);
};

Node::Node(int data) {
   this->data = data;
   this->left = this->right = NULL;
}

Node::~Node(){
    if (this->left != NULL) delete this->left;
    if (this->right != NULL) delete this->right;
}

int Node::count() {
    int r = 1;
    if (this->left != NULL) r += this->left->count();
    if (this->right != NULL) r += this->right->count();
    return r;
}

void Node::insert(Node* n){
    if (this->left == NULL) this->left = n;
    else if (this->right == NULL) this->right = n;
    else if (this->left->count() > this->right->count()) this->right->insert(n);
    else this->left->insert(n);
}

void Node::print(const int indent=0, const char *note="") {
    for(int i = 0; i < indent; i++) cout << " ";
    cout << this->data << " " << note << endl;
    if (this->left != NULL) this->left->print(indent+1, "(l)");
    if (this->right != NULL) this->right->print(indent+1, "(r)");
}

int main(int argc, char const *argv[]) {
    Node *root = new Node(0);
    for (int i = 1; i <= 10; i++) root->insert(new Node(i));
    root->print();
    delete root;
    return 0;
}

См. Полный проект с реализованными min / max кучами

...