[211129] 교육 29일차

oxllz·2022년 2월 8일
Java교육
0

교육

목록 보기
21/41

재귀호출

import static banana.Logic.print;
//
class Logic {
	public static void print() {}
}
//
public class Test236 {
	public static void main( String[] args ) {
		System.out.println("HelloWorld");
		print();
	}	
}

import static static 하게 선언된 함수를 호출한다.

import static banana.Logic.print;
//
class Logic {
	// 적절한 종료시점이 없어 무한반복한다.
	public static void print() {
		System.out.println("HelloWorld");
		try {
			Thread.sleep( 800 );
		}
		catch( Exception e ){}
		print();
	}
/*
재귀 호출을 그만하는 시점이 있어야 한다.
	print( 5 );
		System.out.println("HelloWorld " + 5 );
		print( 4 );
			System.out.println("HelloWorld " + 4 );
			print( 3 );
				System.out.println("HelloWorld " + 3 );
				print( 2 );
					System.out.println("HelloWorld " + 2 );
					print( 1 );
						System.out.println("HelloWorld " + 1 );
						print( 0 );
							System.out.println("HelloWorld " + 0 );
							-- 더 이상 재귀호출 안함. 여기서 종료
	*/
	public static void print( int i ) {
		System.out.println("HelloWorld " + i );
		if( i > 0 ) {
			print( i-1 );
		}
	}	
}
//
public class Test237 {
	public static void main( String[] args ) {
		print( 5 );
	}	
}

재귀 호출 ( recursive call ) : 함수 안에서 자기 자신을 다시 호출, 적절한 종료 시점이 없으면 무한 반복한다.

import static banana.Logic.*;
//
class Logic {
	public static int apple( int i ) {
		if( i != 0 )
			return i * apple( i-1 );
		else
			return 1;
	}
}
//
public class Test238 {
	public static void main( String[] args ) {
		int r = apple( 5 );
		System.out.println( r );
	}	
}
apple(5) = 5 * apple(4)
		 = 5 * 4 * apple(3)
         = 5 * 4 * 3 * apple(2)
         = 5 * 4 * 3 * 2 * apple(1)
         = 5 * 4 * 3 * 2 * 1 * apple(0)
         = 5 * 4 * 3 * 2 * 1 * 1

이진트리

class Node {
	int data = 0;
	Node next = null;
    // 매개변수와 로컬변수가 이름이 같으면 this 를 사용하여 구별
	Node( int data, Node n ) {
		this.data = data;
		next = n;
	}
}

class Node {
	int data = 0;
	Node left = null;
	Node right = null;
	//
	public Node( int data ) {
		this.data = data;
	}
}
//
public class Test240 {
	public static void main( String[] args ) {
		Node root = new Node( 5 );
		// 이렇게 코드를 쓰면 a 와 root.left 는 같은 대상. 즉 new Node( 3 ) 을 가리키게 된다.
		Node a = root.left = new Node( 3 );
		Node b = root.right = new Node( 8 );
		//
		System.out.println( a == root.left );
		System.out.println( b == root.right );
		//
		a.left = new Node( 1 );
		a.right = new Node( 4 ); 
	}
}

이진트리 : 포인터 2개를 가지고 아래로 이어붙이는 형태의 자료구조

import static banana.Logic.*;
//
class Node {
	int data = 0;
	Node left  = null;
	Node right = null;
	//
	public Node( int data ) {
		this.data = data;
	}
}
//
public class Test241 {
	public static void main( String[] args ) {
		Node root = new Node( 5 );
		//
		Node a = root.left = new Node( 3 );
		Node b = root.right = new Node( 8 );
		//
		a.left  = new Node( 1 );
		a.right = new Node( 4 );
		//
		print( root );
	}	
}
//
class Logic {
	public static void print ( Node n ) {
		if( n != null ) {
			System.out.println( n.data );
			print( n.left );
			print( n.right );
		}
	}
}
	print( n = [5] )
		System.out.println( 5 )
		print( n = [3] )
			System.out.println( 3 )
			print( n = [1] )
				System.out.println( 1 )
				print( null )
				print( null )
			print( n = [4] );
				System.out.println( 4 )
				print( null )
				print( null )
		print( n = [8] )
			System.out.println( 8 )
			print( null )
			print( null )

print( n.left );
print( n.right );

이므로 트리의 왼쪽 끝까지 탐색 후 오른쪽을 탐색하는 코드

중위순회

