从 N 叉树中随机 Select 个节点

Question

我的节点Class:

import java.util.ArrayList;

public class Tree<T> {

    private Node<T> root;

    public Tree(Node<T> root) {
        this.root = root;
    }

    public boolean isEmpty() {
        return (root == null) ? true : false;
    }

    public Node<T> getRoot() {
        return root;
    }

    public void setRoot(Node<T> root) {
        this.root = root;
    }

    public boolean exists(T key) {
        return find(root, key);
    }

    public int getNumberOfNodes() {
        return getNumberOfDescendants(root) + 1;
    }

    public int getNumberOfDescendants(Node<T> node) {
        int n = node.getChildren().size();
        for (Node<T> child : node.getChildren())
            n += getNumberOfDescendants(child);

        return n;

    }

    private boolean find(Node<T> node, T keyNode) {
        boolean res = false;
        if (node.getData().equals(keyNode))
            return true;

        else {
            for (Node<T> child : node.getChildren())
                if (find(child, keyNode))
                    res = true;
        }

        return res;
    }

    private Node<T> findNode(Node<T> node, T keyNode)
    {
        if(node == null)
            return null;
        if(node.getData().equals(keyNode))
            return node;
        else
        {
            Node<T> cnode = null;
            for (Node<T> child : node.getChildren())
                if ((cnode = findNode(child, keyNode)) != null)
                    return cnode;
        }
        return null;         
    } 

    public ArrayList<Node<T>> getPreOrderTraversal() {
        ArrayList<Node<T>> preOrder = new ArrayList<Node<T>>();
        buildPreOrder(root, preOrder);
        return preOrder;
    }

    public ArrayList<Node<T>> getPostOrderTraversal() {
        ArrayList<Node<T>> postOrder = new ArrayList<Node<T>>();
        buildPostOrder(root, postOrder);
        return postOrder;
    }

    private void buildPreOrder(Node<T> node, ArrayList<Node<T>> preOrder) {
        preOrder.add(node);
        for (Node<T> child : node.getChildren()) {
            buildPreOrder(child, preOrder);
        }
    }

    private void buildPostOrder(Node<T> node, ArrayList<Node<T>> postOrder) {
        for (Node<T> child : node.getChildren()) {
            buildPostOrder(child, postOrder);
        }
        postOrder.add(node);
    }

    public ArrayList<Node<T>> getLongestPathFromRootToAnyLeaf() {
        ArrayList<Node<T>> longestPath = null;
        int max = 0;
        for (ArrayList<Node<T>> path : getPathsFromRootToAnyLeaf()) {
            if (path.size() > max) {
                max = path.size();
                longestPath = path;
            }
        }
        return longestPath;
    }

    public int getMaxDepth()
    {
        return getLongestPathFromRootToAnyLeaf().size();
    }

    public ArrayList<ArrayList<Node<T>>> getPathsFromRootToAnyLeaf() {
        ArrayList<ArrayList<Node<T>>> paths = new ArrayList<ArrayList<Node<T>>>();
        ArrayList<Node<T>> currentPath = new ArrayList<Node<T>>();
        getPath(root, currentPath, paths);

        return paths;
    }

    private void getPath(Node<T> node, ArrayList<Node<T>> currentPath,
            ArrayList<ArrayList<Node<T>>> paths) {
        if (currentPath == null)
            return;

        currentPath.add(node);

        if (node.getChildren().size() == 0) {
            // This is a leaf
            paths.add(clone(currentPath));
        }
        for (Node<T> child : node.getChildren())
            getPath(child, currentPath, paths);

        int index = currentPath.indexOf(node);
        for (int i = index; i < currentPath.size(); i++)
            currentPath.remove(index);
    }

    private ArrayList<Node<T>> clone(ArrayList<Node<T>> list) {
        ArrayList<Node<T>> newList = new ArrayList<Node<T>>();
        for (Node<T> node : list)
            newList.add(new Node<T>(node));

        return newList;
    }
}

我的树Class:

import java.util.ArrayList;
import java.util.List;

public class Node<T> {
    private T data;
    private List<Node<T>> children;
    private Node<T> parent;

    public Node(T data) {
        this.data = data;
        this.children = new ArrayList<Node<T>>();
    }

    public Node(Node<T> node) {
        this.data = (T) node.getData();
        children = new ArrayList<Node<T>>();
    }

    public void addChild(Node<T> child) {
        child.setParent(this);
        children.add(child);
    }

    public void addChildAt(int index, Node<T> child) {
        child.setParent(this);
        this.children.add(index, child);
    }

    public void setChildren(List<Node<T>> children) {
        for (Node<T> child : children)
            child.setParent(this);

        this.children = children;
    }

    public void removeChildren() {
        this.children.clear();
    }

    public Node<T> removeChildAt(int index) {
        return children.remove(index);
    }


    public void removeThisIfItsAChild(Node<T> childToBeDeleted)
    {
        List <Node<T>> list = getChildren();
        list.remove(childToBeDeleted);
    }

    public T getData() {
        return this.data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getParent() {
        return this.parent;
    }

    public void setParent(Node<T> parent) {
        this.parent = parent;
    }

    public List<Node<T>> getChildren() {
        return this.children;
    }

    public Node<T> getChildAt(int index) {
        return children.get(index);
    }

    @Override
    public boolean equals(Object obj) {
        if (null == obj)
            return false;

        if (obj instanceof Node) {
            if (((Node<?>) obj).getData().equals(this.data))
                return true;
        }

        return false;
    }

    @Override
    public String toString() {
        return this.data.toString();
    }

}

在创建树之后，我将如何着手从所述树（包括根）中随机 select 一个节点。 select从树中随机选择一个节点后，我需要能够删除该节点并将其替换为新的子树。

最好的方法是什么？谢谢

Answer 1

这将用新节点替换树中的随机节点：

public static void replaceRandom(Tree<T> tree, Node<T> newNode) { 
  // Find a random node
  List<Node<T>> nodeList = tree.getPreOrderTraversal();
  int globalIndex = (int) (Math.random() * nodeList.size());
  Node<T> old = nodeList.get(globalIndex);

  if (old.isRoot()) {
    // If it is the root, we just replace the root.
    tree.setRoot(newNode);
  } else {
    // Otherwise, we need to find the local index to replace it.
    Node<T> parent = old.getParent();
    int localIndex = parent.getChildren().indexOf(old);
    parent.removeChildAt(localIndex);
    parent.addChildAt(localIndex, newNode);
  }
}

Answer 2

从树中寻找一个随机节点：遍历树（使用 bfs 或 dfs 遍历）并在访问每个节点时使用 rand 函数。对 rand 函数可以 return 的值进行一些限制，同时记住树的节点数，以便选择每个节点的可能性相同。

从 N 叉树中随机 Select 个节点

Randomly Select a Node from N-ary Tree

java

algorithm

tree

nodes