Скопируйте двоичное дерево итеративным способом - PullRequest
Новая
       4

Скопируйте двоичное дерево итеративным способом

10 голосов
/ 10 марта 2012

Мне задали этот вопрос в интервью, и это буквально стоило мне работы: P Интервьюер спросил, что вам дадут корень дерева, и вы должны вернуть корень к скопированному дереву, но копиядолжно быть сделано итеративным способом.Я вставляю свой код здесь, я написал то же самое там, и он отлично работает.Сначала я сделал это с помощью двух стеков, которые, по словам интервьюера, ему не понравились, а затем я сделал это следующим образом.Интервьюер был недоволен тем, что я использовал другую структуру, которая содержит указатель на исходное и конечное дерево (см. Код).

Мне интересно, есть ли другой, лучший способ сделать это ?? 

struct node
{
   int data;
   struct node * left;
   struct node * right;
};

struct copynode
{
   node * original;
   node * final;
};

node * copy(node *root)
{
    stack <copynode*> s;
    copynode * temp=(copynode*)malloc(sizeof(copynode));
    temp->original=root;
    temp->final=(node *)malloc(sizeof(node));
    s.push(temp);
    while(s.empty()==false)
    {
       copynode * i;
       i=s.top();
       s.pop();
       i->final=i->original;
       if(i->original->left)
       {
          copynode *left=(copynode*)malloc(sizeof(copynode));
          left->original=i->original->left;
          left->final=(node *)malloc(sizeof(node));
          s.push(left);
       }
       if(i->original->right)
       {
          copynode *right=(copynode*)malloc(sizeof(copynode));
          right->original=i->original->right;
          right->final=(node *)malloc(sizeof(node));
          s.push(right);
       }
   }  
   return temp->final;
}

Ответы [ 7 ]

17 голосов
/ 10 марта 2012

Если вам разрешено иметь родительские указатели в каждом узле, вам даже не нужен стек:

Идите параллельно исходному дереву и дереву, которое вы создаете.Если текущий узел в исходном дереве имеет левого дочернего элемента, но узел в дереве, которое вы создаете, не имеет, создайте его и спуститесь влево.Аналогично с правильными детьми.Если ни одно из условий не применимо, увеличьте значение.

