バイナリ ツリーの非再帰的走査に関するサンプル コード共有

バイナリ ツリーの非再帰的走査とはどのようなものですか?バイナリ ツリーの非再帰的走査でも、再帰的なアイデアが使用されます。例として、前置順序走査を取り上げます。最初に左下隅にあるノードを見つけて、それを出力し、次にこのノードの右側のサブツリーに対して次の操作を実行します。

プリオーダートラバーサル:

 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 中国語 Web サイトの他の関連記事を参照してください。