原创
  • 2020-08-04
  • 浏览 (7)
  • 评论 (0)

二叉树的前序、中序、后序非递归遍历

二叉树的遍历方法是以打印根节点的顺序来命名的。先打印根节点就叫做前序遍历,先打印左结点后打印根节点就叫做中序遍历,最后打印根节点就叫做后序遍历。以下面一颗二叉树为例,本文分析这颗二叉树前序、中序、后序非递归遍历的方法。虽然这三种遍历的策略不一样,但是遍历二叉树本质上就是递归,而递归在计算机内部就是不停的压栈,保留现场。所以我们能够很容易的想到用栈这种结构实现非递归遍历。

image
上图给出了非递归前序遍历的过程。

前序遍历

前序遍历就是对每个节点按照"根左右"的顺序进行遍历。本质上是一种递归,由于每个节点的遍历策略都是一样的,即按照"根左右"的遍历顺序。自然可以想出非递归的遍历方法。递归在计算机内部,本质上就是不停的压栈,一个一个方法往栈顶放。既然如此,那么非递归的前序遍历就可以如下表述:根节点直接打印,右结点先入栈,左结点后入栈。左结点后入栈是因为栈是一种后进先出的结构,和我们的先打印左结点,后打印右结点的策略一致。下面请看代码实现。

public static void preOrderUrec(Node head) {
    if(head != null) {
        System.out.println("preOrder:");
        Stack<Node> stack = new Stack();
        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 inOrderUrec(Node head) {
    if(head != null) {
        System.out.println("inOrder:");
        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.print(head.value + " ");
                head = head.right;
            }
        }
        System.out.println();
    }
}
二叉树的非递归中序遍历

后序遍历

后序遍历是按照"左右根"的策略进行遍历的。根据栈的后进先出特点,我们可以使用两个栈来实现先压右结点,后压左结点的进栈策略。这样在出栈时,就可以先打印左结点,后打印右结点。

public static void posOrderUnRecur1(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();
}
二叉树的非递归后序遍历
正文到此结束
该篇文章的评论功能已被站长关闭
本文目录