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

Question

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

Answer 1

Так что ваша задача перейти к каждому узлу листьев в дереве и добавить 2 новых узлов к нему, как дети, используя x и y в качестве их значений. узлов листьев являются узлами, которые не имеют какие-либо сами ребенок так говорят, что ваш узел определяются как

struct Node{ 
int value; 
Node* left; 
Node* right; 
} 

затем в примере показывает в изображении 3'в узле, если он был сохранен в Node * Стиве; будет

steve->value = 3; 
steve->left = NULL; 
steve->right = NULL; 

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

steve->left = new Node; 
steve->left-> value = x; 
steve->right-> value = new Node; 
steve->right-> value = y; 

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

Answer 2

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

Answer 3

Не видя доступных конструкторов 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; 
}