[자료구조] 트리

Fekim·2022년 1월 12일

목록 보기

6/7

트리(Tree)

용어

노드(Node) : 트리를 구성하는 원소(자료)

간선(Edge) : 노드를 연결하는 선

루트(Root) : 트리 가장 꼭대기의 노드

차수(degree) : 한 노드가 가지는 서브 트리의 수. 즉 자식노드의 수

깊이(depth) : root부터 어떤 특정 노드까지의 깊이

leaf : 자식이 없는 최말단 노드

이진트리(Binary Tree)

모든 노드의 차수를 2 이하로 정하여, 전테 트리의 차수가 2 이하가 되도록 만든 트리.
포화 이진트리 : 모든 레벨에 노드가 꽉 차서 포화 상태인 이진트리.
완전 이진트리 : 포화 이진트리의 leaf들을 오른쪽 아래부터 제거하여 얻어진 트리.
편향 이진트리 : 이진트리 중에서 최소 개수의 노드를 가지면서, 왼쪽이나 오른쪽 서브트리만 가지고 있는 트리.

이진트리의 순회

전위 순회 : DLR
중위 순회 : LDR
후위 순회 : LRD

이진트리 구현

package Tree;

public class Tree
{
	int count;
	
	public Tree()
	{
		count = 0;
	}
	
	public class TreeNode
	{
		Object data;
		TreeNode left;
		TreeNode right;
		
		public TreeNode(Object data)
		{
			this.data = data;
			left = null;
			right = null;
		}
	
		public void addLeft(TreeNode node)
		{
			left = node;
			count++;
		}
		
		public void addRight(TreeNode node)
		{
			right = node;
			count++;
		}
		
		public void deleteLeft()
		{
			left = null;
			count--;
		}
		
		public void deleteRight()
		{
			right = null;
			count--;
		}
		
	}
	
	public TreeNode addNode(Object data)
	{
		TreeNode newNode = new TreeNode(data);
		return newNode;
	}
	
	/* 전위 순회 */
	public void preOrder(TreeNode node)
	{
		if(node == null)
			return ;
		System.out.println(node.data + " ");
		preOrder(node.left);
		preOrder(node.right);
	}
	
	/* 중위 순회 */
	public void inOrder(TreeNode node)
	{
		if(node == null)
			return;
		inOrder(node.left);
		System.out.println(node.data + " ");
		inOrder(node.right);
	}
	
	/* 후위 순회 */
	public void postOrder(TreeNode node)
	{
		if(node == null)
			return ;
		postOrder(node.left);
		postOrder(node.right);
		System.out.println(node.data + " ");	
	}
}