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

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

1
 2 3
 4 5

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

1
 3 2
 5 4

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

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

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

12 ответов

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

Это выглядит очень легко. Напишите рекурсивную подпрограмму, которая сначала посещает каждую страницу 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;
 }
}

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


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


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

for each node in tree
 exchange leftchild with rightchild.


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


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


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

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


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


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


Ну, у этого вопроса есть много ответов. Я отправляю итеративную версию для этого, что довольно легко понять. Это использует 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);
}
}
</treenode*></treenode*>


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

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


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


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)

licensed under cc by-sa 3.0 with attribution.