二叉树的递归和非递归遍历

package tree;

import java.util.Stack;

class treenode<T> {
    T value;
    treenode left;
    treenode right;

    public treenode(T value) {
        this.value = value;
    }
}

public class treebianli {
    public static void main(String[] args) {
        treenode node1 = new treenode(1);
        treenode node2 = new treenode(2);
        treenode node3 = new treenode(3);
        treenode node4 = new treenode(4);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        pre(node1);
//        preunrecur(node1);
//        posunrecur(node1);

        inunrecur(node1);
    }

    //递归
    static void pre(treenode root) {
        if (root == null) {
            return;
        }
        pre(root.left);
        System.out.print(root.value);
        pre(root.right);


    }

    //二叉树非递归遍历
    static void preunrecur(treenode root) {
        System.out.println("二叉树非递归遍历");
        if (root == null) {
            return;
        }
        Stack<treenode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {//栈为空就截至循环
            treenode treenode = stack.pop();
            System.out.print(treenode.value);//出栈打印!!
            if (treenode.right != null) {//先看右子树 不为空就压栈
                stack.push(treenode.right);
            }
            if (treenode.left != null) {//再看左子树 不为空就压栈
                stack.push(treenode.left);
            }
        }
    }

    static void inunrecur(treenode root) {
        System.out.println("中序非递归-----");
        if (root == null) {
            return;
        }
        Stack<treenode> stack = new Stack<>();
        treenode node = root;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {//左边不为空就一直向下
                stack.push(node);
                node = node.left;
            } else {//左边为空 先出栈打印 然后node指向出栈节点的右边
                treenode pop = stack.pop();
                System.out.print(pop.value);
                node = pop.right;
            }
        }
    }

    static void posunrecur(treenode root) {//后序  把先序左右换过来 然后拿一个栈来存最后打印
        System.out.println("非递归后序遍历");
        if (root == null) {
            return;
        }
        Stack<treenode> stack1 = new Stack<>();
        stack1.push(root);//坑! 先把根节点压进去
        Stack<treenode> stack2 = new Stack<>();
        while (!stack1.isEmpty()) {
            treenode treenode = stack1.pop();
            stack2.push(treenode);//存入另外一个栈
            if (treenode.left != null) {//先进左 再进右
                stack1.push(treenode.left);
            }
            if (treenode.right != null) {
                stack1.push(treenode.right);
            }
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().value);
        }
    }
}

中序遍历多给一条指针parent
区别: 就是打印时你要判断一下是 不是左边上来的 是左边上来的话就要打印;

package tree;

import java.util.LinkedList;

public class treewidth {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }


    //二叉树的宽度优先遍历
    static void width(Node root) {
        if (root == null) {
            return;
        }
        LinkedList<Node> queue = new LinkedList<Node>();
//用linkedlist 当作队列 先进先出
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.value);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        node.left = node2;
        node.right = node3;
        node2.right = node4;
        node2.left = node5;
        node3.right = node6;
        node5.left = node7;
        width(node);
    }
}


//变式 统计最大宽度