Печать оставляет узел родительского бинарного дерева

Мое упражнение на C++ посвящено печати выходных родительских узлов в двоичном дереве. Я работал над двумя идеями, чтобы добиться этого. Они следующие

Идея 1

/* Write a program that finds and prints all vertices of a binary tree which have 
 * successor leaves only */

#include <iostream>

class Node{
  public:
    int data;
    Node* left = nullptr;
    Node* right = nullptr;

    Node(int value){data=value;}
};

bool traverse(Node* node);

bool traverse(Node* node){
  if (!node->left&&!node->right)
    return true;

  if (traverse(node->left)||traverse(node->right)) 
      std::cout<<node->data<<'\t';  

  if (node->left)
    traverse(node->left);

  if (node->right) 
    traverse(node->right);  
}//Non-void function does not return a value in all control paths

Плюсы:

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

Минусы

Моя основная проблема с моей функцией traverse заключается в том, что я не знаю, как реализовать отсутствующий оператор return false;, на который жалуется компилятор. Если я это сделаю, в моем понимании не будет рекурсии.

Идея 2

/* Write a program that finds and prints all vertices of a binary tree which have 
 * successor leaves only */

#include <iostream>

class Node{
  public:
    int data;
    Node* left = nullptr;
    Node* right = nullptr;
    bool isLeaf = false;

    Node(int value){data=value;}
};

void traverse(Node* node);

void traverse(Node* node){
  if (!node->left&&!node->right){
    node->isLeaf = true;
    return;
  }

  if (node->left||node->right) 
      std::cout<<node->data<<'\t';  

  if (node->left)
    traverse(node->left);

  if (node->right) 
    traverse(node->right);  
}

Плюсы:

Я чувствую, что идея 2 более эффективна и в некотором роде менее авантюрна.

Минусы

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

Ошибка

Что-то есть в этих двух идеях, чего я не могу понять. Почему они не зацикливаются рекурсивно? В обоих есть оператор return, который позволяет избежать бесконечного цикла, и рекурсивные вызовы происходят до тех пор, пока либо right, либо left дочерние элементы выходят. Может ли кто-нибудь сообщить мне, что я делаю неправильно с моей функцией traverse, пожалуйста?

Вопрос

Я также хотел бы, чтобы идея 1 работала, потому что мне нравится, как она проверяет, является ли узел родителем конечного узла, вызывая сам себя. Как я могу справиться с отсутствующим оператором return false;, который компилятор хочет, чтобы я включил?

Редактировать

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

int main(){
  Node* root = new Node(1);
  root->left = new Node(2);
  root->right = new Node(3);
  root->left->left = new Node(4);
  root->left->right = new Node (5);
  root->right->left = new Node(6);
  root->right->right = new Node(7);

  traverse(root);
  return 0;
}

Обновлять

Мой код недалек от решения, как сказал мне RandomBits. Он / она указал на некоторые недостатки в нем, и я протестировал его в песочнице. Результат хороший, но при каждом вызове функции он печатает родительские листы, чего я сейчас не понимаю.

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

trincot 27.05.2023 20:04

Не могли бы вы предоставить больше контекста прототипа bool... Это требование? Для чего вы собираетесь использовать метод? pre-order У ходьбы действительно нет другого применения, кроме печати содержимого. Если вы пытаетесь найти предшественника или преемника, вам следует взглянуть на обход in-order

I_throw_but_dont_catch 28.05.2023 03:59

Привет @trincot! Спасибо за вопрос. В основном упражнение заключается в печати родительского узла только с листьями, а листья находятся на нижнем уровне дерева.

wavesinaroom 30.05.2023 04:13

Привет, @TheCompile-TimeComedian! Только заметил, что прототип был избыточен. Я собираюсь снова прочитать о in-order обходе. Цель упражнения состоит в том, чтобы напечатать только листья родительских узлов, поэтому in-order обход имеет смысл.

wavesinaroom 30.05.2023 04:17

@JuanJáuregui хорошо, если бы задача заключалась в том, чтобы напечатать «печать только оставляет узлы родительского узла», чем любой обход. Вам понадобится обход in-order, если вы хотите найти преемника или предшественника. Третий блок кода в моем ответе должен быть тем, что вы ищете. Если это не так, пожалуйста, предоставьте более подробную информацию, чтобы мы могли вам помочь :-)

I_throw_but_dont_catch 30.05.2023 04:20

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

wavesinaroom 30.05.2023 04:59
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
6
69
4
Перейти к ответу Данный вопрос помечен как решенный

Ответы 4

Код Idea 1, который вы разместили, очень близок, но предупреждение компилятора может быть не единственной проблемой.

