一二进制树的镜像 [英] Mirror image of a binary tree

问题描述

假设我有这样的树：

                   1
           2             3
                        4  5

然后镜像将是：

Then the mirror image will be:

                   1
           3               2
        5     4

假定节点是这个结构的

Assume the nodes are of this structure:

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

有人能提出一个算法呢？

Can someone suggest an algorithm for this?

推荐答案

听起来像是功课。

这看起来很容易。编写递归例程深度优先访问的每一个节点，并建立镜像树左右颠倒。

It looks very easy. Write a recursive routine that depth-first visits every node and builds the mirror tree with left and right reversed.

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

这会返回一个新的树 - 一些其他的答案做到这一点的地方。取决于你的任务要求你做:)

This returns a new tree - some other answers do this in place. Depends on what your assignment asked you to do :)

这篇关于一二进制树的镜像的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！