import static banana.Logic.*;
//
class Node {
	int data = 0;
	Node left  = null;
	Node right = null;
	//
	public Node( int data ) {
		this.data = data;
	}
}
//
public class Test242 {
	public static void main( String[] args ) {
		Node root = new Node( 5 );
		//
		Node a = root.left = new Node( 3 );
		Node b = root.right = new Node( 8 );
		//
		a.left  = new Node( 1 );
		a.right = new Node( 4 );
		//
		print( root );
	}	
}
//
class Logic {
	public static void print ( Node n ) {
		if( n != null ) {
			print( n.left );
			System.out.println( n.data );
			print( n.right );
		}
	}
}
	print( n = [5] );
		print( n = [3] );
			print( n = [1] );
				print( null );
				System.out.println( 1 );
				print( null );
			System.out.println( 3 );
			print( n = [4] );
				print( null );
				System.out.println( 4 );
				print( null );
		System.out.println( 5 );
		print( n = [8] );
			print( null );
			System.out.println( 8 );
			print( null );

트리의 제일 오른쪽으로 이동한뒤
제일 왼쪽에 위치한 서브트리의 왼쪽노드 - 루트노드 - 오른쪽노드
해당 서브트리를 가진 루트노드 -> 오른쪽 서브트리에 왼쪽 노드가 존재한다면 그쪽으로 이동 ... 이런식으로 이동한다.

배치

이진트리 에서 노드를 배치하는 원칙

  • 중복을 허용하지 않는다.
  • 작은 값을 왼쪽으로 보낸다.
  • 큰 값을 오른쪽으로 보낸다.
  • null 을 만나면 거기에 node 를 추가한다.

최소값 찾기

public class Test243 {
	public static void main( String[] args ) {
		Node root = null;
		root = new Node( 5 );
		Node a = root.left = new Node( 3 );
		Node b = root.right = new Node( 8 );
		Node c = a.left  = new Node( 1 );
		a.right = new Node( 4 );
		//	위의 원칙에 의해 추가된 노드들
		c.right = new Node( 2 );
		b.left  = new Node( 7 );
		b.right = new Node( 9 );
        //	최소값을 리턴하는 min 구현
		//	단 데이터가 하나도 없으면 -1 
		int r = min( root );
		System.out.println( r );
        // 재귀호출 이용하지 않는 경우
        int r2 = min2( root );
		System.out.println( r2 );
	}	
}
//
class Logic {
	//	재귀호출 없이 최소값 찾기
	public static int min2( Node t ) {
		if( t == null ) 
			return -1;
		while( t.left != null ) {
			t = t.left;
		}
		return t.data;
	}
	//
	public static int min( Node t ) {
		if( t == null ) {
			return -1;
		}
		else if( t.left != null ){
			return min( t.left );
		}
		else {
			return t.data;
		}
	}
}


위의 원칙에 의해 최소값은 가장 왼쪽에 위치하므로 t.left != null 일때까지 이동한다.

노드 찾기

public class Test245 {
	public static void main( String[] args ) {
		Node root = null;
		root = new Node( 5 );
		Node a = root.left = new Node( 3 );
		Node b = root.right = new Node( 8 );
		Node c = a.left  = new Node( 1 );
		a.right = new Node( 4 );
		//
		Node found = apple( root, 1 );
		if( found != null ) {
			System.out.println( found.data );
		}
	}	
}
//
class Logic {
	public static Node apple ( Node n, int d ) {
		Node found = null;
		if( n != null ) {
			//	찾던값과 data 가 맞으면 대입
			if( n.data == d )
				found = n;
            // 찾는 값보다 노드의 data 값이 크면 왼쪽으로 이동한다.     
			if( found == null && n.data > d )
				found = apple( n.left , d );
			// 찾는 값보다 노드의 data 값이 작으면 오른쪽으로 이동한다. 
			if( found == null && n.data < d )
				found = apple( n.right , d );
		}
		return found;
	}
}
배치 원칙 : 왼쪽 노드 < 루트 노드 < 오른쪽 노드

함수를 이용해 노드 추가하기

public class Test248 {
	public static void main( String[] args ) {
/*		아래의 모양대로 노드를 배치하던 걸 함수호출로 구현
		root = new Node( 5 );
		Node a = root.left = new Node( 3 );
		Node b = root.right = new Node( 8 );
		Node c = a.left  = new Node( 1 );
		a.right = new Node( 4 );
*/		
		Node root = null;
		root = add( root, 5 );
		root = add( root, 3 );
		root = add( root, 8 );
		root = add( root, 1 );
		root = add( root, 4 );
	}	
}
//
class Logic {
	public static Node add( Node n, int d ) {
		if( n == null ) {
			n = new Node( d );
		}
		else {
			if( n.data > d )
				n.left  = add( n.left , d );
			else if( n.data < d )
				n.right = add( n.right , d );
			else 
				throw new RuntimeException("Data Duplicated");
		}
		return n;
	}
}
profile
oxllz
이전 포스트

[211126] 교육 26일차

다음 포스트

[211130] 교육 30일차

0개의 댓글