Java实现二叉树的递归和非递归遍历-蒲公英云

点击进入尚硅谷数据结构和算法Java代码导航

1.1 递归前序遍历

//递归前序遍历
public void preOrderRec(Node temp) {
    if(temp == null) {
        System.out.println("BinaryTree is empty.");
    }else {
        System.out.print(temp.data + " ");
        if(temp.left != null) {
            preOrderRec(temp.left);
        }
        if(temp.right != null) {
            preOrderRec(temp.right);
        }
    }
}

1.2 非递归前序遍历算法一

算法思路：先遍历到二叉树的最左边的子节点，过程中同时打印数据被遍历的子节点并将其压栈，到末尾时依次出栈遍历右子节点。该方法将子二叉树的根节点压栈，利用根节点寻找它的右子节点。

//非递归前序遍历算法一，压栈的是每个二叉子树的根节点，利用这个根节点来找右子节点
public void preOrderNotRec2() {
    Node temp = root;
    Stack<Node> stack = new Stack<Node>();
    while(!stack.isEmpty() || temp != null) {
        if(temp != null) {
            System.out.print( temp.data + " ");
            stack.push(temp);
            temp = temp.left;
        }else {
            temp = stack.pop();
            temp = temp.right;
        }
    }
}

1.3 非递归前序遍历算法二

算法思路：
1，将根节点压栈。
2，从栈顶弹出节点，记为temp，打印temp数据，然后再将temp的右子节点和左子节点分别入栈。
3，重复步骤2直至栈空。
该算法与算法一不同之处是栈里存储的是每个子二叉树的右子节点，而不是根节点。

//非递归前序遍历算法一，压栈的是右子节点，
public void preOrderNotRec1() {
    Node temp = root;
    Stack<Node> stack = new Stack<Node>();
    stack.push(temp);
    while(!stack.isEmpty()) {
        temp = stack.pop();
        System.out.print( temp.data + " ");
        if(temp.right != null) {
            stack.push(temp.right);
        }
        if(temp.left != null) {
            stack.push(temp.left);
        }
    }
}

2.1 递归中序遍历

//递归中序遍历
public void inOrderRec(Node temp) {
    if(temp == null) {
        System.out.println("BinaryTree is empty.");
    }else {
        if(temp.left != null) {
            inOrderRec(temp.left);
        }
        System.out.print(temp.data + " ");
        if(temp.right != null) {
            inOrderRec(temp.right);
        }
    }
}

2.2 非递归中序遍历

和非递归前序遍历算法一类似，只是输出数据的位置不同。

//非递归中序遍历
public void inOrderNotRec() {
    Stack<Node> stack = new Stack<Node>();
    Node temp = root;
    while(!stack.isEmpty() || temp != null) {
        if(temp != null) {
            stack.push(temp);
            temp = temp.left;
        }else {
            temp = stack.pop();
            System.out.print(temp.data + " ");
            temp = temp.right;
        }
    }
}

3.1 递归后序遍历

//递归后序遍历
public void postOrderRec(Node temp) {
    if(temp == null) {
        System.out.println("BinaryTree is empty.");
    }else {
        if(temp.left != null) {
            postOrderRec(temp.left);
        }
        if(temp.right != null) {
            postOrderRec(temp.right);
        }
        System.out.print(temp.data + " ");
        }
}

3.2 非递归后序遍历算法一

算法思路：后序遍历的难点在于需要判断是从左子树返回还是从右子树返回。若从左子树返回则先遍历右子树，若从右子树返回直接输出。因此我们用里一个栈记录是从左子树返回还是从右子树返回。

具体思路参考：https://www.bilibili.com/video/av23885544

//非递归后序遍历算法一
public void postOrderNotRec2() {
    Stack<Node> s1 = new Stack<Node>();
    //用另一个栈记录是从左子树返回还是从右子树返回
    Stack<Boolean> s2 = new Stack<Boolean>();
    Node temp = root;
    boolean flag;
    while(!s1.isEmpty() || temp != null) {
        if(temp != null) {
            s1.push(temp);
            s2.push(false);
            temp = temp.left;
        }else {
            temp = s1.pop();
            flag = s2.pop();
            //false代表从左子树返回，此时需要先到右子树，并将tag改为true
            if(!flag) {
                s1.push(temp);
                s2.push(true);
                temp = temp.right;
            }else {
    //从右子树返回说明该节点的左右子树的遍历过了，直接输出
                System.out.print(temp.data + " ");
                //此时temp位于子二叉树的根节点，不为空，将其手动置空，否则出现死循环
                temp = null;
            }
        }
    }
}

3.3 非递归后序遍历算法二

非常巧妙，也是用两个栈。
算法思路：
1，将根节点压入栈s1。
2，从s1中弹出节点记为temp，并将temp压入栈s2。然后将temp的左子节点和右子节点分别入栈。
3，重复步骤2直至栈s1为空。
4，从栈s2中取出数据并打印，打印的顺序就是后序遍历的顺序。

//非递归后序遍历算法二
public void postOrderNotRec1() {
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();
    Node temp = root;
    s1.push(temp);
    while(!s1.isEmpty()) {
        temp = s1.pop();
        s2.push(temp);
        if(temp.left != null) {
            s1.push(temp.left);
        }
        if(temp.right != null) {
            s1.push(temp.right);
        }
    }
    while(!s2.isEmpty()) {
        System.out.print(s2.pop().data + " ");
    }
}

4 层次遍历

//层次遍历
public void levelOrder() {
    ArrayDeque<Node> quene = new ArrayDeque<Node>();
    Node temp = this.root;
    quene.add(temp);
    while(!quene.isEmpty()) {
        temp = quene.poll();
        System.out.print(temp.data + " ");
        if(temp.left != null) {
            quene.add(temp.left);
        }
        if(temp.right != null) {
            quene.add(temp.right);
        }
    }
}