菜鸟笔记
提升您的技术认知

二叉树的前序、中序、后序

一、概念

二叉树遍历分为三种:前序、中序、后序,其中序遍历最为重要。

二、特点

A:根节点、B:左节点、C:右节点;

  • 前序顺序是ABC(根节点排最先,然后同级先左后右);
  • 中序顺序是BAC (先左后根最后右);
  • 后序顺序是BCA(先左后右最后根)。

三、图

四、代码实现

递归方式

第一步: 节点实体类

package node.tree;

public class Node {
  

    private String value;
    private  Node left;
    private  Node right;

    public String getValue() {
  
        return value;
    }

    public void setValue(String value) {
  
        this.value = value;
    }

    public Node getLeft() {
  
        return left;
    }

    public void setLeft(Node left) {
  
        this.left = left;
    }

    public Node getRight() {
  
        return right;
    }

    public void setRight(Node right) {
  
        this.right = right;
    }

    public Node(String value, Node left, Node right) {
  
        this.value = value;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
  
        return "Node{" +
                "value='" + value + '\'' +
                ", left=" + left +
                ", right=" + right +
                '}';
    }

}

二:节点数和核心处理类

package node.tree;

import java.util.ArrayList;
import java.util.List;

public class Tree {
  
    private Node root;
    private List<Node> result=new ArrayList<Node>();

    public Node getRoot() {
  
        return root;
    }

    public void setRoot(Node root) {
  
        this.root = root;
    }

    public List<Node> getResult() {
  
        return result;
    }

    public void setResult(List<Node> result) {
  
        this.result = result;
    }
    public Tree(){
  
        init();
    }

    private void init() {
  
        Node g=new Node("G",null,null);
        Node x=new Node("X",null,null);
        Node y=new Node("Y",null,null);
        Node d=new Node("D",x,y);
        Node b=new Node("B",d,null);
        Node e=new Node("E",g,null);
        Node f=new Node("F",null,null);
        Node c=new Node("C",e,f);
        Node a=new Node("A",b,c);
        root=a;
    }

    /**
     * 计算深度
     * @param node
     * @return
     */
    public int calDepth(Node node){
  
        if (node.getLeft()==null&&node.getRight()==null){
  
            return 1;
        }
        int leftDepth=0;
        int rightDepth=0;
        if(node.getLeft()!=null){
  
            leftDepth=calDepth(node.getLeft());
        }
        if(node.getRight()!=null){
  
            rightDepth=calDepth(node.getRight());
        }
        System.out.println("左"+leftDepth+"右"+rightDepth);
        int temp=leftDepth>rightDepth?leftDepth+1:rightDepth+1;
        System.out.println("中间计算结果"+temp);
        return temp;
    }
    //前序遍历  根左右
    public void perOrder(Node root){
  
        if(root==null){
  
            return;
        }
        result.add(root);
        if(root.getLeft()!=null){
  
            perOrder(root.getLeft());
        }
        if(root.getRight()!=null){
  
            perOrder(root.getRight());
        }
    }
    //中序遍历   左根右
    public void InMiddleOrder(Node root){
  
        if(root==null){
  
            return;
        }
        if(root.getLeft()!=null){
  
            InMiddleOrder(root.getLeft());
        }
        result.add(root);
        if(root.getRight()!=null){
  
            InMiddleOrder(root.getRight());
        }
    }
    //后序遍历   左右根
    public void LastOrder(Node root){
  
        if(root==null){
  
            return;
        }
        if(root.getLeft()!=null){
  
            LastOrder(root.getLeft());
        }
        if(root.getRight()!=null){
  
            LastOrder(root.getRight());
        }
        result.add(root);
    }





}

三:测试类

package node.tree;

public class Test {
  

