RK2015 RK2015 - 15 days ago 6
Java Question

Randomly Select a Node from N-ary Tree

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


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

}


How would I go about, after creating a tree, randomly select a node from said tree (root included). After selecting a random node from the tree, I need to be able to delete that node and replace it with a new subtree.

What would be the best way to do this? Thanks.

Answer

This replaces a random node in the tree with a new node:

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