이진 트리의 비재귀 순회란 무엇인가요? 이진 트리의 비재귀 순회도 재귀적 아이디어를 사용합니다. 선주문 순회를 예로 들어 보겠습니다. 먼저 왼쪽 하단에서 노드를 찾아 출력한 후 이 노드의 오른쪽 하위 트리에서 다음 작업을 수행합니다.
선주문 순회:
public void pre_iteration(Node p) {if (p == null) return; Stack<Node> stack = new Stack<>();while (!stack.isEmpty() || p != null) {while (p != null) { System.out.println(p.val); stack.push(p); p = p.left; }if (!stack.isEmpty()) { p = stack.pop(); p = p.right; } } }
순차 순회:
public void in_iteration(Node p) {if (p == null) return; Stack<Node> stack = new Stack<>();while (!stack.isEmpty() || p != null) {while (p != null) { stack.push(p); p = p.left; }if (!stack.isEmpty()) { p = stack.pop(); System.out.println(p.val); p = p.right; } } }
후순 순회: (stack2는 현재 노드의 올바른 하위 트리가 통과되었는지 기록하는 데 사용됩니다.)
public static void post_iteration(Node p) {if (p == null) return; Stack<Node> stack = new Stack<>(); Stack<Boolean> stack2 = new Stack<>();while (!stack.isEmpty() || p != null) {while (p != null) { stack.push(p); stack2.push(false); p = p.left; }while (!stack.isEmpty() && stack2.peek()) { System.out.println(stack.pop().val); stack2.pop(); }if (!stack.isEmpty()) { p = stack.peek().right; stack2.pop(); stack2.push(true); } } }
위 내용은 이진 트리의 비재귀 순회에 대한 예제 코드 공유의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!