    public static void main(String[] args) {
  
        Tree tree=new Tree();
        System.out.println("根节点"+tree.getRoot().getValue());
        //先序遍历
        tree.perOrder(tree.getRoot());
        System.out.println("树的深度是"+tree.calDepth(tree.getRoot()));
        System.out.println("先序遍历结果是:");
        for (Node node  :tree.getResult() ) {
  
            System.out.print(node.getValue()+" ");
        }
        System.out.println("");
        tree.getResult().clear();
        tree.InMiddleOrder(tree.getRoot());
        System.out.println("中序遍历结果是:");
        for (Node node  :tree.getResult() ) {
  
            System.out.print(node.getValue()+" ");
        }
        System.out.println("");
        tree.getResult().clear();
        tree.LastOrder(tree.getRoot());
        System.out.println("后序遍历结果是:");
        for (Node node  :tree.getResult() ) {
  
            System.out.print(node.getValue()+" ");
        }

    }

}

非递归方式实现

前序遍历:

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

		public Node(int v) {
  
			value = v;
		}
	}

	//	Object peek( )
	//	查看堆栈顶部的对象,但不从堆栈中移除它。
	//	Object pop( )
	//	移除堆栈顶部的对象,并作为此函数的值返回该对象。
	//	Object push(Object element)
	//	把项压入堆栈顶部。

	// 先头节点,先压右,后压左
	public static void pre(Node head) {
  
		// 压栈
		System.out.print("pre-order: ");
		if (head != null) {
  
			Stack<Node> stack = new Stack<Node>();
			stack.add(head);
			while (!stack.isEmpty()) {
  
				// 弹出来
				head = stack.pop();
				System.out.print(head.value + " ");
				if (head.right != null) {
  
					// 压右
					stack.push(head.right);
				}
				if (head.left != null) {
  
					// 压右
					stack.push(head.left);
				}
			}
		}
		System.out.println();
	}

后序遍历方式:


	public static void pos1(Node head) {
  
		System.out.print("pos-order: ");
		if (head != null) {
  
			Stack<Node> s1 = new Stack<Node>();
			Stack<Node> s2 = new Stack<Node>();
			s1.push(head);
			while (!s1.isEmpty()) {
  
				head = s1.pop(); // 头 右 左
				s2.push(head);
				if (head.left != null) {
  
					s1.push(head.left);
				}
				if (head.right != null) {
  
					s1.push(head.right);
				}
			}
			// 左 右 头
			while (!s2.isEmpty()) {
  
				System.out.print(s2.pop().value + " ");
			}
		}
		System.out.println();
	}

这里后序遍历其实跟前序遍历是一样的,前序遍历是根,左,右。后序是根,右,左
其实只需要再加一个栈来区别他是左边的还是右边的就好。

中序遍历方式:


	public static void in(Node cur) {
  
		System.out.print("in-order: ");
		if (cur != null) {
  
			Stack<Node> stack = new Stack<Node>();
			while (!stack.isEmpty() || cur != null) {
  
				if (cur != null) {
  
					// head整条左边树进栈,除去空的情况
					stack.push(cur);
					cur = cur.left;
				} else {
  
					// 右节点为空的时候弹出打印
					// 从栈中弹出节点打印,这个节点的右孩子为cur
					cur = stack.pop();
					System.out.print(cur.value + " ");
					cur = cur.right;
				}
			}
		}
		System.out.println();
	}

中序先将左树全部进栈,右节点为空的时候就弹出,在把当前节点给到他的左父节点。

后序遍历的话其实也可以用一个栈来实现:


	// 一个栈实现
	public static void pos2(Node h) {
  
		System.out.print("pos-order: ");
		if (h != null) {
  
			Stack<Node> stack = new Stack<Node>();
			stack.push(h);
			Node c = null;
			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.print(stack.pop().value + " ");
					h = c;
				}
			}
		}
		System.out.println();
	}


	public static void main(String[] args) {
  
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);

		pre(head);
		System.out.println("========");
		in(head);
		System.out.println("========");
		pos1(head);
		System.out.println("========");
		pos2(head);
		System.out.println("========");
	}