将一棵树转换为一棵以 p 为新根的新树

Question

实际问题是：

Write a program that takes as input a general tree T and a position p of T and converts T to another tree with the same set of position adjacencies, but now with p as its root.

我不确定位置邻接到底是什么意思，但据我了解，应该保持作为节点的父节点之间的关系。

但是如果一个节点被设为根节点，那么它们将不会具有相同的位置邻接关系。对于初学者，我想使用二叉树来实现这道题。

有人可以帮我解决我应该如何实施吗？

Answer 1

引用中使用了一些需要进一步定义的术语，但我会在这里尝试做一些假设：

...but now with p as its root.

这意味着作为输入给出的树是 so-called rooted 树，而不仅仅是 general 树，因为它一开始就说。重要的是要注意这一点，因为在图论中，树只是一个图，其中每对节点都由一条路径连接。根的概念只有在我们谈到有根树时才会出现。

...a position p of T...

这是一个不常见的术语。我假设 position 是图中通常称为 vertex 或 node 的同义词理论。

... position adjacencies

我假设这是指树的边。

... the relation between the parent as the nodes should be maintained.

如果你这样说，那么就不可能改变树，因为 parent-child 关系集唯一地定义了根树。所以我们必须假设这不是维护 parent-child 关系，而是维护两个顶点之间的关系，其中父节点的角色可能正在改变。

I would like to implement this question using a binary tree for starters.

这不是一个好主意：二叉树可能需要转换为 non-binary 树。例如，假设输入树是这个二叉树：

并且输入顶点是值为 2 的顶点。这意味着输出树将不是二叉树，而是：

               2
              /|\
             1 3 4

因此，我们有一个有根树和该树中的一个顶点作为输入，并且需要生成一个有根树作为输出，其根是给定的顶点。

算法

算法可以递归：

如果给定节点p（应该成为根节点）没有父节点，则无需更改：exit
解决以递归方式使父节点成为根节点的问题。完成后，p 的父级就没有父级了，因为 p 的父级已成为根。
从其父项中分离 p，并使该父项成为 p 的子项。所以这两个节点保持连接，但是 parent-child 的角色切换到 child-parent.

这是 JavaScript 中的一个实现。您可以运行示例图上的代码片段：

                  8
                 / \
                4   10
               /
              2  <-- to become new root
             / \
            1   3

结果树应该是：

class Node {
    constructor(value) {
        this.value = value;
        this.children = new Set; // any number of children
        this.parent = null;
    }
    addChild(node) {
        this.children.add(node);
        node.parent = this; // back reference
        return node;
    }
    detachFromParent() {
        if (this.parent != null) {
            this.parent.children.delete(this);
            this.parent = null;
        }
    }
    makeRoot() {
        let parent = this.parent; 
        if (parent != null) {
            parent.makeRoot();
            this.detachFromParent();
            this.addChild(parent);
        }
    }
    print(indent="") {
        console.log(indent + this.value);
        indent += "  ";
        for (const child of this.children) {
            child.print(indent);
        }
    }
}

// demo
let eight = new Node(8);
let ten = new Node(10);
let four = new Node(4);
let two = new Node(2);
let one = new Node(1);
let three = new Node(3);
eight.addChild(four);
eight.addChild(ten);
four.addChild(two);
two.addChild(one);
two.addChild(three);

console.log("input:");
eight.print();

console.log("change root to 2...");
two.makeRoot();
two.print();

将一棵树转换为一棵以 p 为新根的新树

Conversion of a tree to a new tree with p as its new root

tree

binary-tree

data-structures

算法