Я думаю, вы правы, склоняясь к решению, которое не требует дополнительных данных в структуре Node. Idea 1 будет считаться non-intrusive решением, а Idea 2intrusive решением.

  • Первое условие возвращает true для случая, когда нет дочерних элементов, то есть листового узла. Все остальные случаи — false, поэтому просто верните false в конце функции.
  • Я думаю, вы хотите напечатать узел только в том случае, если traverse дочернего элемента left и right возвращает true, то есть оба дочерних элемента являются листовыми узлами, но я могу не совсем понять проблему.
// Returns true if this node is a leaf, otherwise, false.
bool traverse(Node* node){

  if (!node->left&&!node->right)
    return true;

  // I think you want an `and` here, i.e. both children must be leaves
  if (traverse(node->left)&&traverse(node->right)) 
      std::cout<<node->data<<'\t';  

  if (node->left)
    traverse(node->left);

  if (node->right) 
    traverse(node->right);

  // There are at least some children, so not a leaf.
  return false;  
}

Привет @RandomBits! Спасибо за участие в ответе на вопрос. return false; в конце функция помогла. Все еще не заставляя рекурсию работать должным образом, это все еще сбивает с толку.

wavesinaroom 27.05.2023 05:03

Это самый близкий ответ прямо сейчас. Добавление && вместо || во втором условном плюсе return false в конце дает мне почти правильный результат. По какой-то причине первый родительский лист печатается дважды. Я выясняю, почему

wavesinaroom 31.05.2023 04:32

Я не вижу реального вопроса, но у меня возникла проблема с отображением деревьев, когда они стали глубокими и широкими. Я закончил тем, что напечатал его «боком», используя рекурсию головой вперед, которая хорошо работает для меня:

void BinTree::showTree(const Node *ptr, const int depth) {
        if (ptr->right != nullptr) {
                showTree(ptr->right, depth + 1);
        }
        cout << string(depth, '\t') << ptr->val << endl;
        if (ptr->left != nullptr) {
                showTree(ptr->left, depth + 1);
        }
}

Просто мои 0,02 доллара

Привет @David Rosario! Спасибо за Ваш ответ. Мой вопрос был о поиске способа справиться с отсутствующим оператором возврата idea 1 и почему моя функция не зацикливается рекурсивно. С другой стороны, мне нравится ваш ответ, и я выбрал этот подход для решения другой проблемы (обход двоичного дерева с порядком уровней). Я буду использовать его как запасной план, если не смогу idea 1 работать.

wavesinaroom 27.05.2023 05:10

Судя по всему, вы пересекаете дерево в pre-order (печатаете, а затем «обходите» дерево влево и вправо).

Я не совсем понимаю, почему вы должны использовать bool в этом случае, поскольку эти функции/методы обычно недействительны. Вы на правильном пути, рекурсия — ваш лучший друг в Data Structures.

Вот моя реализация для pre-ordertype void:

void traverse(Node* node /*root*/) {
  if (node == nullptr) {
    return; //do nothing
    
  }else if (node != nullptr){ //could just be an else
    std::cout << node -> data << "\t";
    
    traverse(root -> left); //walk left
    
    traverse(root -> right); //walk right
  }
}

Вот моя реализация printLeafNodestype void:

void printLeafNodes(Node* node) {
  if (node == nullptr) {
    return; 
  }

  if (node->left == nullptr && node->right == nullptr) {
    std::cout << node->data << "\t";
  }
  printLeafNodes(node->left); 
  printLeafNodes(node->right); 
}

Редактировать:

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

Код:

void traverse(Node* node) {
    if (!node)
        return;

    if (node->left && !node->left->left && !node->left->right)
        std::cout << node->left->data << '\t';

    if (node->right && !node->right->left && !node->right->right)
        std::cout << node->right->data << '\t';

    traverse(node->left);
    traverse(node->right);
}

Это должно ответить на ваш вопрос, я надеюсь.

По сути то же самое, но здесь вы проверяете, действительно ли это конечный узел. Отсутствие left или right дочернего элемента означает leaf узел

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

Чтобы ответить на ваш вопрос: почему они не зацикливаются рекурсивно? Трудно сказать без дополнительного контекста или не видя вашего главного. Вы возвращаетесь рано, если node->left или node->right это nullptr, возможно, ваше дерево skewed или degenerate.

Привет, комик @компиляции времени! Только что проверил ваш код после прочтения ваших ответов. Боюсь, на выходе получается 4 5 6 7 вместо 4 5, как ожидалось. Я вернусь к нему завтра, чтобы посмотреть, что с ним происходит. Кстати, я использовал cpp.sh для проверки. О, извините, это ввело в заблуждение, я включу функцию main в вопрос в качестве редактирования.

wavesinaroom 30.05.2023 05:09

Не беспокойся. SO не является службой «проверки кода», но если вы вставите свой код сюда и ответите комментарием (с той же ссылкой), мы сможем выяснить, в чем была проблема. Звучит отлично?

I_throw_but_dont_catch 30.05.2023 05:13

Да, это было бы здорово! Вот вам ссылка, в любом случае я вернусь к этому завтра.

wavesinaroom 30.05.2023 05:28