В коде (C #): 

public static Node Clone(Node original)
{
    if (original == null)
        return null;

    var root = new Node(original.Data, null);
    var clone = root;

    while (original != null)
    {
        if (original.Left != null && clone.Left == null)
        {
            clone.Left = new Node(original.Left.Data, clone);
            original = original.Left;
            clone = clone.Left;
        }
        else if (original.Right != null && clone.Right == null)
        {
            clone.Right = new Node(original.Right.Data, clone);
            original = original.Right;
            clone = clone.Right;
        }
        else
        {
            original = original.Parent;
            clone = clone.Parent;
        }
    }

    return root;
}
1 голос
/ 10 марта 2012

две идеи:

  1. вам нужен стек или родительские ссылки для обхода дерева ввода (afaict). так что давайте предположим, что интервьюер был бы счастлив с одним из них. что осталось упростить?

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

    и нетрудно увидеть, что обход предварительного заказа будет делать это (при условии, что при добавлении не происходит перебалансировки).

    чтобы вы могли написать свою копию с точки зрения обхода предварительного заказа плюс простое добавление в корень копии. это дало бы более простой код и / или разрешило бы повторное использование за счет того, что оно менее эффективно (у вас есть O (nlog (n)) дополнительных «прыжков», чтобы найти правильные места в вашей копии при вставке).

  2. для неизменяемых узлов вам нужно только скопировать корень (это нормальный функциональный стиль).

мое внутреннее чувство состоит в том, что (1) может быть тем, что он искал, учитывая ссылку на "свойства дерева".

1 голос
/ 10 марта 2012

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

РЕШЕНИЕ: 

public Node clone() {
    if(null == root)
        return null;
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(root);
    Node n;

    Queue<Node> q2 = new LinkedList<Node>();
    Node fresh;
    Node root2 = new Node(root.data);
    q2.add(root2);

    while(!queue.isEmpty()) {
        n=queue.remove();
        fresh = q2.remove();
        if(null != n.left) {
            queue.add(n.left);
            fresh.left = new Node(n.left.data);
            q2.add(fresh.left);
        }
        if(null != n.right) {
            queue.add(n.right);
            fresh.right= new Node(n.right.data);
            q2.add(fresh.right);
        }           
    }       
    return root2;
}//

ФАЙЛ ПРОГРАММЫ: 

import java.util.LinkedList;
import java.util.Queue;

public class BST {
Node root;

public BST() {
    root = null;
}

public void insert(int el) {

    Node tmp = root, p = null;
    while (null != tmp && el != tmp.data) {
        p = tmp;
        if (el < tmp.data)
            tmp = tmp.left;
        else
            tmp = tmp.right;
    }
    if (tmp == null) {
        if (null == p)
            root = new Node(el);
        else if (el < p.data)
            p.left = new Node(el);
        else
            p.right = new Node(el);
    }
}//

public Node clone() {
    if(null == root)
        return null;
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(root);
    Node n;

    Queue<Node> q2 = new LinkedList<Node>();
    Node fresh;
    Node root2 = new Node(root.data);
    q2.add(root2);

    while(!queue.isEmpty()) {
        n=queue.remove();
        fresh = q2.remove();
        if(null != n.left) {
            queue.add(n.left);
            fresh.left = new Node(n.left.data);
            q2.add(fresh.left);
        }
        if(null != n.right) {
            queue.add(n.right);
            fresh.right= new Node(n.right.data);
            q2.add(fresh.right);
        }           
    }       
    return root2;
}//

private void inOrder(Node n) {
    if(null == n) return;
    inOrder(n.left);
    System.out.format("%d;", n.data);
    inOrder(n.right);
}//

public static void main(String[] args) {
    int[] input = { 50, 25, 75, 10, 35, 60, 100, 5, 20, 30, 45, 55, 70, 90,
            102 };
    BST bst = new BST();
    for (int i : input)
        bst.insert(i);
    Node root2 = bst.clone();
    bst.inOrder(root2);
}
}

class Node {
public int data;
public Node left;
public Node right;

public Node(int el) {
    data = el;
}
}
0 голосов
/ 22 июля 2017

Рассмотрим ниже дерева: 

                      10
                      / \
                    20   30
                    /\
                  40  50
                      /\
                     60 70

Теперь на основе BFS, если вы создаете массив узлов (массив используется для более быстрого доступа), это будет выглядеть так:

Массив узлов: 10 20 30 40 50 N N N N 60 70 N N N N

Индекс: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Обратите внимание, что индексирование основано на 1 для более простого расчета, и дочерние узлы листьев обозначаются как N для NULL.

Теперь, если вы заметите, что для узла с индексом i его левый потомок находится с индексом 2 * i, а его правый потомок с индексом 2 * i + 1. Это свойство правильное двоичное дерево.

Теперь, чтобы скопировать двоичное дерево не рекурсивно.

  1. Создать массив узлов из исходного дерева на основе BFS.
  2. Назначить ток = 1 (ток для индекса),

  3. Делать ниже, пока текущий <= размер массива узлов </p>

    а. создать новый узел (родитель)

    б. Присвойте значение parent-> val из узла на текущий момент.

    с. Замените оригинальный узел в текущем (индекс) новым узлом. // Этот шаг должен пройти через новые узлы.

    * 1 035 * d. создайте новый узел, назначьте parent-> left и присвойте значение из Lindex = 2 * current.

    е. Замените оригинальный узел в Lindex новым узлом.

    е. создать новый узел, назначить parent-> right и присвоить значение из Rindex = 2 * current + 1.

    е. Замените оригинальный узел в Rindex новым узлом.

    е. Увеличение тока на 1.

Теперь приближаемся ко времени сложности,

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

Если число узлов в исходном дереве равно n, то по свойству двоичного дерева число внешних узлов двоичного дерева всегда на 1 больше, чем количество внутренних узлов, 

 a. Number of external nodes is (n + 1) /2.
 b. Number of children of external nodes (count of all null nodes) is 2 * (n + 1)/2 = n + 1.
 c. Thus the total size of array is number of nodes + number of null nodes = n + n + 1 = 2n + 1

Поскольку во всем алгоритме мы прошли через весь массив, временная сложность этого подхода составляет O (n).

0 голосов
/ 12 июня 2017

Java-код, который работает и имеет относительно простой подход: 

static Node cloneTree(Node original){
    if(original == null) return null;

    Node temp = original;
    Node root = temp;
    if(original.left!=null)
      temp.left = original.left;
    if(original.right!=null)
      temp.right = original.right;

   cloneTree(original.left);
   cloneTree(original.right);
  return root;
}
0 голосов
/ 12 января 2015

Вот мой рабочий код:

Для каждого узла нажимайте сначала влево, один нажимайте на левые узлы, нажимайте на правый узел и затем повторяйте то же самое. 

#include <iostream>
#include <stack>

using namespace std;

struct Node {
    Node() 
    : left(NULL), right(NULL) {}
    int val;
    Node *left;
    Node *right;
};

struct Wrap {
    Wrap()
    : oldNode(NULL), newNode(NULL), flags(0) {}
    Node *oldNode;
    Node *newNode;
    int flags;
};

void InOrder(Node *node) {
    if(node == NULL) {
        return;
    }
    InOrder(node->left);
    cout << node->val << " ";
    InOrder(node->right);
}

Node *AllocNode(int val) {
    Node *p = new Node;
    p->val = val;
    return p;
}

Wrap *AllocWrap(Node *old) {
    Wrap *wrap = new Wrap;

    Node *newNode = new Node;
    newNode->val = old->val;

    wrap->oldNode = old;
    wrap->newNode = newNode;

    return wrap;
}

Wrap* PushLeftNodes(stack<Wrap*> &stk) {

    Wrap *curWrap = stk.top();  
    while(((curWrap->flags & 1) == 0) && (curWrap->oldNode->left != NULL)) {
        curWrap->flags |= 1;
        Wrap *newWrap = AllocWrap(curWrap->oldNode->left);
        stk.push(newWrap);
        curWrap->newNode->left = newWrap->newNode;
        curWrap = newWrap;
    }
    return curWrap;
}

Node *Clone(Node *root) {

    if(root == NULL) {
        return NULL;
    }

    Node *newRoot = NULL;
    stack<Wrap*> stk;

    Wrap *wrap = AllocWrap(root);
    stk.push(wrap);

    while(!stk.empty()) {
        wrap = PushLeftNodes(stk);
        if(((wrap->flags & 2) == 0) && (wrap->oldNode->right != NULL)) {
            wrap->flags  |= 2;
            Wrap *newWrap = AllocWrap(wrap->oldNode->right);
            stk.push(newWrap);
            wrap->newNode->right = newWrap->oldNode;
            continue;
        }

        wrap = stk.top();
        newRoot = wrap->newNode;
        stk.pop();
        delete wrap;
    }
    return newRoot;
}

int main() {
    Node *root = AllocNode(10);
    Node *curNode = root;

    curNode->left = AllocNode(5);
    curNode->right = AllocNode(15);

    curNode = curNode->left;
    curNode->left = AllocNode(14);

    curNode->right = AllocNode(17);

    curNode = curNode->right;
    curNode->left = AllocNode(18);
    curNode->right = AllocNode(45);

    curNode = root->right;
    curNode->right = AllocNode(33);

    curNode = curNode->right;
    curNode->right = AllocNode(46);

    cout << "Original tree : " << endl;
    InOrder(root);

    Node *newRoot = Clone(root);
    cout << "New tree : " << endl; 
    InOrder(newRoot);

    return 0;
}
0 голосов
/ 10 марта 2012

Один из методов без рекурсии состоял бы в том, чтобы пройти через каждый узел, и если узел содержит правую ветвь, поместите этот правый узел в стек.Когда у вас закончатся узлы вдоль вашего пути (следуя только за узлами с левыми ветвями), вытолкните верхний узел из стека и следуйте ему, используя те же правила (нажмите вправо, затем следуйте влево).Повторяйте этот цикл, пока ваш стек не станет пустым.Для этого требуется только один стек.

Редактировать: Вы спрашивали интервьюера, какой метод он / она искал?Если нет, то вы должны были бы таким образом, который предполагает вашу готовность изучать новые вещи, и вы должны были попытаться сделать это двусторонним диалогом.Я уверен, что у вас есть желание учиться чему-то новому (или вы не разместили бы здесь), но знал ли об этом ваш интервьюер?Имейте в виду, что интервьюеры, как правило, не ищут конкретного ответа на вещи, а скорее оценивают ваш подход к их решению, а не чисто техническим способом.Если вы не участвовали в этом, вы не позволили интервьюеру считать, что вы не знаете всего, но способны учиться и могут стать отличным дополнением к своей команде.

...