[Java] 계층 구조 데이터에서 특정 노드 찾기

[Java] 계층 구조 데이터에서 특정 노드 찾기

 

 

계층 구조 이미지

 

계층 구조(Hierarchical Structure)는 요소들이 계층적인 관계를 가지고 구성된 구조를 의미한다. 이 구조에서는 상위 요소와 하위 요소 사이에 부모-자식 관계가 존재하며, 최상위에는 단일한 루트 요소가 있다. 예를 들어, 조직의 조직도는 계층 구조의 한 예이다. 조직도에서 최상위에는 회사 자체가 위치하고, 그 아래에는 부서, 부서 아래에 팀, 팀 아래 개인이 있을 것이다. 이러한 데이터를 관리할 때 특정 노드를 찾는 방법을 자바스크립트로 구현해보고자 한다. 전자제품에는 컴퓨터와 모바일 폰으로 구분되고 모바일 폰은 스마트 폰과 피쳐 폰으로 구분된다. 스마트폰 하위노드로 Android와 IOS가 있으며 새로운 JiurinieOS가 생겼다고 가정해보자. 우선 전자제품안에서 스마트폰을 찾고 스마트폰의 하위노드에 JiurinieOS를 추가해야 할 것이다. 

 

• 계층 구조 데이터

- Electronics
  - Computers
    - Laptops
    - Desktops
  - Mobile Phones
    - Smartphones
      - Android
      - iOS
    - Feature Phones

 

 

• Java 계층 구조 데이터 생성

import java.util.ArrayList;
import java.util.List;

class Node {
	private int id;
	private String label;
	private List<Node> nodes;

	public Node(int id, String label) {
		this.id = id;
		this.label = label;
		this.nodes = new ArrayList<>();
	}

	public void addNode(Node node) {
		nodes.add(node);
	}

	public int getId() {
		return id;
	}

	public String getLabel() {
		return label;
	}

	public List<Node> getNodes() {
		return nodes;
	}
}

public class Main {
	public static void main(String[] args) {
		Node node8 = new Node(8, "Android");
		Node node9 = new Node(9, "iOS");
		List<Node> smartphonesNodes = new ArrayList<>();
		smartphonesNodes.add(node8);
		smartphonesNodes.add(node9);
		Node smartphones = new Node(6, "Smartphones");
		smartphones.getNodes().addAll(smartphonesNodes);

		Node laptops = new Node(4, "Laptops");
		Node desktops = new Node(5, "Desktops");
		List<Node> computersNodes = new ArrayList<>();
		computersNodes.add(laptops);
		computersNodes.add(desktops);
		Node computers = new Node(2, "Computers");
		computers.getNodes().addAll(computersNodes);

		Node featurePhones = new Node(7, "Feature Phones");
		List<Node> mobilePhonesNodes = new ArrayList<>();
		mobilePhonesNodes.add(smartphones);
		mobilePhonesNodes.add(featurePhones);
		Node mobilePhones = new Node(3, "Mobile Phones");
		mobilePhones.getNodes().addAll(mobilePhonesNodes);

		Node electronics = new Node(1, "Electronics");
		electronics.getNodes().add(computers);
		electronics.getNodes().add(mobilePhones);
	}
}

 

 

• 계층 구조 데이터에서 노드를 찾는 과정
  
  1. 루트 노드에서 시작한다.
  2. 현재 노드에서 현재 노드와 자식 노드를 검사한다.
  3. 찾지 못한 경우 자식노드를 재귀적으로 수행한다.
  4. 원하는 노드를 찾으면 검색을 종료하며, 찾을 때까지 모든 노드를 검색하여 위 단계를 반복한다.

 

 

• Main.class

Java를 이용하여 계층 구조 데이터에서 특정 노드를 찾고, 해당 노드의 하위에 새로운 노드를 추가하는 코드를 작성해보았다. 재귀적으로 노드를 검색하는 findNode 메소드를 작성하여 노드 리스트와 목표값을 을 받아 해당 리스트에서 목표 값과 일치하는 노드를 찾는다.  만약 노드(Smartphones)를 찾으면 해당 노드를 반환 후 JiurinieOS를 추가하였으며, 노드를 찾지 못한 경우에는 null'를 반환한다.

import java.util.ArrayList;
import java.util.List;

class Node {
	private int id;
	private String label;
	private List<Node> nodes;

	public Node(int id, String label) {
		this.id = id;
		this.label = label;
		this.nodes = new ArrayList<>();
	}

	public void addNode(Node node) {
		nodes.add(node);
	}

	public int getId() {
		return id;
	}

	public String getLabel() {
		return label;
	}

	public List<Node> getNodes() {
		return nodes;
	}
}

public class Main {
	public static void main(String[] args) {
		Node node8 = new Node(8, "Android");
		Node node9 = new Node(9, "iOS");
		List<Node> smartphonesNodes = new ArrayList<>();
		smartphonesNodes.add(node8);
		smartphonesNodes.add(node9);
		Node smartphones = new Node(6, "Smartphones");
		smartphones.getNodes().addAll(smartphonesNodes);

		Node laptops = new Node(4, "Laptops");
		Node desktops = new Node(5, "Desktops");
		List<Node> computersNodes = new ArrayList<>();
		computersNodes.add(laptops);
		computersNodes.add(desktops);
		Node computers = new Node(2, "Computers");
		computers.getNodes().addAll(computersNodes);

		Node featurePhones = new Node(7, "Feature Phones");
		List<Node> mobilePhonesNodes = new ArrayList<>();
		mobilePhonesNodes.add(smartphones);
		mobilePhonesNodes.add(featurePhones);
		Node mobilePhones = new Node(3, "Mobile Phones");
		mobilePhones.getNodes().addAll(mobilePhonesNodes);

		Node electronics = new Node(1, "Electronics");
		electronics.getNodes().add(computers);
		electronics.getNodes().add(mobilePhones);

		List<Node> list = new ArrayList<>();
		list.add(electronics);

		
		// Smartphones 노드 검색
		Node node = findNode(list, 6);
		Node node10 = new Node(10, "JiurinieOS");
		node.addNode(node10);

		// 계층 구조 출력
		printHierarchy(electronics, 0);
	}

	public static void printHierarchy(Node node, int depth) {
		StringBuilder indentation = new StringBuilder();
		for (int i = 0; i < depth; i++) {
			indentation.append("  ");
		}
		System.out.println(indentation + "- " + node.getLabel());
		for (Node childNode : node.getNodes()) {
			printHierarchy(childNode, depth + 1);
		}
	}

	public static Node findNode(List<Node> nodes, int id) {
		for (Node node : nodes) {
			// 현재 노드가 찾는 값과 일치하면 현재 노드 반환
			if (node.getId() == id) {
				return node;
			}

			// 자식 노드 순회하며 재귀 검색
			if (node.getNodes() != null) {
				Node childNode = findNode(node.getNodes(), id);
				if (childNode != null) {
					return childNode; // 목표 노드를 찾은 경우 반환
				}
			}
		}

		return null; // 모든 노드를 검색 후 찾지 못한 경우 null 반환
	}
}