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

零下一度
リリース: 2017-07-18 17:56:53
オリジナル
1699 人が閲覧しました

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

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

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

関連ラベル:
ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート