Spiegelbild eines binären Baum

Question

Angenommen, ich habe diesen Baum:

    1 
      2    3 
         4 5 

Dann wird das Spiegelbild sein wird:

    1 
      3    2 
     5  4 

Angenommen, die Knoten dieser Struktur sind:

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

Kann jemand einen Algorithmus dafür vorschlagen?

Answer 1

Klingt nach Hausaufgaben.

Es sieht sehr einfach aus. Schreiben Sie eine rekursive Routine, bei der die Tiefe zuerst jeden Knoten besucht und den Spiegelbaum mit umgekehrten Links und Rechtsformen erstellt.

Dies gibt einen neuen Baum zurück - einige andere Antworten tun dies. Hängt davon ab, was Ihre Aufgabe Sie gefragt :)

Answer 2

Banal Lösung zu tun:

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

Hier ist meine Funktion ist. wenn jede bessere Lösung schlagen:

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

Eine iterative Lösung:

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

rekursive Java-Code

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

Zeitkomplexität: O (n) Raum Komplexität: O (n)

Answer 11

rekursive und iterative Methoden in JAVA: 1) Rekursiv:

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

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

Nun, das ques hat viele answers.I ist Entsendung eine iterative Version bekommen Das ist ziemlich einfach zu verstehen. Dies verwendet Level Reihenfolge 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); 
} 
}