代码之家 › 专栏 › 技术社区 › Peter Lee

如何有效地查找二叉树中给定节点(或项)的镜像节点

mirror binary-tree

Peter Lee · 技术社区 · 15 年前

我一直在考虑这个问题,但我没有找到一个好的、有效的解决方案。

如何在二叉树中查找给定节点(或项)的镜像节点?

// Node definition
struct _Node {
    char data;
    struct _Node* left;
    struct _Node* right;
} Node;

// Assumption:
//     "given" is guaranteed in the binary tree ("root" which is not NULL)
Node* FindMirrorNode(Node* root, Node* given)
{
     // Implementation here
}

// OR: 

// Assumption:
//    in the binary tree ("root"), there is no repeated items, which mean in each node the char data is unique;
//   The char "given" is guaranteed in the binary tree.
char FindMirrorNodeData(Node* root, char given)
{
    // Implementation here
}

注:我不是在问如何找到给定树的镜像树:—)

For example, considering the tree below
              A
          /      \
       B             C
      /            /   \
    D             E     F
     \           / \
      G         H   I

The mirror node of 'D' is node 'F'; while the mirror node of 'G' is NULL.

谢谢。

2 回复 | 直到 15 年前

Kru 15 年前

我已经为函数编写了一个解决方案, char . 是 FindMirrorNode(r, n) == FindMirrorNodeData(r, n->data) ?

在将镜像节点保持在堆栈上的同时,必须遍历整个树来搜索给定的数据。这是一个非常简单的解决方案,仍然非常有效。如果需要,可以将尾调用转换为 while .

static Node* FindMirrorNodeRec(char given, Node* left, Node* right)
{
    // if either node is NULL then there is no mirror node
    if (left == NULL || right == NULL)
        return NULL;
    // check the current candidates
    if (given == left->data)
        return right;
    if (given == right->data)
        return left;
    // try recursively
    // (first external then internal nodes)
    Node* res = FindMirrorNodeRec(given, left->left, right->right);
    if (res != NULL)
        return res;
    return FindMirrorNodeRec(given, left->right, right->left);
}

Node* FindMirrorNodeData(Node* root, char given)
{
    if (root == NULL)
        return NULL;
    if (given == root->data)
        return root;
    // call the search function
    return FindMirrorNodeRec(given, root->left, root->right);
}

Peter Lee 15 年前

感谢克里斯的完美解决方案。它奏效了。

Node* FindMirrorNodeRec(Node* given, Node* left, Node* right)
{
    // There is no mirror node if either node is NULL
    if (!left || !right)
        return NULL;

    // Check the left and right
    if (given == left)
        return right;
    if (given == right)
        return left;

    // Try recursively (first external and then internal)
    Node* mir = FindMirrorNodeRec(given, left->left, right->right);
    if (mir)
        return mir;

    // Internally
    return FindMirrorNodeRec(given, left->right, right->left);
}

// Find the mirror node of the given node
// Assumption: root is not NULL, and the given node is guaranteed
//             in the tree (of course, not NULL :-)
Node* FindMirrorNode(Node* const root, Node* const given)
{
    if (!root || root == given)
        return root;

    return FindMirrorNodeRec(given, root->left, root->right);
}