数据结构——二叉树的遍历

一、二叉树的前序、中序、后序遍历的递归、非递归、迭代器版本

(1)Tree.java

package com.zx.tree;

import java.util.Stack;

public class Tree {
	
	private Node root;
	private Integer[] ans;
	private Integer size;
	private Integer cnt;
	
	public Tree(){
		root = null;
		ans = null;
		size = null;
		cnt = null;
	}
	
	public Tree(Integer[] ans){
		this.ans=ans;
		size=this.ans.length;
		cnt = null;
		root = build(0);
	}
	
	private Node build(Integer pos){
		Node node = new Node();
		node.setData(ans[pos]);
		if(pos*2+1 stack = new Stack<>();
		
		Node p = root;
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				visit(p);
				stack.add(p);
				p = p.getLnode();
			}
			else
			{
				p = stack.pop();
				p = p.getRnode();
			}
		}
		return ans;
	}
	
	
	//----------------------------------------------------------------------
	//非递归形式中续遍历
	public Integer[] stackMidList() {
		reset();
		Stack stack = new Stack<>();
		
		Node p = root;
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				stack.add(p);
				p = p.getLnode();
			}
			else
			{
				p = stack.pop();
				visit(p);
				p = p.getRnode();
			}
		}
		return ans;
	}
	
	
	//----------------------------------------------------------------------
	//非递归形式后续遍历
	public Integer[] stackLastList() {
		reset();
		Stack stack = new Stack<>();
		
		Node p = root;
		//后续遍历为左右根
		//r表示上一个访问的节点，用来判断是不是从右子树返回的
		Node r = null;
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				stack.add(p);
				p = p.getLnode();
			}
			else
			{
				//查看栈顶
				p = stack.peek();
				
				if(p.getRnode() != null && p.getRnode() != r)//右子树存在且未被访问过
				{
					p = p.getRnode();
					stack.add(p);
					p = p.getLnode();
				}
				else
				{
					p = stack.pop();
					visit(p);
					r = p;
					//访问完以p为根的子树
					p = null;
				}
			}
		}
		return ans;
	}
	
	
	
	
	//利用迭代器实现遍历
	//采用非递归形式
	public Iter getPreIter() {
		return new PreIter(root);
	}
	
	public Iter getMidIter() {
		return new MidIter(root);
	}
	
	public Iter getLastIter() {
		return new LastIter(root);
	}
	
}


class Node
{
	private Integer data;
	private Node lnode;
	private Node rnode;
	
	public Node() {
		data = null;
		lnode = null;
		rnode = null;
	}
	
	public Integer getData() {
		return data;
	}
	public void setData(Integer data) {
		this.data = data;
	}
	public Node getLnode() {
		return lnode;
	}
	public void setLnode(Node lnode) {
		this.lnode = lnode;
	}
	public Node getRnode() {
		return rnode;
	}
	public void setRnode(Node rnode) {
		this.rnode = rnode;
	}
	
}

(2) Iter.java

package com.zx.tree;

public interface Iter {
	public abstract boolean hasNext() ;
	public abstract Integer next();
}

(3)PreIter.java

package com.zx.tree;

import java.util.Stack;

public class PreIter implements Iter{
	private Node root;
	Stack stack;
	private Node p;
	
	public PreIter(Node root)
	{
		this.root = root;
		stack = new Stack<>();
		this.p = this.root;
	}
	
	@Override
	public boolean hasNext() {
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				return true;
			}
			else
			{
				p = stack.pop();
				p = p.getRnode();
			}
		}
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public Integer next() {
		
		stack.add(p);
		Integer ans = p.getData();
		p = p.getLnode();
		return ans ;
		// TODO Auto-generated method stub
	}
	
	
	
}

(4)MidIter.java

package com.zx.tree;

import java.util.Stack;

public class MidIter  implements Iter{
	private Node root;
	Stack stack;
	private Node p;
	
	public MidIter(Node root)
	{
		this.root = root;
		stack = new Stack<>();
		this.p = this.root;
	}
	
	@Override
	public boolean hasNext() {
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				stack.add(p);
				p = p.getLnode();
			}
			else
			{
				return true;
			}
		}
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public Integer next() {
		
		p = stack.pop();
		Integer ans = p.getData();
		p = p.getRnode();
		return ans ;
		// TODO Auto-generated method stub
	}
	
	
	
}

