Is it possible to design a tree where nodes have infinitely many children?

Question

How can design a tree with lots (infinite number) of branches ?

Which data structure we should use to store child nodes ?

Answer 1

You can't actually store infinitely many children, since that won't fit into memory. However, you can store unboundedly many children - that is, you can make trees where each node can have any number of children with no fixed upper bound.

There are a few standard ways to do this. You could have each tree node store a list of all of its children (perhaps as a dynamic array or a linked list), which is often done with tries. For example, in C++, you might have something like this:

struct Node {
   /* ... Data for the node goes here ... */
   std::vector<Node*> children;
};

Alternatively, you could use the left-child/right-sibling representation, which represents a multiway tree as a binary tree. This is often used in priority queues like binomial heaps. For example:

struct Node {
    /* ... data for the node ... */
    Node* firstChild;
    Node* nextSibling;
};

Hope this helps!

Answer 2

Yes! You can create a structure where children are materialized on demand (i.e. "lazy children"). In this case, the number of children can easily be functionally infinite.

Haskell is great for creating "functionally infinite" data structures, but since I don't know a whit of Haskell, here's a Python example instead:

class InfiniteTreeNode:
    ''' abstract base class for a tree node that has effectively infinite children '''
    def __init__(self, data):
        self.data = data
    def getChild(self, n):
        raise NotImplementedError

class PrimeSumNode(InfiniteTreeNode):
    def getChild(self, n):
        prime = getNthPrime(n) # hypothetical function to get the nth prime number
        return PrimeSumNode(self.data + prime)

prime_root = PrimeSumNode(0)
print prime_root.getChild(3).getChild(4).data # would print 18: the 4th prime is 7 and the 5th prime is 11

Now, if you were to do a search of PrimeSumNode down to a depth of 2, you could find all the numbers that are sums of two primes (and if you can prove that this contains all even integers, you can win a big mathematical prize!).

Answer 3

Something like this

Node {
  public String name;
  Node n[]; 
}

Add nodes like so

public Node[] add_subnode(Node n[]) {
    for (int i=0; i<n.length; i++) {
        n[i] = new Node();
        p("\n Enter name: ");
        n[i].name = sc.next();

        p("\n How many children for "+n[i].name+"?");
        int children = sc.nextInt();

        if (children > 0) {
            Node x[] = new Node[children];
            n[i].n = add_subnode(x);
        }
    }
    return n;
}

Full working code:

class People {
  private Scanner sc;
  public People(Scanner sc) {
    this.sc = sc;
  }
public void main_thing() {
    Node head = new Node();
    head.name = "Head";
    p("\n How many nodes do you want to add to Head: ");
    int nodes = sc.nextInt();

    head.n = new Node[nodes];
    Node[] n = add_subnode(head.n);

    print_nodes(head.n);

}

public Node[] add_subnode(Node n[]) {
    for (int i=0; i<n.length; i++) {
        n[i] = new Node();
        p("\n Enter name: ");
        n[i].name = sc.next();

        p("\n How many children for "+n[i].name+"?");
        int children = sc.nextInt();

        if (children > 0) {
            Node x[] = new Node[children];
            n[i].n = add_subnode(x);
        }
    }
    return n;
}

public void print_nodes(Node n[]) {
    if (n!=null && n.length > 0) {
    for (int i=0; i<n.length; i++) {
        p("\n "+n[i].name);
        print_nodes(n[i].n);
    }
    }
}

public static void p(String msg) {
    System.out.print(msg);
}
}

class Node {
    public String name;
    Node n[]; 
}

Answer 4

I recommend you to use a Node class with a left child Node and right child Node and a parent Node.

   public class Node
   {      
      Node<T>  parent;      
      Node<T>  leftChild;  
      Node<T>  rightChild;  
      T          value;       


      Node(T val)
      {
         value = val;
         leftChild = new Node<T>();
         leftChild.parent = this;
         rightChild = new Node<T>();
         rightChild.parent = this;
      }

You can set grand father and uncle and sibling like this.

  Node<T> grandParent()
  {
     if(this.parent.parent != null)
     {
         return this.parent.parent;
     }
     else
         return null;
  }


  Node<T> uncle()
  {
      if(this.grandParent() != null)
      {
          if(this.parent == this.grandParent().rightChild)
          {
              return this.grandParent().leftChild;
          }
          else
          {
              return this.grandParent().rightChild;
          }
      }
      else
          return null;

  }

  Node<T> sibling()
  {
      if(this.parent != null)
      {
          if(this == this.parent.rightChild)
          {
              return this.parent.leftChild;
          }
          else
          {
              return this.parent.rightChild;
          }
      }
      else
          return null;
  }

And is impossible to have infinite child, at least you have infinite memory.

good luck !

Hope this will help you.