Зеркальное изображение двоичного дерева

Ответ 1

Звучит как домашнее задание.

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

struct node *mirror(struct node *here) {

  if (here == NULL)
     return NULL;
  else {

    struct node *newNode = malloc (sizeof(struct node));

    newNode->value = here->value;
    newNode->left = mirror(here->right);
    newNode->right = mirror(here->left);

    return newNode;
  }
}

Это возвращает новое дерево - некоторые другие ответы делают это на месте. Зависит от того, что ваше задание попросило вас сделать.

Ответ 2

void swap_node(node n) {
  if(n != null) {
    node tmp = n.left;
    n.left = n.right;
    n.right = tmp;

    swap_node(n.left);
    swap_node(n.right);
  }
}

swap_node(root);

Ответ 3

Банальное решение:

for each node in tree
    exchange leftchild with rightchild.

Ответ 4

Рекурсивные и итеративные методы в JAVA: 1) Рекурсивный:

    public static TreeNode mirrorBinaryTree(TreeNode root){

    if(root == null || (root.left == null && root.right == null))
        return root;

    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

    mirrorBinaryTree(root.left);
    mirrorBinaryTree(root.right);


    return root;

}

2) Итеративный:

public static TreeNode mirrorBinaryTreeIterative(TreeNode root){
    if(root == null || (root.left == null && root.right == null))
        return root;

    TreeNode parent = root;
    Stack<TreeNode> treeStack = new Stack<TreeNode>();
    treeStack.push(root);

    while(!treeStack.empty()){
        parent = treeStack.pop();

        TreeNode temp = parent.right;
        parent.right = parent.left;
        parent.left = temp;

        if(parent.right != null)
            treeStack.push(parent.right);
        if(parent.left != null)
            treeStack.push(parent.left);
    }
    return root;
}

Ответ 5

void mirror(struct node* node)  
{
   if (node==NULL)
   {
      return;
   }
   else 
   {
      struct node* temp;
      mirror(node->left);
      mirror(node->right);
      temp = node->left;
      node->left = node->right;
      node->right = temp;
    }
}

Ответ 6

Итеративное решение:

public void mirrorIterative() {
    Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
    nodeQ.add(root);
    while(!nodeQ.isEmpty()) {
        TreeNode node = nodeQ.remove();
        if(node.leftChild == null && node.rightChild == null)
            continue;
        if(node.leftChild != null && node.rightChild != null) {
            TreeNode temp = node.leftChild;
            node.leftChild = node.rightChild;
            node.rightChild = temp;
            nodeQ.add(node.leftChild);
            nodeQ.add(node.rightChild);
        }
        else if(node.leftChild == null) {
            node.leftChild = node.rightChild;
            node.rightChild = null;
            nodeQ.add(node.leftChild);
        } else {
            node.rightChild = node.leftChild;
            node.leftChild = null;
            nodeQ.add(node.rightChild);
        }
    }
}

Ответ 7

void mirror(node<t> *& root2,node<t> * root)
{
    if(root==NULL)
    {
        root2=NULL;
    }
    else {
        root2=new node<t>;
        root2->data=root->data;
        root2->left=NULL;
        root2->right=NULL;
        mirror(root2->left,root->right);
        mirror(root2->right,root->left);
    }
}

Ответ 8

TreeNode * mirror(TreeNode *node){
  if(node==NULL){
    return NULL;
  }else{
    TreeNode *temp=node->left;
    node->left=mirror(node->right);
    node->right=mirror(temp);
    return node;
  }
}

Ответ 9

Вот моя функция. Если вы предлагаете лучшее решение:

void mirrorimage(struct node *p)
{
    struct node *q;
    if(p!=NULL)
    {
        q=swaptrs(&p);
        p=q;
        mirrorimage(p->left);
        mirrorimage(p->right);
    }
}

struct node* swaptrs(struct node **p)
{
    struct node *temp;
    temp=(*p)->left;
    (*p)->left=(*p)->right;
    (*p)->right=temp;
    return (*p);
}

Ответ 10

Рекурсивный код Java

public class TreeMirrorImageCreator {

public static Node createMirrorImage(Node originalNode,Node mirroredNode){

    mirroredNode.setValue(originalNode.getValue());

    if(originalNode.getLeft() != null){
        mirroredNode.setLeft(createMirrorImage(originalNode.getRight(),new Node(0)));
    }

    if(originalNode.getRight() != null){
        mirroredNode.setRight(createMirrorImage(originalNode.getLeft(), new Node(0)));
    }

    return mirroredNode;

}
}

Ответ 11

struct node *MirrorOfBinaryTree( struct node *root)
{ struct node *temp;
if(root)
{
MirrorOfBinaryTree(root->left);
MirrorOfBinaryTree(root->right);
/*swap the pointers in this node*/
temp=root->right;
root->right=root->left;;
root->left=temp;
}
return root;
}

Сложность времени: O (n) Сложность пространства: O (n)

Ответ 12

Ну, у этого вопроса есть много ответов. Я отправляю итеративную версию для этого, что довольно легко понять. Это использует Traversal порядка уровня.

//Function for creating Binary Tree
//Assuming *root for original tree and *root2 for mirror tree
//are declared globally
void insert(int data)
{
struct treenode* temp;
if(root2 == NULL)
{
root2 = createNode(data);
return;
}
else{
queue<treenode*> q;
q.push(root2);
while(!q.empty())
{
 temp = q.front();
 q.pop();
 if(temp->left)
 q.push(temp->left);
 else{
 temp->left = createNode(data);
 return;
}
if(temp->right)
{
q.push(temp->right);
}
else{
temp -> right = createNode(data);
return;
}
}
}
}
//Iterative version for Mirror of a Binary Tree 
void mirrorBinaryTree()
{
struct treenode *front;
queue<treenode*> q;
q.push(root);
while(!q.empty())
{
 front = q.front();
 insert(front->data);
 q.pop();
 if(front->right)
 q.push(front->right);
 if(front->left)
 q.push(front->left);
}
}

Ответ 13

Здесь нерекурсивный способ сделать это в Python с использованием очередей. Класс Queue может быть инициализирован так:

class Queue(object):
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop()

    def is_empty(self):
        return len(self.items) == 0

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def __len__(self):
        return self.size()

    def size(self):
        return len(self.items)

Класс, который представляет узел:

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.val = data

И вот метод, который выполняет основную задачу:

def mirror_tree_iterative(root):
    if root is None:
        return

    q = Queue()
    q.enqueue(root)

    while(not q.is_empty()):
        curr = q.peek()
        q.dequeue()
        curr.left, curr.right = curr.right, curr.left
        if curr.left:
            q.enqueue(curr.left)
        if curr.right:
            q.enqueue(curr.right)