BLOG

BLOG

二叉树的非递归遍历

算法
479
2021-03-30

二叉树的非递归遍历

树的结构

设计一个遍历的接口

import java.util.List;

public interface TreeNodeIterator {
    List<Integer> traversal(TreeNode root);
}

设计一个树节点

import com.sun.source.tree.BinaryTree;

import java.util.List;

public class TreeNode {
    public Integer val;
    public TreeNode left;
    public TreeNode right;

    
    public List<Integer> traversal(TreeNodeIterator iterator) {
        return iterator.traversal(this);
    }

    public TreeNode() {
    }

    public TreeNode(Integer val) {
        this.val = val;
    }

    public TreeNode(Integer val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    //设计一个静态的测试用例方便调用
    static TreeNode test = new TreeNode(1);

    static {
        test.left = new TreeNode(2);
        test.right = new TreeNode(3);
        test.right.left = new TreeNode(4);
        test.right.right = new TreeNode(5);
    }
}

测试的树结构：

	    1
	  /   \
         2     3
             /   \
            4     5

前序遍历

递归的实现

二叉树前序递归遍历比较简单，这里不作赘述，请看代码：

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

public class Preorder implements TreeNodeIterator {
    private List<Integer> content;

    @Override
    public List<Integer> traversal(TreeNode root) {
        content = new ArrayList<>();
        if(root == null){
            return  content;
        }
        search(root);
        return content;
    }

    private void search(TreeNode node) {
        content.add(node.val);
        //遍历左子树
        if (node.left != null) {
            search(node.left);
        }
        //遍历右子树
        if (node.right != null) {
            search(node.right);
        }
    }

    public static void main(String[] args) {
        List<Integer> content = TreeNode.test.traversal(new Preorder());
        content.forEach((x) -> System.out.print(x + " "));
    }
}


输出结果：
1 2 3 4 5

非递归的实现

具体步骤和思想

