關於二元樹的非遞歸遍歷實例程式碼分享

    二元樹的非遞歸遍歷是怎麼樣的？二元樹的非遞歸遍歷也是採用的是遞歸的思想，拿前序遍歷為例：先透過找到最左下角的節點，然後將其輸出，並且對此節點的右子樹再進行下一步的操作。

前序遍歷：

 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中文網其他相關文章！