二叉树的遍历

谁践踏了优雅 2022-01-07 23:07 191阅读 0赞

**递归的本质是通过栈来保存状态，然后再次调用自己进入新的状态，然后函数返回的时候回到上次保存的状态。往往机器保存的状态不一定用得到，这就会造成栈资源浪费。所以要把递归改为非递归，这样自己可以设置需要保存的状态，减少栈空间的浪费。**

//树的节点类
    class Node {
    	public int val; //节点值
    	public Node left; //左子树
    	public Node right; //右子树
    	public Node() {}
    	public Node(int val, Node left, Node right) {
    		this.val = val;
    		this.left = left;
    		this.right = right;
    	}
    }

### **1、二叉树前序遍历** ###

**非递归：**

*  实现思路，先序遍历是要先访问根节点，然后再去访问左子树以及右子树，这明显是递归定义，但这里是用栈来实现的
 *  首先需要先从栈顶取出节点，然后访问该节点，如果该节点不为空，则访问该节点，同时把该节点的右子树先入栈，然后
 *  左子树入栈。循环结束的条件是栈中不在有节点。即 !s.empty()。

public void preOrder(Node root) {
        if (root == null) return;
        Stack<Node> s = new Stack<Node>();
        s.push(root);
        while (!s.empty()) {
            root = s.pop();
            System.out.print(root.val + " ");
            if(root.right!=null){
                s.push(root.right);
            }            
            if(root.left!=null){
                s.push(root.left);
            }
        }
    }

**递归：**

public static void preOrder(Node root){
    		if(root != null){
    			System.out.print(root.val + " ");
    			preOrder(root.left);
    			preOrder(root.right);
    		}
    	}

### 2、二叉树的中序遍历 ###

**非递归：**

*  实现思路，中序遍历是要先遍历左子树，然后跟节点，最后遍历右子树。所以需要先把跟节点入栈然后在一直把左子树入栈
 *  直到左子树为空，此时停止入栈。栈顶节点就是我们需要访问的节点，取栈顶节点p并访问。然后改节点可能有右子树，所以
 *  访问完节点p后还要判断p的右子树是否为空，如果为空则接下来要访问的节点在栈顶，所以将p赋值为null。如果不为空则
 *  将p赋值为其右子树的值。 循环结束的条件是p不为空或者栈不为空。

public void inOrder(Node root) {
        if (root == null) return;
        Stack<Node> s = new Stack<Node>();
        while (!s.isEmpty() || root != null) {
            if(root != null){   // 入栈
                s.push(root);
                root = root.left;
            }else {   // 打印
                root = s.pop();
                System.out.println(root.val);
                root = root.right;
            }
        }
    }

**递归实现：**

public static void inOrder(TreeNode root){
    		if(root != null){
    			inOrder(root.left);
    			System.out.print(root.val + " ");
    			inOrder(root.right);
    		}
    	}

### 3、二叉树的后序遍历 ###

**非递归实现：**

*  实现思路，在进行后序遍历的时候是先要遍历左子树，然后在遍历右子树，最后才遍历根节点。所以在非递归的实现中要先把根节点入栈
 *  然后再把左子树入栈直到左子树为空，此时停止入栈。此时栈顶就是需要访问的元素，所以直接取出访问p。在访问结束后，还要判断被访问的节点p是否为栈顶节点的左子树，如果是的话那么还需要访问栈顶节点的右子树，所以将栈顶节点的右子树取出赋值给p。如果不是的话则说明栈顶节点的右子树已经访问完了，那么现在可以访问栈顶节点了，所以此时将p赋值为null。判断结束的条件是p不为空或者栈不为空，若果两个条件都不满足的话，说明所有节点都已经访问完成。

public static void process(Node root) {
            if (root == null) {
                return;
            }
            Stack<Node> s1 = new Stack<>();
            Stack<Node> s2 = new Stack<>();
            s1.push(root);
            while (!s1.empty()) {
                root = s1.pop();
                s2.push(root);
                if (root.left != null) {
                    s1.push(root.left);
                }
                if (root.right != null) {
                    s1.push(root.right);
                }
            }
    
            while (!s2.empty()) {
                System.out.println(s2.pop().value);
            }
        }

**递归实现：**

public static void postOrder(TreeNode root){
    		if(root != null){
    			postOrder(root.left);
    			postOrder(root.right);
    			System.out.print(root.val + " ");
    		}
    	}

### 4、层次遍历 ###

