재귀 적 접근법은 이해하기 쉽지만 트리 모양이 기대에 어긋날 경우 여기에 최대 스택 깊이가 나타나며 이는 명시 적으로 할당 된 스택 구조에 의해 소비되는 힙 메모리를 제한하는 경향이 있습니다 . 그러므로 iterative walker를 만드는 데 시간을 투자하는 것이 좋습니다.
첫째, 자신은 트리 노드의 구조를 정의 : 우리는 이벤트가 나무를 통해 깊이 우선 산책하는 동안 신호에 반응 할 수있는 방법을 원하는거야
public final class TreeNode {
public final int data;
public final TreeNode left, right;
public TreeNode(int data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
public TreeNode(int data) {
this(data, null, null);
}
}
. 이 방법들에서 사실을 되 돌리는 것은 방문객이 산책을 계속하기를 바란다. 도보가 가능한 한 빨리 멈추는 거짓 요청을 돌려줍니다.
입니다
(1)
|
+-+-+
| |
(2) (5)
|
+-+-+
| |
(3) -
|
+-+-+
| |
- (4)
, 다섯 개 노드 곳이 있습니다 :
final class InOrder {
private InOrder() {}
private static final class Breadcrumb {
public final TreeNode node;
public final boolean rightIsNext; // Not a great name.
public Breadcrumb(TreeNode node, boolean rightIsNext) {
this.node = node;
this.rightIsNext = rightIsNext;
}
public static Breadcrumb goingLeft(TreeNode departingPoint) {
return new Breadcrumb(departingPoint, true);
}
public static Breadcrumb goingRight(TreeNode departingPoint) {
return new Breadcrumb(departingPoint, false);
}
}
public static <T extends Visitor> T walk(TreeNode root, T visitor) {
if (null == root ||
null == visitor)
throw new NullPointerException();
final Deque<Breadcrumb> stack = new ArrayDeque<Breadcrumb>();
if (!visitor.visitPre(root))
return visitor;
for (;;) {
for (TreeNode left = root.left;
null != left;
root = left, left = root.left) {
if (!visitor.visitPre(left))
return visitor;
stack.push(Breadcrumb.goingLeft(root));
}
if (!visitor.visitMid(root))
return visitor;
final TreeNode right = root.right;
if (null != right) {
if (!visitor.visitPre(right))
return visitor;
stack.push(Breadcrumb.goingRight(root));
root = right;
} else {
if (!visitor.visitPost(root))
return visitor;
// Go back up the tree until we find a node with an unexplored right child.
for (;;) {
if (stack.isEmpty())
return visitor;
final Breadcrumb breadcrumb = stack.pop();
if (breadcrumb.rightIsNext) {
if (!visitor.visitMid(breadcrumb.node)) {
return visitor;
}
if (null != breadcrumb.node.right) {
if (!visitor.visitPre(breadcrumb.node.right))
return visitor;
stack.push(Breadcrumb.goingRight(breadcrumb.node));
root = breadcrumb.node.right;
break;
}
}
if (!visitor.visitPost(breadcrumb.node))
return visitor;
}
}
}
}
}
은 샘플 트리에 walk() 기능을 운동 : 이제
public abstract class Visitor {
public boolean visitPre(TreeNode node) {
return true;
}
public boolean visitMid(TreeNode node) {
return true;
}
public boolean visitPost(TreeNode node) {
return true;
}
}
, 반복의 순서 도보 알고리즘을 정의 데이터 4와 5가있는 두 잎은 모두 오른쪽 자식입니다.
Pre(1)
Pre(2)
Pre(3)
Mid(3)
Pre(4)
Mid(4)
Post(4)
Post(3)
Mid(2)
Post(2)
Mid(1)
Pre(5)
Mid(5)
Post(5)
Post(1)
지금, 당신은에서 주문 산책하는 동안 발생하는 n 번째 노드를 찾을 수있는 편리한 방법을 질문 :
final TreeNode root = new TreeNode(1,
new TreeNode(2,
new TreeNode(3,
null,
new TreeNode(4)),
null),
new TreeNode(5));
walk(root,
new Visitor() {
private final PrintStream ps = System.out;
@Override
public boolean visitPre(TreeNode node) {
trace(node, "Pre");
return true;
}
@Override
public boolean visitMid(TreeNode node) {
trace(node, "Mid");
return true;
}
@Override
public boolean visitPost(TreeNode node) {
trace(node, "Post");
return true;
}
private TreeNode trace(TreeNode node, String phase) {
ps.print(phase);
ps.print('(');
ps.print(node.data);
ps.println(')');
return node;
}
});
이
다음과 같은 인쇄합니다.
private static TreeNode findNthInOrder(TreeNode root, final int n) {
if (n < 0)
throw new IllegalArgumentException();
return walk(root,
new Visitor() {
public TreeNode found = null;
private int remaining = n + 1;
@Override
public boolean visitMid(TreeNode node) {
if (0 == --remaining) {
found = node;
return false;
}
return true;
}
}).found;
}
우리의 샘플에서이 함수를 호출 : 우리는 하나는 두 번째를 지정하고, 매개 변수 n 누구의 왼쪽 서브 트리 이미 탐사 된 발생의 첫 번째 노드로 제로를 지정 findNthInOrder()라는 함수를 쓸 것이다 샘플 트리로 이전 추적 거리를 일치 콘솔에
final TreeNode nth = findNthInOrder(root, 3);
System.out.println(null != nth ? nth.data : "(none)");
이 인쇄 "1": 나무는 예상 된 결과를 얻을 수 위의 인수에 따라 (즉 네 번째, 제로로부터 시작되는 인덱스 3,) 방출 된 "Mid"추적은 data 값을 가진 루트 노드에 대한 것입니다. .
요약하면 놀이터에서 개념을 형식화하기에 충분한 빌드를 고려하여 이러한 특정 쿼리를 건전한 기초 위에보다 확실하게 작성할 수 있습니다.
이것은 이해가되지 않습니다. x를 두 번 초기화하는 이유는 무엇입니까? 'int c = x == 0에서 y는 어디에 있습니까? y : x;'? 이것은 디자인에 대한 커다란 질문입니다. –
@ArjunPatel Keeto가 편집하기 전에 OP의 코드를 복사하여 붙여 넣었습니다 (편집 내역 참조). 두 번째'int x'는'int y'이어야합니다. 이 문제가 해결되었습니다. – dasblinkenlight