(5)LastIter.java

package com.zx.tree;

import java.util.Stack;

public class LastIter implements Iter{
	private Node root;
	Stack stack;
	private Node p;
	private Node r;
	
	public LastIter(Node root)
	{
		this.root = root;
		stack = new Stack<>();
		this.p = this.root;
		this.r = null;
	}
	
	@Override
	public boolean hasNext() {
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				stack.add(p);
				p = p.getLnode();
			}
			else
			{
				p = stack.peek();
				if(p.getRnode()!=null && p.getRnode() !=r)
				{
					p = p.getRnode();
					stack.add(p);
					p = p.getLnode();
				}
				else
				{
					return true;
				}
			}
		}
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public Integer next() {
		
		p = stack.pop();
		Integer ans = p.getData();
		r = p;
		p = null;
		return ans ;
		// TODO Auto-generated method stub
	}
	
	
	
}

(6)main.java

package com.zx.tree;

public class Main {
	
	public static Integer[] ans = {1,2,3,4,5,6,7,8,9,10,11,12};
	
	private static void printArray(Integer[] ans)
	{
		for(int i=0;i

输出：

前序遍历
递归:  1 2 4 8 9 5 10 11 3 6 12 7 
非递归:1 2 4 8 9 5 10 11 3 6 12 7 
迭代:  1 2 4 8 9 5 10 11 3 6 12 7 
--------------------------------------------------
中序遍历
递归:  8 4 9 2 10 5 11 1 12 6 3 7 
非递归:8 4 9 2 10 5 11 1 12 6 3 7 
迭代:  8 4 9 2 10 5 11 1 12 6 3 7 
--------------------------------------------------
后序遍历
递归:  8 9 4 10 11 5 2 12 6 7 3 1 
非递归:8 9 4 10 11 5 2 12 6 7 3 1 
迭代:  8 9 4 10 11 5 2 12 6 7 3 1 
--------------------------------------------------

二、泛型版本

（1）Tree.java

package com.zx.treet;

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

public class Tree {
	
	private Node root;
	private List ans;
	private Integer size;
	
	public Tree(){
		root = null;
		ans = null;
		size = null;
	}
	
	public Tree(List ans){
		this.ans=ans;
		size=this.ans.size();
		root = build(0);
	}
	
	private Node build(Integer pos){
		Node node = new Node<>();
		node.setData(ans.get(pos));
		if(pos*2+1();		

	}
	
	private void visit(Node node){
		ans.add(node.getData());
	}
	
	//----------------------------------------------------------------------
	//递归形式前序遍历
	public List preList() {
		reset();
		dfsPre(root);
		return ans;
	}
	
	//递归形式前序遍历
	private void dfsPre(Node node){
		if(node == null) return ;
		visit(node);
		dfsPre(node.getLnode());
		dfsPre(node.getRnode());
	}
	
	//----------------------------------------------------------------------
	//递归形式中序遍历
	public List midList() {
		reset();
		dfsMid(root);
		return ans;
		
	}
	
	//递归形式中序遍历
	private void dfsMid(Node node){
		if(node == null) return ;
		dfsMid(node.getLnode());
		visit(node);
		dfsMid(node.getRnode());
	}
	
	
	//----------------------------------------------------------------------
	//递归形式后续遍历
	public List lastList() {
		reset();
		dfsLast(root);
		return ans;
		
	}
	
	//递归形式后续遍历
	private void dfsLast(Node node){
		if(node == null) return ;
		dfsLast(node.getLnode());
		dfsLast(node.getRnode());
		visit(node);
	}
	
	
	
	//----------------------------------------------------------------------
	//非递归形式前序遍历
	public List stackPreList() {
		reset();
		Stack> stack = new Stack<>();
		
		Node p = root;
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				visit(p);
				stack.add(p);
				p = p.getLnode();
			}
			else
			{
				p = stack.pop();
				p = p.getRnode();
			}
		}
		return ans;
	}
	
	
	//----------------------------------------------------------------------
	//非递归形式中续遍历
	public List stackMidList() {
		reset();
		Stack> stack = new Stack<>();
		
		Node p = root;
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				stack.add(p);
				p = p.getLnode();
			}
			else
			{
				p = stack.pop();
				visit(p);
				p = p.getRnode();
			}
		}
		return ans;
	}
	
	
	//----------------------------------------------------------------------
	//非递归形式后续遍历
	public List stackLastList() {
		reset();
		Stack> stack = new Stack<>();
		
		Node p = root;
		//后续遍历为左右根
		//r表示上一个访问的节点，用来判断是不是从右子树返回的
		Node r = null;
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				stack.add(p);
				p = p.getLnode();
			}
			else
			{
				//查看栈顶
				p = stack.peek();
				
				if(p.getRnode() != null && p.getRnode() != r)//右子树存在且未被访问过
				{
					p = p.getRnode();
					stack.add(p);
					p = p.getLnode();
				}
				else
				{
					p = stack.pop();
					visit(p);
					r = p;
					//访问完以p为根的子树
					p = null;
				}
			}
		}
		return ans;
	}
	
	
	
	
	//利用迭代器实现遍历
	//采用非递归形式
	public Iter getPreIter() {
		return new PreIter(root);
	}
	
	public Iter getMidIter() {
		return new MidIter(root);
	}
	
	public Iter getLastIter() {
		return new LastIter(root);
	}
	
}


