트리(tree)

 

트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

트리에서 최상위 노드를 루트 노드(root node 뿌리 노드)라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

트리를 간단히 자바 코드로 구현하면 아래와 같이 구현이 가능하다.

 

	public static class Tree {
		int count;

		public Tree() {
			count = 0;
		}

		public class Node {
			Object data;
			Node left;
			Node right;

			public Node(Object data) {
				this.data = data;
				left = null;
				right = null;
			}

			public void addLeft(Node node) {
				left = node;
				count++;
			}

			public void addRight(Node node) {
				right = node;
				count++;
			}

			public void deleteLeft() {
				left = null;
				count--;
			}

			public void deleteRight() {
				right = null;
				count--;
			}
		}

		public Node addNode(Object data) {
			Node n = new Node(data);
			return n;
		}

		public void preOrder(Node node) {
			if (node == null) {
				return;
			}

			System.out.print(node.data + " ");
			preOrder(node.left);
			preOrder(node.right);
		}

		public void inOrder(Node node) {
			if (node == null) {
				return;
			}

			inOrder(node.left);
			System.out.print(node.data + " ");
			inOrder(node.right);
		}

		public void postOrder(Node node) {
			if (node == null) {
				return;
			}

			postOrder(node.left);
			postOrder(node.right);
			System.out.print(node.data + " ");
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Tree tree = new Tree();
		
		Node node1 = tree.addNode(1);
		Node node2 = tree.addNode(2);
		Node node3 = tree.addNode(3);
		Node node4 = tree.addNode(4);
		Node node5 = tree.addNode(5);
		Node node6 = tree.addNode(6);
		Node node7 = tree.addNode(7);
		
		// 트리 연결관계 생성
		node1.addLeft(node2);
		node1.addRight(node3);
		node2.addLeft(node4);
		node2.addRight(node5);
		node3.addLeft(node6);
		node3.addRight(node7);
		
		tree.preOrder(node1);
		System.out.println();
		tree.inOrder(node1);
		System.out.println();
		tree.postOrder(node1);
		System.out.println();
		
		node2.deleteLeft();
		node3.deleteRight();

		System.out.println();
		tree.preOrder(node1);
		System.out.println();
		tree.inOrder(node1);
		System.out.println();
		tree.postOrder(node1);
		System.out.println();
	}