二叉树交换法

发布于 2024-12-06 09:37:22 字数 848 浏览 0 评论 0原文

我在两个二叉树之间交换节点时遇到问题。

我试图将当前节点与树中传递的节点交换，但我不知道如何进行；我似乎只能交换节点的父节点，但不能交换节点本身。有人能给我一些指导吗？

    public void swap(Node node) {           
        if(this.equals(this.parent.leftChild)){
            Node tempNodeR = node.parent.rightChild;
            System.out.println("Is a left child");
            node.parent.rightChild = this.parent.leftChild;
            this.parent.leftChild = tempNodeR;
        }
        else{
            Node tempNodeL = node.parent.leftChild;
            System.out.println("Is a right child");
            node.parent.leftChild = this.parent.rightChild;
            this.parent.rightChild = tempNodeL;
        }        
    }

Calling node2.swap(node4):

Given Tree:
  1  3
 /    \
2      4

Resulting Tree (unchanged):
  1  3
 /    \
2      4

Expected Tree:
  1  3
 /    \
4      2

原文

I'm having trouble with swapping nodes between two binary trees.

I'm trying to swap the current node with the passed node in the tree, but I can't figure out how; I can only seem to swap the parents of the nodes, but not the nodes themselves.
Can anyone give me some direction?

    public void swap(Node node) {           
        if(this.equals(this.parent.leftChild)){
            Node tempNodeR = node.parent.rightChild;
            System.out.println("Is a left child");
            node.parent.rightChild = this.parent.leftChild;
            this.parent.leftChild = tempNodeR;
        }
        else{
            Node tempNodeL = node.parent.leftChild;
            System.out.println("Is a right child");
            node.parent.leftChild = this.parent.rightChild;
            this.parent.rightChild = tempNodeL;
        }        
    }

Calling node2.swap(node4):

Given Tree:
  1  3
 /    \
2      4

Resulting Tree (unchanged):
  1  3
 /    \
2      4

Expected Tree:
  1  3
 /    \
4      2

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

長街聽風 2024-12-13 09:37:22

对于每个节点，该节点都有对其父节点的引用，而父节点也有对该子节点的引用。因此，如果要交换两个节点，则需要更新四个引用。

Tree
  1  3
 /    \
2      4

所以这里...

1 有一个指向 2 的引用，而您想指向 4。2
有一个对 1 的引用，该引用应该指向 3。4
有一个对 3 的引用，该引用应该指向 1。3
有一个对4 应该指向 2。

希望有帮助。

For each node, the node has a reference to its parent and the parent has a reference to that child. So if you're going to swap two nodes, you need to update four references.