class Node 
{
	private T data;
	private Node lnode;
	private Node rnode;
	
	public Node() {
		data = null;
		lnode = null;
		rnode = null;
	}
	
	public T getData() {
		return data;
	}
	public void setData(T data) {
		this.data = data;
	}
	public Node getLnode() {
		return lnode;
	}
	public void setLnode(Node lnode) {
		this.lnode = lnode;
	}
	public Node getRnode() {
		return rnode;
	}
	public void setRnode(Node rnode) {
		this.rnode = rnode;
	}
	
}

(2)Iter.java

package com.zx.treet;

public interface Iter {
	public abstract boolean hasNext() ;
	public abstract T next();
}

(3)PreIter.java

package com.zx.treet;

import java.util.Stack;

public class PreIter implements Iter {
	private Node root;
	Stack> stack;
	private Node p;
	
	public PreIter(Node root)
	{
		this.root = root;
		stack = new Stack<>();
		this.p = this.root;
	}
	
	@Override
	public boolean hasNext() {
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				return true;
			}
			else
			{
				p = stack.pop();
				p = p.getRnode();
			}
		}
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public T next() {
		
		stack.add(p);
		T ans = p.getData();
		p = p.getLnode();
		return ans ;
		// TODO Auto-generated method stub
	}
	
	
	
}

(4)MidIter.java

package com.zx.treet;

import java.util.Stack;

public class MidIter  implements Iter{
	private Node root;
	Stack> stack;
	private Node p;
	
	public MidIter(Node root)
	{
		this.root = root;
		stack = new Stack<>();
		this.p = this.root;
	}
	
	@Override
	public boolean hasNext() {
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				stack.add(p);
				p = p.getLnode();
			}
			else
			{
				return true;
			}
		}
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public T next() {
		
		p = stack.pop();
		T ans = p.getData();
		p = p.getRnode();
		return ans ;
		// TODO Auto-generated method stub
	}
	
	
	
}

(5)LastIter.java

package com.zx.treet;

import java.util.Stack;

public class LastIter implements Iter{
	private Node root;
	Stack> stack;
	private Node p;
	private Node r;
	
	public LastIter(Node root)
	{
		this.root = root;
		stack = new Stack<>();
		this.p = this.root;
		this.r = null;
	}
	
	@Override
	public boolean hasNext() {
		
		while(p != null || !stack.empty())
		{
			if(p!=null)
			{
				stack.add(p);
				p = p.getLnode();
			}
			else
			{
				p = stack.peek();
				if(p.getRnode()!=null && p.getRnode() !=r)
				{
					p = p.getRnode();
					stack.add(p);
					p = p.getLnode();
				}
				else
				{
					return true;
				}
			}
		}
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public T next() {
		
		p = stack.pop();
		T ans = p.getData();
		r = p;
		p = null;
		return ans ;
		// TODO Auto-generated method stub
	}
	
	
	
}

(6)Main.java

package com.zx.treet;

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

public class Main {
	
	public static List ans ;
	public static List res;
	
	public static void init() {
		ans = new ArrayList<>();
		for(int i=1;i<=12;i++)
			ans.add(i);
		
		res = new ArrayList<>();
		for(int i=0;i<12;i++)
			res.add((char)('a'+i)+"");
	}
	
	

