二叉樹的遍歷 遞歸 非遞歸 Java

二叉樹的常用遍歷算法實現(xiàn)

二叉樹的形狀.png

首先定義 二叉樹，節(jié)點值，左子節(jié)點，右子節(jié)點

public class TreeNode {
    private int value;
    private TreeNode left;
    private TreeNode right;
    public TreeNode(int value) {
        this.value = value;
    }
}

前序遍歷

  • 遞歸實現(xiàn)
public static void preOrder(TreeNode treeNode) {
    if (treeNode != null) {
        System.out.print(treeNode.value + " ");
        preOrder(treeNode.left);
        preOrder(treeNode.right);
    }
}
  • 非遞歸實現(xiàn)（1）
    • 這個是常規(guī)思路，先遍歷到根節(jié)點，并打印、壓棧，然后遍歷其左子節(jié)點，打印、壓棧。
    • 若左子節(jié)點已經(jīng)是葉子節(jié)點，則 while 循環(huán)結(jié)束，開始從棧中彈出根節(jié)點，并訪問根節(jié)點的右子樹，直到棧為空，則遍歷結(jié)束。
public static void preOrderStack(TreeNode treeNode) {

    if (treeNode == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode root = treeNode;
    
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            //  注意和 中序非遞歸的區(qū)別，這里是先打印節(jié)點值，再去加入棧中
            System.out.print(root.value + " ");
            stack.push(root);
            root = root.left;
        }
        if (!stack.isEmpty()) {
            root = stack.pop();
            root = root.right;
        }
    }
}
  • 非遞歸實現(xiàn)（2）
    • 這里的思路是利用棧先進后出的性質(zhì)， 先將根節(jié)點入棧
    • 循環(huán)中，彈出根節(jié)點，然后先加入右子節(jié)點，后加入左子節(jié)點
    • 再一次循環(huán)，新彈出的節(jié)點就是剛壓入的左子節(jié)點
public static void preOrderStack1(TreeNode treeNode) {
    if (treeNode == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(treeNode);
    while (!stack.isEmpty()) {
        TreeNode root = stack.pop();
        System.out.print(root.value + " ");
        if (root.right != null) {
            stack.push(root.right);
        }
        if (root.left != null) {
            stack.push(root.left);
        }
    }
}

中序遍歷

  • 遞歸實現(xiàn)
public static void midOrder(TreeNode treeNode) {
    if (treeNode != null) {
        midOrder(treeNode.left);
        System.out.print(treeNode.value + " ");
        midOrder(treeNode.right);
    }
}
  • 非遞歸實現(xiàn)
    • 中序遍歷是 左 根 右
public static void midOrderStack(TreeNode treeNode) {
    if (treeNode == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<TreeNode>();
    while (treeNode != null || !stack.isEmpty()) {
        while (treeNode != null) {
            stack.push(treeNode);
            treeNode = treeNode.left;
        }
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            System.out.print(treeNode.value + " ");
            treeNode = treeNode.right;
        }
    }
}

后序遍歷

  • 遞歸實現(xiàn)
public static void postOrder(TreeNode treeNode) {
    if (treeNode != null) {
        postOrder(treeNode.left);
        postOrder(treeNode.right);
        System.out.print(treeNode.value + " ");
    }
}
  • 非遞歸實現(xiàn)
    • 由于后序遍歷二叉樹的順序是 左 右 根，故可以使用中間臨時棧保存 根 右 左 的遍歷結(jié)果
public static void postOrderStack(TreeNode treeNode) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    Stack<TreeNode> stack1 = new Stack<TreeNode>();
    while (treeNode != null || !stack.isEmpty()) {
        while (treeNode != null) {
            stack.push(treeNode);
            stack1.push(treeNode);
            treeNode = treeNode.right;
        }
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            treeNode = treeNode.left;
        }
    }
    while (!stack1.isEmpty()) {
        TreeNode treeNode1 = stack1.pop();
        System.out.print(treeNode1.value + " ");
    }
}

層次遍歷

