트리 순회 Java

자바 트리 순회(Java tree traversal)는 자바 프로그래밍 언어로 구현된 알고리즘으로 정의되며, 트리를 데이터 구조로 구성하고 알고리즘 구현을 통해 트리의 모든 노드를 방문하는 기본 기능을 통합합니다. 컴퓨터 과학 데이터 구조 용어에서 순회는 더 큰 작업을 완료하기 위해 데이터 구조의 모든 노드를 방문해야 함을 의미합니다. 트리의 구성 요소는 루트 및 하위 노드이며, 그 중 일부는 해당 특정 노드에서 끝나고 리프로 명명되고 나머지는 더 많은 하위 트리를 생성합니다. 이 기사에서는 Java에서 트리 순회 구현을 살펴보고 이를 달성할 수 있는 다양한 방법을 살펴보겠습니다.

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

구문

Java 클래스 선언:

class <class name> {
// List the fields (variables) for the class
// Define the methods of the class to perform the specified operations
}

Java에서 메소드 정의:

returnType <method name>() {
// Body of the method that constitutes the steps that will fulfill the assigned task
}

Java에서 노드 선언:

Node<{ Data Type }> <variable name> = new Node<{ Data Type }>(" <Value>");
Access the left of the node in Java:
<variable name>.left

Java에서 노드의 오른쪽에 액세스:

<variable name>.right

Java에서 트리 순회를 수행하는 방법은 무엇입니까?

Java에서 트리를 탐색하는 다양한 방법을 논의하기 전에 먼저 트리가 어떻게 구성되어 있는지 알아야 합니다. 트리는 Java에서 클래스로 트리를 구축하는 데 필수적인 구성 요소 중 하나이기 때문입니다. 트리에는 노드가 있으므로 노드 클래스를 정의합니다. 이 클래스에는 노드의 데이터를 나타내는 데이터, 노드의 왼쪽을 가리키는 왼쪽 포인터, 노드의 오른쪽을 가리키는 또 다른 포인터인 필드가 있습니다. 이 모든 필드는 Node 클래스를 구성합니다. 다음은 나무가 어떻게 생겼는지에 대한 도식입니다.

노드와 포인터를 구성하는 트리 클래스를 정의했으면 이제 Java에서 구현되고 각각 고유한 순회 시그니처를 갖는 3가지 유형의 순회를 살펴보겠습니다.

1개의 순회

이 순회가 정의되는 방식은 왼쪽 하위 트리의 요소를 방문한 다음 하위 트리의 노드를 방문한 다음 마지막으로 오른쪽 하위 트리를 순회하는 것입니다. 의사코드는 다음과 같습니다.

• 노드가 null에 도달할 때까지 왼쪽 노드를 전달하여 함수를 재귀적으로 호출합니다.
• 데이터 표시
• 노드가 null에 도달할 때까지 올바른 노드를 전달하여 함수를 재귀적으로 호출합니다.

순차 알고리즘의 순회 경로는 노드 1.1→노드 1→노드 1.2→루트→노드 2입니다.

2. 선주문 순회

이 순회가 정의되는 방식은 루트 노드의 요소를 방문하고 왼쪽 하위 트리를 순회한 다음 마지막으로 오른쪽 하위 트리를 순회하는 것입니다. 의사코드는 다음과 같습니다.

• 루트 노드를 먼저 탐색하세요.
• 노드가 null에 도달할 때까지 왼쪽 노드를 전달하여 함수를 재귀적으로 호출합니다.
• 노드가 null에 도달할 때까지 올바른 노드를 전달하여 함수를 재귀적으로 호출합니다.

선주문 알고리즘의 순회 경로는 루트→노드 1→노드 1.1→노드 1.2→노드 2입니다.

3. 사후순회

이 순회가 정의되는 방식은 왼쪽 하위 트리의 요소를 방문한 다음 오른쪽 하위 트리를 방문하고 마지막으로 기본 노드에 도달할 때까지 하위 트리의 노드를 순회하는 것입니다. 의사코드는 다음과 같습니다.

• 노드가 null에 도달할 때까지 왼쪽 노드를 전달하여 함수를 재귀적으로 호출합니다.
• 노드가 null에 도달할 때까지 올바른 노드를 전달하여 함수를 재귀적으로 호출합니다.
• 데이터 표시

후위 알고리즘의 순회 경로는 노드 1.1→노드 1.2→노드 1→노드 2→루트입니다.

트리 순회 Java의 예

아래는 트리 순회 Java의 예입니다.

예시 #1

재귀를 이용한 순회 순서

구문

class NodeClass {
int value;
NodeClass left, right;
public NodeClass(int key) {
value = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void inOrderFunc(NodeClass node) {
if (node == null)
return;
inOrderFunc(node.left);
System.out.print(node.value + "->");
inOrderFunc(node.right);
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
System.out.println("In Order traversal");
tree.inOrderFunc(tree.base);
}
}

출력:

예시 #2

재귀를 이용한 선주문 순회

구문

class NodeClass {
int item;
NodeClass left, right;
public NodeClass(int key) {
item = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void preorderFunc(NodeClass node) {
if (node == null)
return;
//First the node:
System.out.print(node.item + "->");
//Recursively look at the left side of the tree
preorderFunc(node.left);
//Recursively look at the right side of the tree
preorderFunc(node.right);
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
// preorderFunc tree traversal
System.out.println("Preorder traversal: ");
tree.preorderFunc(tree.base);
}
}

출력:

예시 #3

재귀를 통한 후순 순회

구문

class NodeClass {
int item;
NodeClass left, right;
public NodeClass(int key) {
item = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void postorderFunc(NodeClass node) {
if (node == null)
return;
postorderFunc(node.left);
postorderFunc(node.right);
System.out.print(node.item + "->");
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
System.out.println("Postorder traversal: ");
tree.postorderFunc(tree.base);
}
}

출력:

결론

이 기사에서는 실제 사례와 함께 Java에서 트리 순회를 구현하는 다양한 방법을 모두 살펴보았습니다. 독자들은 코드에 더 많은 노드를 추가하고 순회 결과를 확인하여 순회를 살펴보는 것이 좋습니다!

위 내용은 트리 순회 Java의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!