Бинарное дерево реализовать с помощью ссылок


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

#include <iostream>

struct Node {
  Node(Node& l, Node& r, const char* v) : left_child(l), right_child(r), value(v) {}
  const char* value;
  Node& left_child;
  Node& right_child;
};

Node null_node(null_node, null_node, "END_OF_TREE");

bool is_leaf(Node& node){
  return &node.left_child == &null_node && &node.right_child == &null_node;
}

void post_order(Node& node){
  if (is_leaf(node)){
    std::cout << node.value;
  }
  else{
    if (&node.left_child != &null_node){
       post_order(node.left_child);
    }
    if (&node.right_child != &null_node){
       post_order(node.right_child);
    }
    std::cout << node.value;
  }
}

int main(){
  Node n1(null_node, null_node, "1");
  Node n2(null_node, null_node, "2");
  Node n3(n1, n2, "3");
  Node n4(null_node, null_node, "4");
  Node n5(n3, n4, "5");
  post_order(n5);
}

Я до сих пор не могу понять, почему ссылки не уступает указатели. Что с помощью ссылок для бинарного дерева (кроме того, что вы не можете вставлять или удалять элементы)?

Кроме того, я совершенно новым для C++, поэтому любая обратная связь на сам код-это хорошо. Спасибо.



142
2
задан 8 апреля 2018 в 03:04 Источник Поделиться
Комментарии
2 ответа


Что с помощью ссылок для бинарного дерева (кроме того, что вы не можете вставлять или удалять элементы)?

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

(1) Вам пришлось изобрести null_node объект, который является глобальной переменной, и страдает все проблемы глобальные переменные (например, он не будет хорошо играть с динамическими библиотеками,.к.а. общая объектов.к.а. Библиотеки DLL, потому что вы могли закончиться вверх с программа, содержащая два null_node переменные — одна из основной программы и одной из DLL).

(2) Вы должны префикс все ваши обращается за дополнительную & характер.

Сравниваем свой путь (немного переформатировать для стиля и const-корректности):

void post_order(const Node& node) {
if (&node.left_child != &null_node) {
post_order(node.left_child);
}
if (&node.right_child != &null_node) {
post_order(node.right_child);
}
std::cout << node.value;
}

к "естественному" подходу:

void post_order(const Node *node) {
if (node->left_child) {
post_order(node->left_child);
}
if (node->right_child) {
post_order(node->right_child);
}
std::cout << node->value;
}

Который легче читать (и кстати писать)?

Обратите внимание, что синтаксис с++для указателей восходит аж к C, т. е. в середине 1970-х годов. Это было долгое время, чтобы польский и уточнить и упорядочить этот синтаксис. Вы пытаетесь изобрести что-то "лучше", без контроля определение языка. Вы не должны удивляться, что встроенный в, ~40-год-старый синтаксис действительно подходит для точной работы, для которых оно предназначено. :)

Кстати, если вы хотите иметь дело с пустыми деревьев в "естественный" способ, рассмотрим следующий рефакторинг:

void post_order(const Node *node) {
if (node != nullptr) {
post_order(node->left_child);
post_order(node->right_child);
std::cout << node->value;
}
}

Прямой код-лучший код!

3
ответ дан 8 апреля 2018 в 04:04 Источник Поделиться

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

Подумайте о ситуации в клиентский код использует new для создания узла экземпляра:

Node n1(null_node, null_node, "1");
Node* n2 = new Node(null_node, null_node, "2"); // Dynamically allocated for
// whatever reason
Node n3(n1, *n2, "3");

// Some exception prone code here ...

Node n4(null_node, null_node, "4");
Node n5(n3, n4, "5");
post_order(n5);

delete n2;

Может вызвать утечки памяти в случае исключение.

Также, если delete n2; используется до двоичного дерева экземпляре n5 выходит из области видимости, будет подвешенные в дереве.

Лучший выбор, чем при использовании сырых указателей или ссылок будет использовать соответствующий смарт-указатель, например

struct Node {
Node(std::unique_ptr<Node> l, std::unique_ptr<Node> r, const char* v)
: left_child(l), right_child(r), value(v) {}
const char* value;
std::unique_ptr<Node> left_child;
std::unique_ptr<Node> right_child;
};

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

2
ответ дан 8 апреля 2018 в 04:04 Источник Поделиться