一、二叉樹(shù)先序遍歷：頭>左>右

1. 遞歸方式實(shí)現(xiàn)

 //先序打印 頭左右
    public static void pre(Node head) {
        if (head == null) return;
        System.out.print(head.value + ", ");
        pre(head.left);
        pre(head.right);
    }

二、 非遞歸方式實(shí)現(xiàn)

使用棧集合存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù)，完成非遞歸實(shí)現(xiàn)

1. 數(shù)據(jù)結(jié)構(gòu)

二叉樹(shù)

1.1 . 將根節(jié)點(diǎn) 1 壓入站內(nèi),進(jìn)入循環(huán)后將 1 彈出棧并打印輸出，利用棧后入先出的規(guī)則將右樹(shù)3壓入棧底，再將左樹(shù)節(jié)點(diǎn)2壓入棧，

1.2 進(jìn)入下一輪循環(huán)，將節(jié)點(diǎn)2彈出棧并輸出打印，并將節(jié)點(diǎn)2 的子節(jié)點(diǎn)5和4壓入棧(先右后左)

1.3 進(jìn)入下一輪循環(huán)，將節(jié)點(diǎn)4彈出棧并輸入打印，發(fā)現(xiàn)其左子樹(shù)節(jié)點(diǎn)和右子樹(shù)節(jié)點(diǎn)都沒(méi)值，不做任何操作。

1.4 進(jìn)入下一輪循環(huán)，將節(jié)點(diǎn)5彈出棧并輸入打印，發(fā)現(xiàn)其左子樹(shù)節(jié)點(diǎn)和右子樹(shù)節(jié)點(diǎn)都沒(méi)值，不做任何操作。

1.5 左數(shù)整體遍歷完畢，這時(shí)候棧內(nèi)只有右數(shù)節(jié)點(diǎn)3，將其彈出棧并獲取其右樹(shù)節(jié)點(diǎn)和左樹(shù)節(jié)點(diǎn)壓入棧。

1.6 后面邏輯和1.1至1.5一樣循環(huán)。代碼如下：

 public static void pre(Node head) {
        System.out.println("pre----------------");
        //非空判斷
        if (head != null) {
            // 定義一個(gè)棧集合
            Stack<Node> stack = new Stack<>();
            // 將根節(jié)點(diǎn)壓入棧
            stack.push(head);
            //循環(huán)條件-棧內(nèi)不為空的情況下繼續(xù)循環(huán)
            while (!stack.isEmpty()) {
                //彈出一個(gè)node節(jié)點(diǎn)
                head = stack.pop();
                System.out.print(head.value + ", ");
                //判斷當(dāng)前的節(jié)點(diǎn)的右節(jié)點(diǎn)是否有值，有值壓入棧
                if (head.right != null) {
                    stack.push(head.right);
                }
                //判斷當(dāng)前的節(jié)點(diǎn)的左節(jié)點(diǎn)是否有值，有值壓入棧
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
    }