Мое упражнение на C++ посвящено печати выходных родительских узлов в двоичном дереве. Я работал над двумя идеями, чтобы добиться этого. Они следующие
/* 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;
, на который жалуется компилятор. Если я это сделаю, в моем понимании не будет рекурсии.
/* 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. Он / она указал на некоторые недостатки в нем, и я протестировал его в песочнице. Результат хороший, но при каждом вызове функции он печатает родительские листы, чего я сейчас не понимаю.
Не могли бы вы предоставить больше контекста прототипа bool
... Это требование? Для чего вы собираетесь использовать метод? pre-order
У ходьбы действительно нет другого применения, кроме печати содержимого. Если вы пытаетесь найти предшественника или преемника, вам следует взглянуть на обход in-order
Привет @trincot! Спасибо за вопрос. В основном упражнение заключается в печати родительского узла только с листьями, а листья находятся на нижнем уровне дерева.
Привет, @TheCompile-TimeComedian! Только заметил, что прототип был избыточен. Я собираюсь снова прочитать о in-order
обходе. Цель упражнения состоит в том, чтобы напечатать только листья родительских узлов, поэтому in-order
обход имеет смысл.
@JuanJáuregui хорошо, если бы задача заключалась в том, чтобы напечатать «печать только оставляет узлы родительского узла», чем любой обход. Вам понадобится обход in-order
, если вы хотите найти преемника или предшественника. Третий блок кода в моем ответе должен быть тем, что вы ищете. Если это не так, пожалуйста, предоставьте более подробную информацию, чтобы мы могли вам помочь :-)
На самом деле я читаю ваш ответ прямо сейчас и проверяю его в песочнице, прежде чем проверять его как правильный ответ. Это определенно работает, но я уверен, что понимаю это полностью. Боюсь, моя возвращающая логическая функция работает плохо, поэтому на этот раз я воспользуюсь вашим кодом. Спасибо за вашу помощь!
Код Idea 1
, который вы разместили, очень близок, но предупреждение компилятора может быть не единственной проблемой.
Я думаю, вы правы, склоняясь к решению, которое не требует дополнительных данных в структуре Node
. Idea 1
будет считаться non-intrusive
решением, а Idea 2
— intrusive
решением.
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;
в конце функция помогла. Все еще не заставляя рекурсию работать должным образом, это все еще сбивает с толку.
Это самый близкий ответ прямо сейчас. Добавление &&
вместо ||
во втором условном плюсе return false
в конце дает мне почти правильный результат. По какой-то причине первый родительский лист печатается дважды. Я выясняю, почему
Я не вижу реального вопроса, но у меня возникла проблема с отображением деревьев, когда они стали глубокими и широкими. Я закончил тем, что напечатал его «боком», используя рекурсию головой вперед, которая хорошо работает для меня:
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
работать.
Судя по всему, вы пересекаете дерево в pre-order
(печатаете, а затем «обходите» дерево влево и вправо).
Я не совсем понимаю, почему вы должны использовать bool
в этом случае, поскольку эти функции/методы обычно недействительны. Вы на правильном пути, рекурсия — ваш лучший друг в Data Structures
.
Вот моя реализация для pre-order
type 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
}
}
Вот моя реализация printLeafNodes
type 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
в вопрос в качестве редактирования.
Не беспокойся. SO не является службой «проверки кода», но если вы вставите свой код сюда и ответите комментарием (с той же ссылкой), мы сможем выяснить, в чем была проблема. Звучит отлично?
Да, это было бы здорово! Вот вам ссылка, в любом случае я вернусь к этому завтра.
@JuanJáuregui да, вы должны вставить туда свой код и скопировать ссылку ... Все, что я вижу, это мой комментарий, говорящий: «Вставьте сюда свой код»
> recursion is your best friend in Data Structures.
Не обязательно. Итеративное решение использует меньше системных ресурсов и в некоторых случаях может быть быстрее. Среди прочего, рекурсия может вызвать stack overflow
.
@pacmaninbw Хорошо, справедливое замечание ... Рекурсия требует больше ресурсов (генерация новых кадров стека), и ее сложно отлаживать **, но она также делает код «более» читаемым. Рекурсия - ваш лучший друг в (низкоуровневых) приложениях структур данных, например, в этом вопросе. Рассмотрим (BFS) или обход по уровням, итеративное решение в 3 раза длиннее вашего рекурсивного решения.
У меня большой опыт работы с рекурсией, см. мой вопрос по код-ревью.
Я заметил небольшую разницу в производительности здесь
@TheCompile-TimeComedian Я только что перепроверил ссылку, которую я разместил в своем предыдущем комментарии вчера, и код был. Кроме того, я нажал на вашу ссылку и увидел, что там тоже есть код.
Привет @pacmaninbw! Спасибо за участие. Действительно, бывают случаи, когда итеративная реализация работает лучше, чем рекурсия. Я помню, что факториалы - хороший пример, хотя структуры данных нет, жаль, что у меня сейчас нет примера со структурами данных. Кстати, я пытался прочитать ваш вопрос о проверке кода, но я его не понял, поэтому я буду продолжать работать над своими навыками, чтобы иметь возможность читать такой код.
@JuanJáuregui Хороший пример, когда рекурсия отстой, - это последовательность Фибоначчи, если вы используете 64-битное целое число для вычисления огромных чисел, оно сожрет ваши ресурсы (2 ^ n временная сложность и n пространственная сложность). О, и я действительно не знаю, как работает проводник компилятора, поскольку, когда я нажимаю на свою ссылку, я вижу свою реализацию графа...
@TheCompile-TimeComedian, все в порядке! Я протестировал этот ответ здесь (кстати, нужен был сокращатель ссылок) с несбалансированным двоичным деревом. Вывод немного странный, завтра еще раз посмотрю :)
@wavesinaroom Почему вы хотите напечатать 4 и 5? Это левое «поддерево» вашего главного дерева? Разве ваша задача не «Написать программу, которая находит и печатает все вершины бинарного дерева, у которых есть только листья-преемники»?
@ TheCompile-TimeComedian извините, мой плохой! На самом деле выход должен быть только 2 и 3
@wavesinaroom вот, я думаю, это то, что вы ищете... Я протестировал его на большом дереве, и он печатает 4 5 6 7
именно то, что вам нужно.
@TheCompile-TimeComedian, извини, чувак, я открыл ссылку, и там не было ничего, кроме int square(int num){return num * num)
Это случилось и со мной вчера, когда я пытался поделиться с тобой кодом
это работает?
Потребовалось некоторое время, но я сделал это. Очень доволен результатом, многому научился, выполняя это упражнение.
/* 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;
}
что подразумевается под узлами-преемниками? Я бы ожидал такой термин в упорядоченном дереве. Например, в бинарном дереве поиска преемник узла никогда не может быть его левым потомком. Если у него есть правильный потомок, то его преемник находится где-то в этом поддереве. Что здесь означает «преемник»?