Java에서 트리 구현
이 튜토리얼에서는 Java에서 트리 구조를 만드는 두 가지 방법을 볼 것입니다. 트리 구조는 폴더 및 파일 이름의 디렉토리를 만드는 것과 같은 여러 가지 방법으로 유용할 수 있습니다.
재귀 방법을 사용하여 트리 구현
이 예제에서 우리는 최대 두 개의 자식을 가진 이진 트리를 만듭니다. 하나는 왼쪽에, 다른 하나는 오른쪽에 있습니다. 루트 노드는 모든 자식 노드의 부모입니다. 각 노드는 값을 저장합니다. 아래에서 우리는 두 가지 수업을 듣습니다. 하나는 트리의 노드를 나타내는 Node이고 다른 하나는 노드에서 작업을 수행하는 JavaTree 클래스입니다.
Node 클래스에는 세 개의 변수가 있습니다. 첫 번째는 int 데이터 유형의 노드에 저장할 값입니다. 그런 다음 left 및 right 자식 노드에 대해 두 개의 변수를 사용합니다. 두 변수 모두 Node 유형입니다. Node 클래스의 생성자를 만들고 매개변수에서 value를 초기화합니다. 왼쪽 및 오른쪽 변수는 null로 설정됩니다.
JavaTree 클래스에서 Node 유형의 변수를 가져와 root라고 합니다. 그런 다음 Node를 매개변수로 사용하는 traverseRecursionTree() 메서드를 만들고 메서드 내부에서 node가 null인지 확인합니다. 그렇지 않은 경우 traverseRecursionTree() 메소드를 자체적으로 호출하고 node의 left 부분을 전달합니다. 그런 다음 node의 value를 인쇄하고 자체에서 메서드를 다시 호출하고 right node를 전달합니다. 자체에서 함수를 호출하는 프로세스를 재귀라고 합니다.
main() 메소드에서 javaTree의 객체를 생성하고 루트, 루트의 왼쪽 자식, 오른쪽 자식과 같은 모든 변수를 초기화합니다. 우리는 또한 루트의 자식의 왼쪽 자식을 만듭니다. 모든 자식을 포함하는 javaTree.root를 사용하여 전체 트리를 인쇄합니다.
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
left = null;
right = null;
}
}
public class JavaTree {
Node root;
public void traverseRecursionTree(Node node) {
if (node != null) {
traverseRecursionTree(node.left);
System.out.print(" " + node.value);
traverseRecursionTree(node.right);
}
}
public static void main(String[] args) {
JavaTree javaTree = new JavaTree();
javaTree.root = new Node(10);
javaTree.root.left = new Node(6);
javaTree.root.right = new Node(5);
javaTree.root.left.left = new Node(3);
System.out.print("Binary Tree: ");
javaTree.traverseRecursionTree(javaTree.root);
}
}
출력:
Binary Tree: 3 6 10 5
Generic Method 및 ArrayList를 사용하여 Java에서 트리 만들기
이전 방법에서는 int 노드의 값으로 한 가지 유형의 데이터로만 제한되었습니다. 이 프로그램에서 우리는 우리가 선택한 모든 데이터 유형을 사용할 수 있는 일반 방법을 사용합니다. Node<T> 클래스가 있습니다. 여기 <T>는 모든 데이터 유형을 문자열로 사용할 수 있음을 알려줍니다. 클래스에서 세 개의 변수를 선언합니다. 첫 번째는 T 유형의 루트, 다음은 Node<T> 유형의 parent, 마지막으로 Node<T>라는 이름의 ArrayList가 child입니다.
Node의 생성자에서 T 유형의 root를 가져와 클래스 변수 root로 설정합니다. 그런 다음 children ArrayList를 초기화합니다. 이제 parent에 자식을 추가하기 위해 T 유형의 child를 취하는 addChild() 함수를 만듭니다. addChild() 함수에서 Node<T> - childNode의 개체를 만들고 this 키워드를 사용하여 부모 컨텍스트를 현재 클래스의 컨텍스트로 설정합니다. 다음으로 children ArrayList를 가져와 childNode를 추가하고 childNode를 반환합니다.
Node<T> 클래스에는 root를 반환하는 getRoot() 메서드와 같은 작업을 수행하는 데 사용할 수 있는 여러 메서드가 있습니다. isRoot() 함수는 현재 노드가 root. 트리의 노드 수준을 반환하는 getLevel() 함수를 만듭니다. 마지막으로 toString() 메서드를 재정의하여 null이 아닌 경우 전체 트리를 반환합니다.
이제 main() 메소드가 있는 Javatree 클래스를 생성합니다. 클래스에서 Node<String>의 x와 y를 생성합니다. 여기서는 String을 유형으로 사용합니다. 두 생성자 모두에서 각 트리의 루트를 전달합니다. getRoot()를 사용하여 root를 인쇄한 다음 child1이라는 Node<String>의 개체를 만들고 x 개체를 사용하여 addChild() 메서드를 호출합니다. 여기에서 값을 전달합니다. child1을 인수로 사용합니다. child1 블록에서 객체를 사용하여 child1의 세 자식을 만들고 addChild()를 호출합니다.
동일한 프로세스를 사용하여 child2라는 이름의 다른 트리를 만듭니다.
import java.util.ArrayList;
class Node<T> {
private final T root;
private Node<T> parent;
private final ArrayList<Node<T>> children;
public Node(T root) {
this.root = root;
children = new ArrayList<>();
}
public Node<T> addChild(T child) {
Node<T> childNode = new Node<T>(child);
childNode.parent = this;
this.children.add(childNode);
return childNode;
}
public T getRoot() {
return root;
}
public boolean isRoot() {
return parent == null;
}
public boolean isLeaf() {
return children.size() == 0;
}
public int getLevel() {
if (this.isRoot())
return 0;
else
return parent.getLevel() + 1;
}
@Override
public String toString() {
return root != null ? root.toString() : "null";
}
}
public class JavaTree {
public static void main(String[] args) {
Node<String> x = new Node<String>("parent1");
Node<String> y = new Node<String>("parent2");
System.out.println(x.getRoot());
Node<String> child1 = x.addChild("child1");
{
Node<String> innerChild1 = child1.addChild("innerChild1OfChild1");
Node<String> innerChild2 = child1.addChild("innerChild2OfChild1");
Node<String> innerChild3 = child1.addChild("innerChild3OfChild1");
System.out.println("-" + child1);
System.out.println("--" + innerChild1);
System.out.println("--" + innerChild2);
System.out.println("--" + innerChild3);
System.out.println("Level of child1: " + child1.getLevel());
System.out.println("Level of innerChild2 in Child1: " + innerChild2.getLevel());
}
System.out.println();
System.out.println(y.getRoot());
Node<String> child2 = x.addChild("child2");
{
Node<String> innerChild1 = child2.addChild("innerChild2OfChild2");
Node<String> innerChild2 = child2.addChild("innerChild3OfChild2");
Node<String> innerChild3 = child2.addChild("innerChild4OfChild2");
{
Node<String> innerChild4 = innerChild3.addChild("innerChild4OfChild3");
System.out.println(innerChild4.getLevel());
System.out.println("\nIs inner Child4 Leaf? " + innerChild4.isLeaf());
}
System.out.println("-" + child2);
System.out.println("--" + innerChild1);
System.out.println("--" + innerChild2);
System.out.println("--" + innerChild3);
System.out.println("Level of child1: " + child2.getLevel());
System.out.println("Level of innerChild2 in Child2: " + innerChild2.getLevel());
}
}
}
출력:
parent1
-child1
--innerChild1OfChild1
--innerChild2OfChild1
--innerChild3OfChild1
Level of child1: 1
Level of innerChild2 in Child1: 2
parent2
3
Is inner Child4 Leaf? true
-child2
--innerChild2OfChild2
--innerChild3OfChild2
--innerChild4OfChild2
Level of child1: 1
Level of innerChild2 in Child2: 2
Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.
LinkedIn