二叉树的先序、中序、后序遍历

public static class Traverse {
        public static void preOrderRecur(Node head) {
						//递归实现
            if (head == null) {
                return;
            }
            System.out.println(head.value);
            preOrderRecur(head.left);
            preOrderRecur(head.right);
        }

        public static void inorderRecur(Node head) {
            if (head == null) {
                return;
            }
            inorderRecur(head.left);
            System.out.println(head.value);
            inorderRecur(head.right);
        }

        public static void posOrderRecur(Node head) {
            if (head == null) {
                return;
            }
            posOrderRecur(head.left);
            posOrderRecur(head.right);
            System.out.println(head.value);
        }

        public static void preOrderUnRecur(Node head) {
				//前序的非递归实现，用一个栈，每次弹出一个节点并打印值，并先后压入它的右边和左边孩子
            if (head == null) {
                return;
            }
            Stack<Node> stack = new Stack<>();
            stack.push(head);
            Node cur = null;
            while (!stack.isEmpty()) {
                cur = stack.pop();
                System.out.println(cur.value);
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }

        public static void inOrderUnRecur(Node head) {
            if (head == null) {
                return;
            }
					// 用一个栈和一个指针，指针最开始指向头结点，每次循环都向左移动，若指针指向非空，则把指针指向元素压入栈
					//若指针指向空，则弹出栈顶元素，并让指针指向栈顶元素的右孩子，并继续循环
            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.println(head.value);
                    head = head.right;
                }
            }
        }

        public static void posOrderUnRecur1(Node head) {
					//每次先弹出栈顶元素，并压入栈2，栈1则先后压入左右节点
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();
            stack1.push(head);
            while (!stack1.isEmpty()) {
                head = stack1.pop();
                stack2.push(head);
                if (head.left != null) {
                    stack1.push(head.left);
                }
                if (head.right != null) {
                    stack1.push(head.right);
                }
            }
            while(!stack2.isEmpty()){
                System.out.println(stack2.pop().value);
            }
        }
        public static void posOrderUnRecur2(Node head){
					//h保留最近刚弹出的元素
					//c保留栈顶元素
					//若c的左右孩子非空，并都不等于h节点，则说明c的左右节点还没入栈，压入c的左孩子
					//若c的左右孩子非空，右孩子不等于h节点，则说明c的右节点还没入栈，压入c的右孩子
					//c的左右孩子均为空，或c右节点刚弹出（即等于h），则弹出c，打印c
            Stack<Node> stack=new Stack<>();
            Node h=head;
            Node c=null;
            stack.push(head);
            while(!stack.isEmpty()){
                c=stack.peek();
                if(c.left!=null&&h!=c.left&&h!=c.right){
                    stack.push(c.left);
                }else if(c.right!=null&&h!=c.right){
                    stack.push(c.right);
                }else{
                    System.out.println(stack.pop().value);
                    h=c;
                }
            }
        }
    }

打印二叉树边界

public static class printEdgeNode{
        //打印二叉树的边界节点
        public static void printEdge1(Node head){
            int h=getHeight(head,0);
            Node [][] edgemap=new Node[h][2];
            setEdgeMap(head,0,edgemap);
            for (int i = 0; i < h; i++) {
                System.out.println(edgemap[i][0].value);
            }
            printLeafNotInMap(head,0,edgemap);
            for (int i = 0; i < h; i++) {
                if(edgemap[i][0]!=edgemap[i][1]){
                System.out.println(edgemap[i][1].value);}
            }
        }
        public static int getHeight(Node head,int l){
					//获取当前节点的深度，祖先节点为0
            if(head==null){
                return l;
            }
            return Math.max(getHeight(head.left,l+1),getHeight(head.right,l+1));
        }
        public static void setEdgeMap(Node head,int l,Node[][] edgeMap){
					//由于是树形递归，最先递归到的节点，必定为最左边的节点
					//而最后递归到的必定为最右边节点
            if(head==null) return;
            edgeMap[l][0]=edgeMap[l][0]==null? head:edgeMap[l][0];
            edgeMap[l][1]=head;
            setEdgeMap(head.left,l+1,edgeMap);
            setEdgeMap(head.right,l+1,edgeMap);
        }
        public static void printLeafNotInMap(Node head,int l,Node [][] m){
				//寻找不在左右上的叶子节点
            if(head==null) return;
            if(head.left==null&head.right==null&&m[l][0]!=head&&m[l][1]!=head){
                System.out.println(head.value);
            }
            printLeafNotInMap(head.left,l+1,m);
            printLeafNotInMap(head.right,l+1,m);
        }
    }