Предположим, что у меня есть это дерево:
1
2 3
4 5
Тогда зеркальное изображение будет:
1
3 2
5 4
Предположим, что узлы этой структуры:
struct node{
node left;
node right;
int value;
}
Может кто-нибудь предложить алгоритм для этого?
Звучит как домашнее задание.
Это выглядит очень легко. Напишите рекурсивную подпрограмму, которая сначала посещает каждую страницу 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;
}
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);
}
}
}
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);
}
}
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;
}
}
Вот моя функция. Если вы предлагаете лучшее решение:
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)
Ну, у этого вопроса есть много ответов. Я отправляю итеративную версию для этого, что довольно легко понять. Это использует 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);
}
}
Здесь нерекурсивный способ сделать это в 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)