Как развернуть только листья в дереве Stack Overflow
Может кто-нибудь, пожалуйста, помогите мне с этой проблемой. Мой профессор включил его в учебное пособие, но я не знаю, как с ним справиться, и он не дает нам решения, поэтому любая помощь будет признательна. Спасибо заранее за ваше время!!
Извините, я не могу опубликовать изображения здесь, но вот ссылка на изображение проблемы:
http://postimg.org/image/f70i9dr7f/
Решение
Итак, ваша задача — перейти к каждому листовому узлу в вашем дереве и добавить к нему 2 новых узла как детей, используя x и y в качестве значений.
Конечные узлы — это узлы, которые сами не имеют дочерних узлов, так что ваш узел определяется как
struct Node{
int value;
Node* left;
Node* right;
}
затем в примере показать на вашем изображении узел 3, если он был сохранен в
Узел * Стив;
было бы
steve->value = 3;
steve->left = NULL;
steve->right = NULL;
так что это было бы сделано в другой раз, поэтому вам нужно найти узлы, которые и слева, и справа равны NULL, а затем создать новые листовые узлы с x и y в них, как в вашем примере
steve->left = new Node;
steve->left-> value = x;
steve->right-> value = new Node;
steve->right-> value = y;
так что это будет что-то вроде вашего кода, чтобы фактически добавить его, но вам придется придумать способ пройти по дереву и найти эти узлы
Другие решения
Давайте предположим, что Treenode выглядит примерно так:
typedef int ItemType;
class Treenode
{
int value;
ItemType *left, *right;
}
Я бы предложил рекурсивный метод:
Treenode* expand_leaves(Treenode* node, ItemType x, ItemType y)
{
/* If the argument node has no childs, he becomes father of x & y */
if(node->left == NULL && node->right == NULL)
{
node->left = new Node;
node->left->value=x;
node->right = new Node;
node->right->value=y;
}
else /* Otherwise if he has a left or right child, let's recall the function checking his child(s) */
{
if(node->left) expand_leaves(node->left, x, y);
if(node->right) expand_leaves(node->right, x, y);
}
return node;
}
Обратите внимание, что функция на самом деле модифицирует дочерние узлы того, который она получает в качестве аргумента, поэтому, если вы используете ее в назначении, подобном этому:
Treenode *a, *b;
///... code that modifies a
b=expandleaves(a, 1, 2);
a и b будут указывать точно на один и тот же узел.
Кроме того, я думаю, что мог кое-что забыть, но для меня это лучший способ.
Не видя доступных конструкторов Treenode кое-что из этого является предположением и / или более грязным, чем это должно быть. Но основная идея заключается в создании нового узла для каждой существующей позиции, а также для каждого нового листа.
Treenode* expand_leaves(Treenode* node, ItemType x, ItemType y)
{
if (node==0) return 0;
Treenode* result = new Treenode;
result->value = node->value;
/* If the argument node has no childs */
if(node->left == NULL && node->right == NULL)
{
result->left = new Treenode;
result->left->value=x;
result->right = new Treenode;
result->right->value=y;
}
else /* Otherwise if he has a left or right child, let's recall the function checking his child(s) */
{
result->left = expand_leaves(node->left, x, y);
result->right= expand_leaves(node->right, x, y);
}
return result;
}