public static void levelOrder(TreeNode treeNode) {
    if (treeNode == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(treeNode);
    while (!queue.isEmpty()) {
        TreeNode root = queue.poll();
        System.out.print(root.value + " ");

        if (root.left != null) {
            queue.add(root.left);
        }
        if (root.right != null) {
            queue.add(root.right);
        }
    }
}

“之” 字型遍歷

public static void printZ(TreeNode treeNode){
    if (treeNode == null){
        return;
    }
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(treeNode);
    boolean flag = true;
    while (!stack1.isEmpty() || !stack2.isEmpty()){
        if (flag){
            while (!stack1.isEmpty()) {
                treeNode = stack1.pop();
                System.out.print(treeNode.value+" ");
                if (treeNode.left != null) {
                    stack2.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    stack2.add(treeNode.right);
                }
            }
        }else {
            while (!stack2.isEmpty()) {
                treeNode = stack2.pop();
                System.out.print(treeNode.value+" ");
                if (treeNode.right != null) {
                    stack1.add(treeNode.right);
                }
                if (treeNode.left != null) {
                    stack1.add(treeNode.left);
                }
            }
        }
        flag = flag ^ true;
    }
}

求最大深度

  • 遞歸實現(xiàn)
public static int getDepth(TreeNode treeNode) {
    if (treeNode == null) {
        return 0;
    }
    int left = getDepth(treeNode.left);
    int right = getDepth(treeNode.right);
    return left > right ? left + 1 : right + 1;
}
  • 非遞歸實現(xiàn)
public static void getDepth1(TreeNode treeNode){
    if (treeNode == null){
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(treeNode);
    int depth = 0;
    while (!queue.isEmpty()){
        int size = queue.size();
        while (size > 0){
            treeNode = queue.poll();
            if (treeNode.left != null){
                queue.add(treeNode.left);
            }
            if (treeNode.right != null){
                queue.add(treeNode.right);
            }
            size--;
        }
        depth++;
    }
    System.out.println(depth);
}

求最大寬度

  • 對于二叉樹，每一層的節(jié)點數(shù)是不一樣的，計算二叉樹中具有結(jié)點數(shù)最多的那一層的結(jié)點個數(shù)
    用隊列實現(xiàn)，實質(zhì)就是當當前層節(jié)點彈出，加入下一層節(jié)點 
public static void getWidth(TreeNode treeNode) {
    // 根節(jié)點為空，則 最大寬度為 0 ；
    if (treeNode == null) {
        return;
    }
    // 此時根節(jié)點入隊，最大寬度為 1 
    int max = 1;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(treeNode);

    // 注意循環(huán)條件：隊列不為空
    while (!queue.isEmpty()) {
        // 記錄當前層的節(jié)點數(shù)
        int size = queue.size();  

        // 把當前層的所有節(jié)點依次彈出，循環(huán)結(jié)束時，當前層節(jié)點會全部彈出，此時隊列中只包含下一層的所有節(jié)點
        while (size > 0) {   

            treeNode = queue.poll();
            size--;

            // 彈出的同時把下一層的節(jié)點加入隊列中
            if (treeNode.left != null) {
                queue.add(treeNode.left);   
            }
            if (treeNode.right != null) {
                queue.add(treeNode.right);
            }
        }
       // 此時隊列中存放的是下一層的所有節(jié)點，比較它與上一層節(jié)點的個數(shù)，保存較大值
        if (max < queue.size()) {
            max = queue.size();
        }
    }
    System.out.println(max);
}

用數(shù)組列表實現(xiàn)求最大寬度，類比隊列，用兩個指針 i，j。i 指向當前層節(jié)點第一個，j 指向當前層最后一個。彈出時 i++ ，加入元素時 j++；

public static void levelOrder(TreeNode treeNode){
    if (treeNode == null){
        return;
    }
    List<TreeNode> list = new ArrayList<TreeNode>();
    list.add(treeNode);
    int max = 1;
    int i =0;
    int j = 0;
    // i，j 最多相等，遍歷到最后一個元素時，i = j ，此時 i 節(jié)點左右子節(jié)點為空，下一步 i 將 大于 j ，循環(huán)結(jié)束
    while (i <= j){
        // 臨時保存當前層的節(jié)點數(shù)
        int size = j-i+1;
        while (size > 0){
            treeNode = list.get(i);
            if (treeNode.left != null){
                list.add(treeNode.left);
                j++;
            }
            if (treeNode.right != null){
                list.add(treeNode.right);
                j++;
            }
            size--;
            i++;
        }
        if (max < j-i+1){
            max = j-i+1;
        }
    }
    System.out.println(max);
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容