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

Question

Предположим, что у меня есть это дерево:

    1 
      2    3 
         4 5 

Затем зеркальное изображение будет:

    1 
      3    2 
     5  4 

Предположим, что узлы этой структуры:

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

Может кто-нибудь предложить алгоритм для этого?

Answer 1

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

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

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

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

Answer 2

банальные решения:

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

Вот моя функция. Как предполагает, если какое-либо лучшее решение:

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

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

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

Рекурсивного 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; 
} 

Временной сложность: O (п) Space сложность: O (n)

Answer 11

рекурсивные и итеративные методы в 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; 
} 

Answer 12

Ну, это Ques имеет много answers.I я разместить итеративный версия для этого, что довольно легко понять. Это использует 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); 
} 
}