Java實(shí)現(xiàn)二叉樹的遍歷方法是什么

本篇內(nèi)容主要講解“Java實(shí)現(xiàn)二叉樹的遍歷方法是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Java實(shí)現(xiàn)二叉樹的遍歷方法是什么”吧!

遍歷二叉樹

遍歷或稱周游，traversal。系統(tǒng)地訪問數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都正好被訪問到一次。

深度優(yōu)先遍歷二叉樹

三種深度優(yōu)先遍歷的遞歸定義：

• 前序法（tLR次序，preorder traversal）：訪問根結(jié)點(diǎn)，按前序遍歷左子樹；按前序遍歷右子樹。

• 中序法（LtR次序，inorder traversal）：按中序遍歷左子樹；訪問根結(jié)點(diǎn)；按中序遍歷右子樹。

• 后序法（LRt次序，postorder traversal）：按后序遍歷左子樹；按后序遍歷右子樹；訪問根結(jié)點(diǎn)。

遞歸的前序、中序、后序

public static List<Integer> preOrderTraverseByRecursion(BinaryTreeNode root, List<Integer> list) {
    if (root != null) {
         list.add(root.getKey());//前序法訪問節(jié)點(diǎn)
         preOrderTraverseByRecursion(root.getLeft(), list);
         //list.add(root.getKey());//中序法訪問節(jié)點(diǎn)
         preOrderTraverseByRecursion(root.getRight(), list);
         //list.add(root.getKey());//后序法訪問節(jié)點(diǎn)
    }
    return list;
}

非遞歸遍歷

遞歸算法非常簡潔，推薦使用，當(dāng)前的編譯系統(tǒng)優(yōu)化效率很不錯(cuò)了。特殊情況用棧模擬遞歸，深度優(yōu)先遍歷的回溯特點(diǎn)和棧的工作原理一致，有些應(yīng)用環(huán)境資源限制不適合遞歸。

非遞歸的前序遍歷

實(shí)現(xiàn)

/**
 * 先序遍歷（非遞歸）
 * 通過棧來避免遞歸（有節(jié)點(diǎn)入棧）
 *
 * @param root
 */
public static List<Integer> preOrderTraverseByNonRecursion(BinaryTreeNode root) {
    List<Integer> list = new ArrayList<>();// 用于存放遍歷后的結(jié)果
    Stack<BinaryTreeNode> stack = new Stack();// 用于存放右子樹節(jié)點(diǎn)
    BinaryTreeNode p = root;
    //左子樹和右子樹都未遍歷時(shí)，遍歷
    while (p != null || stack.size() > 0) {
        if (p != null) { //左子樹不為空時(shí)，遍歷左子樹
            list.add(p.getKey());//當(dāng)前節(jié)點(diǎn)輸出
            stack.push(p.getRight());//右子樹入棧，待左子樹遍歷完后遍歷右子樹
             p = p.getLeft();//遍歷左子樹
         } else { //左子樹遍歷完后，遍歷右子樹
             p = stack.pop();
         }
    }
    return list;
}

非遞歸的中序遍歷

實(shí)現(xiàn)

/**
 * 中序遍歷（非遞歸）
 *
 * @param root
 */
public static List<Integer> inOrderTraverseByNonRecursion(BinaryTreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<BinaryTreeNode> stack = new Stack<>();
    BinaryTreeNode current = root;
    //遍歷節(jié)點(diǎn)的左子樹并將根結(jié)點(diǎn)入棧，直到左子樹為null時(shí)，然后出棧獲取節(jié)點(diǎn)并遍歷該節(jié)點(diǎn)的右子樹的左子樹直到為null
    while(current != null || !stack.empty()){
        if(current != null){
            stack.push(current);
            current = current.getLeft();
        }else{
           BinaryTreeNode top = stack.pop();
           list.add(top.getKey());
           current = top.getRight();
        }
    }
    return list;
}

非遞歸的后序遍歷

實(shí)現(xiàn)

/**
 * 后續(xù)遍歷（非遞歸）
 *
 * @param root
 */
public static List<Integer> postOrderTraverseByNonRecursion(BinaryTreeNode root) {
    Stack<BinaryTreeNode> stack = new Stack<>();
    List<Integer> list = new ArrayList<>();
    stack.push(root);
    BinaryTreeNode current;
    while (stack.isEmpty() == false) {
        current = stack.pop();
        if (current != null) {
            list.add(current.getKey());
            stack.push(current.getLeft());
            stack.push(current.getRight());
        }
    }
    Collections.reverse(list);
    return list;
}

寬度優(yōu)先遍歷二叉樹

從二叉樹的第0層（根結(jié)點(diǎn)）開始，自上而下，追層遍歷；在同一層中，按照從左到右的順序?qū)?jié)點(diǎn)逐一訪問。 特點(diǎn)是先遍歷先訪問，符合隊(duì)列的特征，通過隊(duì)列來實(shí)現(xiàn)。 實(shí)現(xiàn)如下：

/**
 * 層序遍歷（寬度優(yōu)先遍歷）
 * 特點(diǎn)是先進(jìn)先出，符合隊(duì)列的特性
 *
 * @param root
 * @return
 */
