二叉树算法之3-二叉树的遍历(递归、非递归)

方法一：递归遍历

public void print(Node node){
  if(node!=null){
    System.out.println(node.value);//先序遍历
    print(node.left);
    //System.out.println(node.value);//中序遍历
    print(node.right);
    //System.out.println(node.value);//后序遍历
  }
}

方法二：非递归遍历
算法思想：使用栈。

1、先序遍历
public void print(Node node){
    Stack stack=new Stack<Node<T>>();
    while(node!=null || !stack.isEmpty){
        while(node!=null){
            System.out.println(node.getValue);//先序遍历
            stack.push(node);
            node=node.left;
        }
     if(!stack.isEmpty()){
            node=stack.pop();
            System.out.println(node.value);
            node = node.right;
        }
    }
}

内层循环用来存储节点，外层循环将内层循环的存储不断地转至节点的右树中。总的思想就是先压栈，然后出栈的时候再依次压入弹出节点的右树中的左树，以此类推。

2、中序遍历
public void print(Node node){
    Stack stack=new Stack<Node<T>>();
    while(node!=null || !stack.isEmpty){
        while(node!=null){
            stack.push(node);
            node=node.left;
        }
        if(!stack.isEmpty()){
            node=stack.pop();
            System.out.println(node.value);
            node = node.right;
        }
    }
}