CS/자료구조 문제

문제 // 자료구조 // 트리(Tree) // 후속자 // toJava

문스코딩 2018. 8. 14. 19:52

package question.treegraph;

/**
* [후속자]
* 이진탐색트리에서 주어진 노드의 다음노드(중위 후속자, in-order-successor)를 찾는 알고리즘
* 각 노드에 부모 노드를 가리키는 링크가 존재
*
* [풀이]
* => 중위후속자가 무엇인가 ?
* => 중위순회를 진행할때 다음에 나올 노드
* => while(true) { 부모의 오른쪽 노드의 왼쪽 자식 노드, 없다면 부모로 올라감 }
* => 부모노드의 참조값을 가지고 있어야함
* */

public class Q06 {

/* main */
public static void main(String[] args) {

// @Test
Node rootB = new Node(4);
rootB.left = new Node(2);
rootB.left.parent = rootB;
rootB.right = new Node(6);
rootB.right.parent = rootB;
rootB.left.left = new Node(1);
rootB.left.left.parent = rootB.left;
rootB.left.right = new Node(3);
rootB.left.right.parent = rootB.left;
rootB.right.left = new Node(5);
rootB.right.left.parent = rootB.right;
rootB.right.right = new Node(7);
rootB.right.right.parent = rootB.right;

// == 중위후속자 ==
System.out.println(getNextInOrder(rootB.left.right).data/*3*/); // -> 4
}

/* Node */
static class Node {
int data;
Node parent;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
}

/* getNextInOrder */
public static Node getNextInOrder( Node node ) {
if( node == null ) return node;

// == 오른쪽 ==
if( node.right != null ) {
// == 오른쪽자식존재 -> 오른쪽에서 제일왼쪽노드 반환 ==
Node n = node.right;
if(n == null) return null;
while(n.left != null) {
n = n.left;
}
return n;
}
// == 위로 ==
else {
// == 오른쪽이 아닌 왼쪽이 있을 때까지 위로 올라감 ==
Node me = node; // me
Node parent = me.parent; // parent
while (parent != null && parent.left != me) {
me = parent;
parent = parent.parent;
}
return parent;
}
}
}


반응형