隨機選擇從N叉樹

Question

我的節點類節點：

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

我的樹類：

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

} 

我怎麼會去，創建一棵樹後，隨機選擇從節點說樹（包括根）。從樹中選擇一個隨機節點後，我需要能夠刪除該節點並將其替換爲新的子樹。

這樣做的最好方法是什麼？謝謝。

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函數可以返回的值給予一些約束，同時考慮到樹的節點數量，因此選擇每個節點的可能性將相同。