Помогите с алгоритмом обхода бинарного дерева в ширину с++

70
05 февраля 2022, 08:40

Помогите пожалуйста с алгоритмом обхода дерева в ширину на с++ Вот код:

#include <vector>
#include <iostream>
#include <queue>
#define PRE 0
#define IN 1
#define POST 2

template<class T>
class tree
{
public:
    tree();
    ~tree();
    void push(T inf);
    std::vector<T> DFS(int flag);
    std::vector<T> BFS();
    int get_size();
private:
    struct node
    {
        node* left;
        node* right;
        T inf;
        node(T inf);
    };
    int size;
    node* root;
    void push(T inf, node* current);
    void DFS(node* current, std::vector<T> &buffer, int flag);
};

template <class T>
tree<T>::node::node(T inf)
{
    left = nullptr;
    right = nullptr;
    this -> inf = inf;
}

template<class T>
tree<T>::tree()
{
    size = 0;
    root = nullptr;
}

template<class T>
tree<T>::~tree()
{
}

template<class T>
int tree<T>::get_size()
{
    return size;
}

template<class T>
void tree<T>::push(T inf)
{
    if (root == nullptr)
    {
        root = new node(inf);
        size++;
    }
    else
    {
        if (inf <= root->inf)
        {
            if (root->left != nullptr)
                push(inf, root->left);
            else
            {
                root->left = new node(inf);
                size++;
            }
        }
        else
        {
            if (root->right != nullptr)
                push(inf, root->right);
            else
            {
                root->right = new node(inf);
                size++;
            }
        }
    }
}

template<class T>
void tree<T>::push(T inf, node* current)
{
    if (inf <= current->inf)
    {
        if (current->left != nullptr)
            push(inf, current->left);
        else
        {
            current->left = new node(inf);
            size++;
        }
    }
    else
    {
        if (current->right != nullptr)
            push(inf, current->right);
        else
        {
            current->right = new node(inf);
            size++;
        }
    }
}

template<class T>
std::vector<T> tree<T>::DFS(int flag)
{
    std::vector<T> buffer;
    buffer.reserve(size);
    if (root == nullptr)
         throw std::invalid_argument( "error - void tree\n" );
    if (flag == 0)
        buffer.push_back(root->inf);
    DFS(root->left, buffer, flag);
    if (flag == 1)
        buffer.push_back(root->inf);
    DFS(root->right, buffer, flag);
    if (flag == 2)
        buffer.push_back(root->inf);
    return buffer;
}

template<class T>
void tree<T>::DFS(node* current, std::vector<T> &buffer, int flag)
{
    if (current == nullptr)
        return;
    if (flag == 0)
        buffer.push_back(current->inf);
    DFS(current->left, buffer, flag);
    if (flag == 1)
        buffer.push_back(current->inf);
    DFS(current->right, buffer, flag);
    if (flag == 2)
        buffer.push_back(current->inf);
}
template<class T>
std::vector<T> tree<T>::BFS()
{
    std::queue<T> temp;
}
Answer 1

разобрался

template<class T>
std::vector<T> tree<T>::BFS()
{
    std::vector<T> buffer;
    buffer.reserve(size);
    std::queue<node> vertex;
    vertex.push(*root);
    while (!vertex.empty())
    {
        node current = vertex.front();
        vertex.pop();
        buffer.push_back(current.inf);
        if (current.left != nullptr)
            vertex.push(*current.left);
        if (current.right != nullptr)
            vertex.push(*current.right);
    }
    return buffer;
}
READ ALSO
Создать пару в MAP

Создать пару в MAP

Смысл цикла: вводятся с клавиатуры s1 и s2Если mapT[s2] существует, то заносится в multiset значение

98
Update varbinary(20) MySQL

Update varbinary(20) MySQL

гуру MySQL, подскажите, как правильно работать с типом данных varbinary(20)? Нужно взять исходное значение, изменить определенный бит и засетать обратноНе...

97
Как делается такое с записью в базе mysql?

Как делается такое с записью в базе mysql?

Хочу реализовать что то такое: Имеем на сайте кнопку и имеем счётчик:

99