Tree data structure implementation
There is no need to import a Java package for implementing Trees. Tree structure is a collection of nodes/instance of a class referencing to the address of the child nodes. Although, there are different types of trees like Binary Search Tree or AVL Trees, however each tree has separate property.
Sample Implementation of Binary Search Tree in Java is as follows:
/* Node Class containing left and right child of current
node and key value*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
class Tree
{
Node root;
Tree()
{
root = null;
}
public static void main(String[] args)
{
Tree tree = new Tree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
}
}
Tree implementation in Java (root, parents and children)
import java.util.ArrayList;
import java.util.List;
public class Node<T> {
private List<Node<T>> children = new ArrayList<Node<T>>();
private Node<T> parent = null;
private T data = null;
public Node(T data) {
this.data = data;
}
public Node(T data, Node<T> parent) {
this.data = data;
this.parent = parent;
}
public List<Node<T>> getChildren() {
return children;
}
public void setParent(Node<T> parent) {
parent.addChild(this);
this.parent = parent;
}
public void addChild(T data) {
Node<T> child = new Node<T>(data);
child.setParent(this);
this.children.add(child);
}
public void addChild(Node<T> child) {
child.setParent(this);
this.children.add(child);
}
public T getData() {
return this.data;
}
public void setData(T data) {
this.data = data;
}
public boolean isRoot() {
return (this.parent == null);
}
public boolean isLeaf() {
return this.children.size == 0;
}
public void removeParent() {
this.parent = null;
}
}
Example:
import java.util.List;
Node<String> parentNode = new Node<String>("Parent");
Node<String> childNode1 = new Node<String>("Child 1", parentNode);
Node<String> childNode2 = new Node<String>("Child 2");
childNode2.setParent(parentNode);
Node<String> grandchildNode = new Node<String>("Grandchild of parentNode. Child of childNode1", childNode1);
List<Node<String>> childrenNodes = parentNode.getChildren();
Java - tree data structure with multiple nodes - how to search efficiently
You need two things for this:
In your Node object, have a reference to the parent node as well:
class Node{
String label;
List<Node> children;
Node parent;
}
Create a HashMap that maps labels to the nodes:
HashMap<String, Node> labelsToNodes;
Then searching is done with the get() method in the HashMap. You get your category list by repeatedly getting the parent nodes. Let me know if you'd like the code for this and I'll add it (I'm short on time right now).
Related Topics
What Is a Nosuchbeandefinitionexception and How to Fix It
What Do ^ and $ Mean in a Regular Expression
Avoid Synchronized(This) in Java
String Is Immutable. What Exactly Is the Meaning
Declaring Variables Inside or Outside of a Loop
Java Error: Comparison Method Violates Its General Contract
How to Check If a String Contains Another String in a Case Insensitive Manner in Java
How to Send an Email by Java Application Using Gmail, Yahoo, or Hotmail
Wait For Page Load in Selenium
Catching Java.Lang.Outofmemoryerror
Compare Two Objects With .Equals() and == Operator
How Many Ways to Click on Webelement in Webdriver
How to Add to List≪? Extends Number≫ Data Structures
Junit Test For System.Out.Println()
Get Generic Type of Java.Util.List
Swing: Link Toggle Buttons Together With a Button Group, Along With Corresponding Menu Items