@JuanJáuregui да, вы должны вставить туда свой код и скопировать ссылку ... Все, что я вижу, это мой комментарий, говорящий: «Вставьте сюда свой код»

I_throw_but_dont_catch 30.05.2023 05:29

> recursion is your best friend in Data Structures. Не обязательно. Итеративное решение использует меньше системных ресурсов и в некоторых случаях может быть быстрее. Среди прочего, рекурсия может вызвать stack overflow.

pacmaninbw 30.05.2023 05:49

@pacmaninbw Хорошо, справедливое замечание ... Рекурсия требует больше ресурсов (генерация новых кадров стека), и ее сложно отлаживать **, но она также делает код «более» читаемым. Рекурсия - ваш лучший друг в (низкоуровневых) приложениях структур данных, например, в этом вопросе. Рассмотрим (BFS) или обход по уровням, итеративное решение в 3 раза длиннее вашего рекурсивного решения.

I_throw_but_dont_catch 30.05.2023 06:30

У меня большой опыт работы с рекурсией, см. мой вопрос по код-ревью.

pacmaninbw 30.05.2023 15:38

Я заметил небольшую разницу в производительности здесь

I_throw_but_dont_catch 30.05.2023 19:15

@TheCompile-TimeComedian Я только что перепроверил ссылку, которую я разместил в своем предыдущем комментарии вчера, и код был. Кроме того, я нажал на вашу ссылку и увидел, что там тоже есть код.

wavesinaroom 31.05.2023 04:12

Привет @pacmaninbw! Спасибо за участие. Действительно, бывают случаи, когда итеративная реализация работает лучше, чем рекурсия. Я помню, что факториалы - хороший пример, хотя структуры данных нет, жаль, что у меня сейчас нет примера со структурами данных. Кстати, я пытался прочитать ваш вопрос о проверке кода, но я его не понял, поэтому я буду продолжать работать над своими навыками, чтобы иметь возможность читать такой код.

wavesinaroom 31.05.2023 04:16

@JuanJáuregui Хороший пример, когда рекурсия отстой, - это последовательность Фибоначчи, если вы используете 64-битное целое число для вычисления огромных чисел, оно сожрет ваши ресурсы (2 ^ n временная сложность и n пространственная сложность). О, и я действительно не знаю, как работает проводник компилятора, поскольку, когда я нажимаю на свою ссылку, я вижу свою реализацию графа...

I_throw_but_dont_catch 31.05.2023 04:50

@TheCompile-TimeComedian, все в порядке! Я протестировал этот ответ здесь (кстати, нужен был сокращатель ссылок) с несбалансированным двоичным деревом. Вывод немного странный, завтра еще раз посмотрю :)

wavesinaroom 31.05.2023 05:03

@wavesinaroom Почему вы хотите напечатать 4 и 5? Это левое «поддерево» вашего главного дерева? Разве ваша задача не «Написать программу, которая находит и печатает все вершины бинарного дерева, у которых есть только листья-преемники»?

I_throw_but_dont_catch 31.05.2023 07:24

@ TheCompile-TimeComedian извините, мой плохой! На самом деле выход должен быть только 2 и 3

wavesinaroom 31.05.2023 16:47

@wavesinaroom вот, я думаю, это то, что вы ищете... Я протестировал его на большом дереве, и он печатает 4 5 6 7 именно то, что вам нужно.

I_throw_but_dont_catch 31.05.2023 17:32

@TheCompile-TimeComedian, извини, чувак, я открыл ссылку, и там не было ничего, кроме int square(int num){return num * num) Это случилось и со мной вчера, когда я пытался поделиться с тобой кодом

wavesinaroom 31.05.2023 19:25

это работает?

I_throw_but_dont_catch 31.05.2023 20:06
Ответ принят как подходящий

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

/* Write a program that finds and prints all vertices of a binary tree which have 
 * successor leaves only */

#include <iostream>

class Node{
  public:
    int data;
    Node* left = nullptr;
    Node* right = nullptr;

    Node(int value){data=value;}
};

bool isLeaf(Node* node){
  return !node->left&&!node->right;
}

bool isParent(Node* node){
  if (node)
    return (isLeaf(node->left)||isLeaf(node->right));
  else
    return false;
}

void printParent(Node* node){
  if (node == nullptr)
    return;

  if (!isLeaf(node)&&isParent(node))
    std::cout<<node->data<<'\n';

  if (node->left) 
    printParent(node->left);
  
  if (node->right) 
    printParent(node->right);  
}

int main(){
  Node* root = new Node(1);
  root->left = new Node(2);
  root->right = new Node(3);
  root->left->left = new Node(4);
  root->left->left->right = new Node(10);
  root->left->left->left = new Node(11);
  root->left->right = new Node (5);
  root->right->left = new Node(6);
  root->right->right = new Node(7);

  printParent(root);
  return 0;
}

Другие вопросы по теме