지역 사회 배우다 도구 라이브러리 여가
찾다
한국어
집 > Java > java지도 시간 > 본문

Java 이진 트리의 재귀 및 비재귀 순회 방법은 무엇입니까?

WBOY
풀어 주다： 2023-04-24 13:04:14
앞으로
1375명이 탐색했습니다.

머리말

이진 트리의 순회 방법은 선순 순회, 순순 순회, 후속 순회, 수준순 순회로 구분됩니다.

Java 이진 트리의 재귀 및 비재귀 순회 방법은 무엇입니까?

1. 재귀 순회

재귀의 경우 재귀의 세 가지 요소에 대해 이야기해야 합니다. 선주문 순회를 예로 들어

재귀 입력 매개변수 및 반환 값

값을 인쇄해야 하기 때문입니다. ​선주문 순회 노드의 매개변수이므로 목록의 노드 값을 전달해야 합니다. 이 외에도 데이터를 처리할 필요가 없으며 반환 값이 필요하지 않으므로 반환됩니다. 재귀 함수 유형은 void입니다. 코드는 다음과 같습니다. 

public void preorder(TreeNode root, List<Integer> result)
로그인 후 복사

종료 조건 결정

재귀 과정에서 재귀는 어떻게 종료됩니까? 물론 현재 순회하는 노드가 비어 있으면 현재 수준은 다음과 같습니다. 재귀가 곧 끝나기 때문에 현재 순회하는 노드가 비어 있으면 바로 리턴

if (root == null) return;
로그인 후 복사

Single-layer loop Logic

선순서 순회는 중간 순서와 왼쪽 순서이므로 단일 수준 재귀의 논리는 다음과 같습니다. 코드는 다음과 같습니다.

result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
로그인 후 복사
// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List preorderTraversal(TreeNode root) {
        List result = new ArrayList();
        preorder(root, result);
        return result;
    }
    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);//先保存中间节点
        preorder(root.left, result); //处理左边节点
        preorder(root.right, result); //处理右边节点
    }
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode root, List list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list); //先处理左边节点
        list.add(root.val);       //保存中间当前的节点
        inorder(root.right, list);//先处理右边节点
    }
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        postorder(root, res);
        return res;
    }
    void postorder(TreeNode root, List list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);  //先处理左边节点
        postorder(root.right, list); //再处理右边节点
        list.add(root.val);          //保存最后  
    }
}
로그인 후 복사

2. 비반복 순회

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        if (root == null) return res;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right != null) { //先将右孩子入栈，因为它在最后
                stack.push(node.right);
            }
            if (node.left != null) { //左孩子入栈再出栈
                stack.push(node.left);
            }
        }
        return res;
    }
}
//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            //如果可以，一直往左下探
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop(); //弹出来的肯定是叶子节点或中间节点
                res.add(cur.val); //将这个节点加入list
                cur = cur.right; //查看当前节点是否有右节点，如果右，肯定是中间节点，如果没有，就是叶子节点，继续弹出就可以
            }
        }
        return res;
    }
}
//后序遍历
//再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.left != null) stack.push(node.left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node.right != null) stack.push(node.right);// 空节点不入栈 
        }
        Collections.reverse(res); // 将结果反转之后就是左右中的顺序了
        return res;
    }
}
로그인 후 복사

3. 이진 트리의 통합 반복 방법

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}
//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}
//后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}
로그인 후 복사

위 내용은 Java 이진 트리의 재귀 및 비재귀 순회 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨：
java
원천：yisu.com
이전 기사：Java에서 재귀 비교를 통해 최대값을 찾는 방법 다음 기사：Java 1차원 배열 및 2차원 배열 요소의 기본 초기화 값을 결정하는 방법에 대한 설명
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
최신 이슈
자동 반올림 없이 JavaScript에서 문자열을 19자리 숫자로 변환하는 방법은 무엇입니까? 숫자로 변환하려는 경우 문자열 입력 숫자 input="6145390195186705543"(6145390195186705000)이 있습니다.
에서 2024-03-30 14:42:35
0
1
367
관련 주제
더>
인기 추천
인기 튜토리얼
더>
관련 튜토리얼
인기 추천
최신 강좌
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