> Java > java지도 시간 > 본문

이진 트리의 비재귀 순회에 대한 예제 코드 공유

零下一度
풀어 주다: 2017-07-18 17:56:53
원래의
1699명이 탐색했습니다.

이진 트리의 비재귀 순회란 무엇인가요? 이진 트리의 비재귀 순회도 재귀적 아이디어를 사용합니다. 선주문 순회를 예로 들어 보겠습니다. 먼저 왼쪽 하단에서 노드를 찾아 출력한 후 이 노드의 오른쪽 하위 트리에서 다음 작업을 수행합니다.

선주문 순회:

 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