public static List<Integer> layerOrderTraverse(BinaryTreeNode root) {
    List<Integer> list = new ArrayList<>();
    LinkedList<BinaryTreeNode> queue = new LinkedList<>();
    BinaryTreeNode current;
    queue.offer(root);
    while (!queue.isEmpty()){
        current = queue.poll();
        list.add(current.getKey());
        if(current.getLeft() != null){
            queue.addLast(current.getLeft());
        }
        if(current.getRight() != null){
            queue.addLast(current.getRight());
        }
    }
    return list;
}

根據(jù)遍歷序列構(gòu)造二叉樹

先來個(gè)結(jié)論及說明：

• 僅一個(gè)先（中、后）序序列不能構(gòu)造唯一一顆二叉樹（原因：無法確定左右子樹或根結(jié)點(diǎn)）

• 僅先（后）序序列和中序序列可以構(gòu)造唯一一顆二叉樹（原因：先序序列和后序序列無法構(gòu)造唯一一顆二叉樹）

• 用擴(kuò)充先（后）序序列可以構(gòu)造唯一一顆二叉樹

• 用擴(kuò)充中序序列不能構(gòu)造唯一一顆二叉樹

先序序列和中序序列創(chuàng)建構(gòu)造二叉樹

實(shí)現(xiàn)：

 /**
     * 根據(jù)先序序列和中序序列構(gòu)造二叉樹（遞歸實(shí)現(xiàn)）
     * <p>
     * 先序序列第一個(gè)元素是樹的根結(jié)點(diǎn)，從中序序列中找出與根結(jié)點(diǎn)所在位置k:
     * 1.確定根結(jié)點(diǎn)的左子樹和右子樹的中序序列：該位置之前的元素就是根結(jié)點(diǎn)左子樹的中序序列，該位置之后的元素就是根結(jié)點(diǎn)的右子樹的中序序列
     * 2.確定根結(jié)點(diǎn)的左子樹和右子樹的先序序列：先序序列第一個(gè)元素往后k元素就是根結(jié)點(diǎn)左子樹的先序序列，k+1位置之后就是根結(jié)點(diǎn)右子樹的先序序列
     * <p>
     * <p>
     * perOrder[i]~perOrder[j] 是子樹的先序序列
     * inOrder[s]~inOrder[t] 是子樹的中序序列
     *
     * @param perOrder
     * @param inOrder
     * @param i
     * @param j
     * @param s
     * @param t
     * @return
     */
    public static BinaryTreeNode buildTreeByPerOrderAndInOrder(Integer[] perOrder, Integer[] inOrder, int i, int j, int s, int t) {
        if (i > j) {
            return null;
        }
        BinaryTreeNode root = new BinaryTreeNode(perOrder[i]);
        int k;
        k = s;
        while (k <= t && inOrder[k] != perOrder[i]) {
            k++;
        }
        if (k > t) {
            return null;
        }
        root.setLeft(buildTreeByPerOrderAndInOrder(perOrder, inOrder, i + 1, j + k - s, s, k - 1));
        root.setRight(buildTreeByPerOrderAndInOrder(perOrder, inOrder, i + k - s + 1, j, k + 1, t));
        return root;
    }

后序序列和中序序列創(chuàng)建構(gòu)造二叉樹

一個(gè)節(jié)點(diǎn)的左子樹和右子樹存在三種組合方式，左子樹為null，右子樹為null，左右子樹都不為null。 運(yùn)用遞歸思想時(shí)，按這三種情況分析左右子樹的后序序列和中序序列。實(shí)現(xiàn)如下：

 /**
     * 根據(jù)后序序列和中序序列構(gòu)造二叉樹（遞歸實(shí)現(xiàn)）
     *
     * postOrder[i]~postOrder[j]是子樹的后序序列
     * inOrder[s]~inOrder[t]是子樹的中序序列
     *
     * @param postOrder
     * @param inOrder
     * @param i
     * @param j
     * @param s
     * @param t
     * @return
     */
    public static BinaryTreeNode buildTreeByPostOrderAndInOrder(Integer[] postOrder, Integer[] inOrder, int i, int j, int s, int t) {
        if (i > j) {
            return null;
        }
        BinaryTreeNode root = new BinaryTreeNode(postOrder[j]);
        int k;
        k = s;
        while (k <= t && inOrder[k] != postOrder[j]) {
            k++;
        }
        if (k > t) {
            return null;
        }
        //左子樹個(gè)數(shù)
        int countLeft = k - s;
        //右子樹個(gè)數(shù)
        int countRight = t - k;

        if (countLeft == 0) {
            //左子樹為null
            root.setRight(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - countRight, j - 1, t - countRight + 1, t));
        } else if (countRight == 0) {
            //右子樹為null
            root.setLeft(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - countLeft, j - 1, t - countLeft, t - countRight - 1));
        } else {
            //左、右子樹不為null
            root.setLeft(buildTreeByPostOrderAndInOrder(postOrder, inOrder, i, i + countLeft - 1, s, s + countLeft - 1));
            root.setRight(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - 1 - countRight + 1, j - 1, t - countRight + 1, t));
        }


        return root;
    }

到此，相信大家對“Java實(shí)現(xiàn)二叉樹的遍歷方法是什么”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！