	public static void main(String[] args) {
		
		init();
		
		startInteger();
		startString();
		
		
	}
	
	public static void startInteger() {
		Tree t = new Tree<>(ans);
		
		System.out.println("前序遍历");
		System.out.print("递归:  ");
		List res = t.preList();
		for(Integer x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		System.out.print("非递归:");
		res = t.stackPreList();
		for(Integer x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		
		System.out.print("迭代:  ");
		Iter iter = t.getPreIter();
		while(iter.hasNext())
			System.out.print(iter.next()+" ");
		System.out.println("");
		
		System.out.println("--------------------------------------------------");
		
		System.out.println("中序遍历");
		System.out.print("递归:  ");
		res = t.midList();
		for(Integer x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		System.out.print("非递归:");
		res = t.stackMidList();
		for(Integer x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		
		System.out.print("迭代:  ");
		iter = t.getMidIter();
		while(iter.hasNext())
			System.out.print(iter.next()+" ");
		System.out.println("");

		System.out.println("--------------------------------------------------");
		
		System.out.println("后序遍历");
		System.out.print("递归:  ");
		res = t.lastList();
		for(Integer x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		System.out.print("非递归:");
		res = t.stackLastList();
		for(Integer x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		
		System.out.print("迭代:  ");
		iter = t.getLastIter();
		while(iter.hasNext())
			System.out.print(iter.next()+" ");
		System.out.println("");

		System.out.println("--------------------------------------------------");
		System.out.println("--------------------------------------------------");
		System.out.println("--------------------------------------------------");
	}
	
	public static void startString() {
		Tree t = new Tree<>(res);
		
		System.out.println("前序遍历");
		System.out.print("递归:  ");
		List res = t.preList();
		for(String x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		System.out.print("非递归:");
		res = t.stackPreList();
		for(String x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		
		System.out.print("迭代:  ");
		Iter iter = t.getPreIter();
		while(iter.hasNext())
			System.out.print(iter.next()+" ");
		System.out.println("");
		
		System.out.println("--------------------------------------------------");
		
		System.out.println("中序遍历");
		System.out.print("递归:  ");
		res = t.midList();
		for(String x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		System.out.print("非递归:");
		res = t.stackMidList();
		for(String x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		
		System.out.print("迭代:  ");
		iter = t.getMidIter();
		while(iter.hasNext())
			System.out.print(iter.next()+" ");
		System.out.println("");

		System.out.println("--------------------------------------------------");
		
		System.out.println("后序遍历");
		System.out.print("递归:  ");
		res = t.lastList();
		for(String x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		System.out.print("非递归:");
		res = t.stackLastList();
		for(String x : res)
			System.out.print(x+" ");
		System.out.println("");
		
		
		System.out.print("迭代:  ");
		iter = t.getLastIter();
		while(iter.hasNext())
			System.out.print(iter.next()+" ");
		System.out.println("");

		System.out.println("--------------------------------------------------");
		System.out.println("--------------------------------------------------");
		System.out.println("--------------------------------------------------");
	}


}

输出：

前序遍历
递归:  1 2 4 8 9 5 10 11 3 6 12 7 
非递归:1 2 4 8 9 5 10 11 3 6 12 7 
迭代:  1 2 4 8 9 5 10 11 3 6 12 7 
--------------------------------------------------
中序遍历
递归:  8 4 9 2 10 5 11 1 12 6 3 7 
非递归:8 4 9 2 10 5 11 1 12 6 3 7 
迭代:  8 4 9 2 10 5 11 1 12 6 3 7 
--------------------------------------------------
后序遍历
递归:  8 9 4 10 11 5 2 12 6 7 3 1 
非递归:8 9 4 10 11 5 2 12 6 7 3 1 
迭代:  8 9 4 10 11 5 2 12 6 7 3 1 
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
前序遍历
递归:  a b d h i e j k c f l g 
非递归:a b d h i e j k c f l g 
迭代:  a b d h i e j k c f l g 
--------------------------------------------------
中序遍历
递归:  h d i b j e k a l f c g 
非递归:h d i b j e k a l f c g 
迭代:  h d i b j e k a l f c g 
--------------------------------------------------
后序遍历
递归:  h i d j k e b l f g c a 
非递归:h i d j k e b l f g c a 
迭代:  h i d j k e b l f g c a 
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------

数据结构——二叉树的遍历

Java相关栏目本月热门文章