二叉树的遍历(递归,非递归)的实现

二叉树的遍历(前序,中序,后序)的递归与非递归遍历

二叉树的java数据结构定义

1
2
3
4
5
6
7
8
9
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

TreeNode(int val) {
this.val = val;
}
}

前序遍历

先访问根节点,再访问左子节点,再访问右子节点,中,左,右

递归方式

递归实现的方法,在每次访问到某个节点的时候,先输出节点值,然后在依次左儿子、右儿子调用遍历的方法

1
2
3
4
5
6
7
8
9
public class preOrderRecur {
void preOrderRecur(TreeNode root){
if(root==null)
return;
System.out.print(root.val);
preOrderRecur(root.left);
preOrderRecur(root.right);
}
}

非递归方式

  • 方法1

设置一个栈,将根节点压入栈中,此后,每从栈中读出栈的顶节点,作为对该节点的访问,然后将该节点的儿子按照先右后左的方式,压入栈中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class preOrderNonRecur {
void preOrderRecur(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode t=stack.pop();
System.out.print(t.val+" ");
if(t.right!=null)
stack.push(t.right);
if(t.left!=null)
stack.push(t.left);
}
}
}
  • 方法2

    1. 建立一个栈stack和一个当前节点node,初始化时将node赋值为根节点
    2. 逐个访问当前节点的左儿子的节点,并推入到栈中,直到没有左节点
    3. 取出栈顶的节点,将node赋值为节点的右儿子
    4. 执行2、3,直到当前节点为空且栈也为空
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void preOrderRecur2(TreeNode root){
    Stack<TreeNode>stack=new Stack<>();
    TreeNode node=root;
    while(node!=null||!stack.isEmpty()){
    while (node!=null){
    System.out.print(node.val+" ");
    stack.push(node);
    node=node.left;
    }
    if(!stack.isEmpty()){
    node=stack.pop();
    node=node.right;
    }
    }
    }

中序遍历

先访问左子节点,再访问根节点,最后访问右子节点,左,中,右

递归方式

先遍历左子树,再打印头结点的值,最后遍历右子树

1
2
3
4
5
6
7
8
9
public class inorderTrav {
void inorderTrav(TreeNode root){
if(root!=null){
inorderTrav(root.left);
System.out.print(root.val+" ");
inorderTrav(root.right);
}
}
}

非递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class inorderTravNoRecur {
void inorderTravNoRecur (TreeNode root){
Stack<TreeNode>stack=new Stack<TreeNode>();
TreeNode node=root;
while(node!=null||!stack.isEmpty()){
while (node!=null){
stack.push(node);
node=node.left;
}
if(!stack.isEmpty()){
node=stack.pop();
System.out.print(node.val);
node=node.right;
}
}
}
}

思路:和非递归先序遍历相似,区别是考察到当前节点时,并不输出该节点。而是到考察节点为空时,从栈中弹出时候在进行弹出(永远先考虑左子树,直到左子树为空时才访问根节点)

后序遍历

先访问左子节点,再访问右子节点,最后访问根节点,左,右,中

递归方式

先遍历左子树,在遍历右子树,最后打印结点

1
2
3
4
5
6
7
8
9
public class postOrderTrav {
void postOrderTrav(TreeNode root){
if(root!=null){
postOrderTrav(root.left);
postOrderTrav(root.right);
System.out.println(root.val+" ");
}
}
}

非递归方式

  1. 后序遍历在决定是否可以输出当前节点值的时候,需要考虑其左右子树是否都已经遍历完成,需要设置一个lastVisit游标
  2. 若lastVisit等于当前考察节点的右子树,表示该节点的左右子树都已经遍历完成,则可以输出当前节点
  3. 把lastVisit节点设置为当前节点,将当前游标节点node设置为空,下一轮就可以访问栈顶元素
  4. 否则,需要接着考虑右子树,node=node.right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class postOrderTravNoRecu {
void postOrderTravNoRecu(TreeNode root){
Stack<TreeNode> treeNodeStack=new Stack<TreeNode>();
TreeNode node=root;
TreeNode lastvisit=root;
while(node!=null||treeNodeStack.isEmpty()){
while (node!=null){
treeNodeStack.push(node);
node=node.left;
}
//查看当前栈顶元素
node=treeNodeStack.peek();
//如果其右子树也为空,或者右子树已经访问,则可以直接输出当前节点的值
if(node.right==null||node.right==lastvisit){
System.out.print(node.val+" ");
treeNodeStack.pop();
lastvisit=node;
node=null;
}else {
node=node.right;
}
}
}
}