  1. 初始化树的节点root，将root视作当前节点
  2. 遍历当前节点的左子树，依次入栈以及加入到结果队列，直到当前节点为null
  3. 如果栈未空出栈一个节点，将这个节点视为当前节点，但是这个节点入栈的过程中遍历过了，我们遍历他的右子树，因此将当前节点指向他的右子树
  4. 重复步骤2，3
  5. 直到栈空且当前节点为null

具体代码

写法一

这种写法比较贴合上面的步骤和思想：

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class PreorderNonRecursive implements TreeNodeIterator {

    @Override
    public List<Integer> traversal(TreeNode root) {
        List<Integer> content = new ArrayList<>();
        if (root == null) {
            return content;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        while(!stack.isEmpty() || root!=null){
            while(root!=null){
                content.add(root.val);
                stack.addLast(root);
                root = root.left;
            }
            root = stack.pollLast();
            root = root.right;
        }
        return content;
    }

    public static void main(String[] args) {
        List<Integer> content = TreeNode.test.traversal(new PreorderNonRecursive());
        content.forEach((x)-> System.out.print(x+" "));
    }
}

写法二

这种写法比较抽象，总的来说就是既然我们要先遍历左子树，后遍历右子树，那么我们就依赖栈先进先出，后进后出的特点，先加入右子树就好了,代码如下：

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class PreorderNonRecursive implements TreeNodeIterator {

    @Override
    public List<Integer> traversal(TreeNode root) {
        List<Integer> content = new ArrayList<>();
        if (root == null) {
            return content;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        stack.addLast(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pollLast();
            content.add(node.val);
            if(node.right!=null){
                stack.addLast(node.right);
            }
            if(node.left!=null){
                stack.addLast(node.left);
            }
        }
        return content;
    }

    public static void main(String[] args) {
        List<Integer> content = TreeNode.test.traversal(new PreorderNonRecursive());
        content.forEach((x)-> System.out.print(x+" "));
    }
}


输出结果：
1 2 3 4 5

中序遍历

递归的实现

二叉树的递归中序遍历比较简单，这里不作赘述，请看代码：

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

public class Inorder implements TreeNodeIterator {
    private List<Integer> content;

    @Override
    public List<Integer> traversal(TreeNode root) {
        content = new ArrayList<>();
        if(root == null){
            return  content;
        }
        search(root);
        return content;
    }

    private void search(TreeNode node) {
        //遍历左子树
        if (node.left != null) {
            search(node.left);
        }
        content.add(node.val);
        //遍历右子树
        if (node.right != null) {
            search(node.right);
        }
    }

    public static void main(String[] args) {
        List<Integer> content = TreeNode.test.traversal(new PreorderNonRecursive());
        content.forEach((x) -> System.out.print(x + " "));
    }
}

非递归的实现

具体的步骤和思想

  1. 初始化树的节点root，将root视作当前节点
  2. 遍历当前节点的左子树，依次入栈，直到当前节点为null
  3. 出栈一个节点，并且将该节点加入到结果队列，如果节点的右子树不为空，则遍历右子树，即将当前节点指向节点的右子树
  4. 重复步骤2，3
  5. 直到栈空且当前节点为null

具体代码

import java.util.*;

public class InorderNonRecursive implements TreeNodeIterator {

    @Override
    public List<Integer> traversal(TreeNode root) {
        List<Integer> content = new ArrayList<>();
        if(root == null){
            return  content;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.addLast(root);
                root = root.left;
            }
            root = stack.pollLast();
            content.add(root.val);
            root = root.right;
        }
        return  content;

    }

    public static void main(String[] args) {
        List<Integer> content = TreeNode.test.traversal(new InorderNonRecursive());
        content.forEach((x) -> System.out.print(x + " "));
    }
}


输出结果：
2 1 4 3 5

后序遍历

递归的实现

二叉树的递归后序遍历比较简单，这里不作赘述，请看代码：

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

public class Postorder implements TreeNodeIterator {
    private List<Integer> content;

    @Override
    public List<Integer> traversal(TreeNode root) {
        content = new ArrayList<>();
        if(root == null){
            return  content;
        }
        search(root);
        return content;
    }

    private void search(TreeNode node) {
        //遍历右子树
        if (node.left != null) {
            search(node.left);
        }
        //遍历左子树
        if (node.right != null) {
            search(node.right);
        }
        content.add(node.val);
    }

    public static void main(String[] args) {
        List<Integer> content = TreeNode.test.traversal(new Postorder());
        content.forEach((x) -> System.out.print(x + " "));
    }
}

非递归的实现

具体步骤和思想

二叉树的非递归后序遍历相对中序和前序要复杂一点，因为要先遍历完左右子树再遍历中间节点，这就需要我们将中间节点入栈两次，并且需要识别中间节点是否已经遍历完左右子树了，因此我们加入一个前缀节点做记录，具体步骤如下：

  1. 初始化树的节点root和前置节点prev，将root视作当前节点
  2. 遍历当前节点的左子树，依次入栈，直到当前节点为null
  3. 出栈一个节点
  4. 如果当前节点的右节点为空或者右节点等于前置节点（说明右子树已经被遍历了），将当前节点加入的结果队列，更新前置节点为当前节点，将当前节点置空，避免再次遍历该节点的左子树
  5. 如果当前节点的右节点不为空，将当前节点再次入栈，并且将当前节点指向右节点
  6. 重复2，3 ，4 ，5
  7. 直到栈空且当前节点为null

具体代码

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class PostorderNonRecursive implements TreeNodeIterator {

    @Override
    public List<Integer> traversal(TreeNode root) {
        List<Integer> content = new ArrayList<>();
        if (root == null) {
            return content;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.addLast(root);
                root = root.left;
            }
            root = stack.pollLast();
            // 如果当前节点的右节点为空或者，该节点的左右子树已经被遍历过了
            if (root.right == null || root.right == prev) {
                content.add(root.val);  //加入到结果队列
                prev = root;    //将当前节点作为前置节点，如果下一次遍历的节点的右节点和该节点相同说明其右子树已经被遍历u过了
                root = null;    //将当前节点置空，避免再次遍历该节点的左子树
            } else {  //如果当前节点的右节点不为空，遍历右边子树
                stack.addLast(root);
                root = root.right;
            }
        }
        return content;
    }

    public static void main(String[] args) {
        List<Integer> content = TreeNode.test.traversal(new PostorderNonRecursive());
        content.forEach((x)-> System.out.print(x+" "));
    }
}


输出结果：
2 4 5 3 1
#算法 1 #二叉树 1
Vagrant虚拟机管理工具使用
如何应对ArchLinux"挂掉"