Как развернуть только листья в дереве Stack Overflow

Может кто-нибудь, пожалуйста, помогите мне с этой проблемой. Мой профессор включил его в учебное пособие, но я не знаю, как с ним справиться, и он не дает нам решения, поэтому любая помощь будет признательна. Спасибо заранее за ваше время!!
Извините, я не могу опубликовать изображения здесь, но вот ссылка на изображение проблемы:
http://postimg.org/image/f70i9dr7f/

-3

Решение

Итак, ваша задача — перейти к каждому листовому узлу в вашем дереве и добавить к нему 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;

так что это будет что-то вроде вашего кода, чтобы фактически добавить его, но вам придется придумать способ пройти по дереву и найти эти узлы

1

Другие решения

Давайте предположим, что 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 будут указывать точно на один и тот же узел.
Кроме того, я думаю, что мог кое-что забыть, но для меня это лучший способ.

0

Не видя доступных конструкторов 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;
}
0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector