Imagen de espejo de un árbol binario

Question

Supongamos que tengo este árbol:

    1 
      2    3 
         4 5 

A continuación, la imagen especular habrá:

    1 
      3    2 
     5  4 

asumir los nodos son de esta estructura:

struct node{ 
     node left; 
     node right; 
     int value; 
} 

¿Alguien puede sugerir un algoritmo para esto?

Answer 1

Suena como tarea.

Parece muy fácil. Escriba una rutina recursiva en la que la profundidad primero visita cada nodo y crea el árbol del espejo con la izquierda y la derecha invertidas.

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; 
    } 
} 

Esto devuelve un nuevo árbol - algunas otras respuestas hacen esto en su lugar. Depende de lo que su asignación se le pide que haga :)

Answer 2

solución banal:

for each node in tree 
    exchange leftchild with rightchild. 

Answer 3

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); 

Answer 4

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; 
    } 
} 

Answer 5

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); 
    } 
} 

Answer 6

Aquí es mi función. No sugerir si cualquier solución mejor:

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); 
} 

Answer 7

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; 
    } 
} 

Answer 8

Una solución iterativa:

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); 
     } 
    } 
} 

Answer 9

recursiva del código de 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; 

} 
} 

Answer 10

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; 
} 

Complejidad de tiempo: O (n) Espacial complejidad: O (n)

Answer 11

métodos recursivos e iterativos en Java: 1) recursivas:

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) iterativos:

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; 
} 

Answer 12

Pues bien, este ques ha conseguido una gran cantidad de answers.I de Publicación de una versión iterativa para esto, que es bastante fácil de entender. Esto usa el orden de nivel Transversal.

//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); 
} 
}