树的层次遍历，故名思议，在一棵树中，把节点从左往右，一层一层的，从上往下，遍历输出，这里要用到一种很重要的数据结构，队列，一提到队列，我们就要想到先进先进先，即为先进入队列元素，先接受处理，我们在日常生活中排队时，就是先到的人，先接受服务。

理解好队列，可以很容易的解决树的层此遍历，步骤如下：

*   1.首先将根节点放入队列中。
 *   2.当队列为非空时，循环执行步骤3到步骤5，否则执行6；
 *   3.出队列取得一个结点，访问该结点；
 *   4.若该结点的左子树为非空，则将该结点的左子树入队列；
 *   5.若该结点的右子树为非空，则将该结点的右子树入队列；
 *   6.结束。

private static void levelOrder(TreeNode root) {
    		Queue<TreeNode> queue = new LinkedList<TreeNode>();
    		if(root == null)
    			return;
    		queue.offer(root);
    		while(!queue.isEmpty()){
    			TreeNode temp  = queue.poll();
    			System.out.print(temp.val + " ");
    			if(temp.left != null)
    				queue.offer(temp.left);
    			if(temp.right != null)
    				queue.offer(temp.right);
    		}
    	}

### 整个程序完整的代码 ###

package cn.edu.ahui;
    
    import cn.edu.ahui.TreeNode;
    import java.util.*;
     
    public class BTraversal{
    	//递归实现二叉树的前序遍历
    	public static void preOrder(TreeNode root){
    		if(root != null){
    			System.out.print(root.val + " ");
    			preOrder(root.left);
    			preOrder(root.right);
    		}
    	}
    	
    	//非递归实现前序遍历
    	public static ArrayList preOrder1(TreeNode root){
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		ArrayList alist = new ArrayList();
    		TreeNode p = root;
    		while(p != null || !stack.empty()){
    			while(p != null){
    				alist.add(p.val);
    				stack.push(p);
    				p = p.left;
    			}
    			if(!stack.empty()){
    				TreeNode temp = stack.pop();
    				p = temp.right;
    			}
    		}
    		return alist;
    	}
    	
    	//递归实现中序遍历
    	public static void inOrder(TreeNode root){
    		if(root != null){
    			inOrder(root.left);
    			System.out.print(root.val + " ");
    			inOrder(root.right);
    		}
    	}
    	//非递归实现中序遍历
    	public static ArrayList inOrder1(TreeNode root){
    		ArrayList alist = new ArrayList();
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		TreeNode p = root;
    		while(p != null || !stack.empty()){
    			while(p != null){
    				stack.push(p);
    				p = p.left;
    			}
    			if(!stack.empty()){
    				TreeNode temp = stack.pop();
    				alist.add(temp.val);
    				p = temp.right;
    			}
    		}
    		return alist;
    	}
        //递归实现二叉树的后序遍历
    	public static void postOrder(TreeNode root){
    		if(root != null){
    			postOrder(root.left);
    			postOrder(root.right);
    			System.out.print(root.val + " ");
    		}
    	}
    	//非递归实现二叉树的后续遍历
    	public static ArrayList postOrder1(TreeNode root){
    		ArrayList alist = new ArrayList();
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		if(root == null)
    			return alist;
    		TreeNode cur,pre = null;
    		stack.push(root);
    		while(!stack.empty()){
    			cur = stack.peek();
    			if((cur.left == null && cur.right == null) || (pre != null && (cur.left == pre || cur.right == pre))){
    				TreeNode temp = stack.pop();
    				alist.add(temp.val);
    				pre = temp;
    			}
    			else{
    				if(cur.right != null)
    					stack.push(cur.right);
    				if(cur.left != null)
    					stack.push(cur.left);
    			}
    		}
    		return alist;
    	}
    	//非递归实现二叉树的层次遍历
    	private static void levelOrder(TreeNode root) {
    		Queue<TreeNode> queue = new LinkedList<TreeNode>();
    		if(root == null)
    			return;
    		queue.offer(root);
    		while(!queue.isEmpty()){
    			TreeNode temp  = queue.poll();
    			System.out.print(temp.val + " ");
    			if(temp.left != null)
    				queue.offer(temp.left);
    			if(temp.right != null)
    				queue.offer(temp.right);
    		}
    	}
    }

参考：[https://blog.csdn.net/u011514810/article/details/75907170][https_blog.csdn.net_u011514810_article_details_75907170]

[https_blog.csdn.net_u011514810_article_details_75907170]: https://blog.csdn.net/u011514810/article/details/75907170