Rumah > Java > javaTutorial > teks badan

关于二叉树的非递归遍历实例代码分享

零下一度
Lepaskan: 2017-07-18 17:56:53
asal
1699 orang telah melayarinya

    二叉树的非递归遍历是怎么样的?二叉树的非递归遍历也是采用的是递归的思想,拿前序遍历为例:先通过找到最左下角的节点,然后将其输出,并且对此节点的右子树再进行下一步的操作。

前序遍历:

 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;
            }
        }
    }
Salin selepas log masuk

中序遍历:

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;
            }
        }
    }
Salin selepas log masuk

后序遍历:(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);
            }
        }
    }
Salin selepas log masuk

Atas ialah kandungan terperinci 关于二叉树的非递归遍历实例代码分享. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Label berkaitan:
sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan