数据结构之二叉树（2）

淩亂°似流年 2022-05-24 02:25 152阅读 0赞

遍历二叉树就是遵循某种次序，访问二叉树中的所有节点，每个节点只访问一次。

二叉树的遍历有三种方式：前序遍历，中序遍历和后序遍历。所谓的前序，中序和后序是针对根节点来说的。

前序遍历：首先访问根节点，然后访问左子树，最后访问右子树。

中序遍历：首先访问左子树，然后访问根节点，最后访问右子树。

后续遍历：首先访问左子树，然后访问右子树，最后访问根节点。

下面我们对链式存储的二叉树进行遍历。

示例代码：

运行结果如下：

前序遍历：
    H D B A C G F E 
    中序遍历：
    B A D C H G E F 
    后序遍历：
    A B C D E F G H

上面是通过递归方式实现的对于二叉树的遍历，虽然这种方式比较简单，但是我们知道会消耗系统较多的资源，下面我们使用非递归的方式实现二叉树的遍历。

首先是前序遍历，思想是：从根节点开始，如果该节点不为空，则将其压入堆栈，接着判断堆栈是否为空，如果不为空，则弹出一个节点，并且输出该节点的数据信息，接着按照前后顺序分别对该节点的右子树和左子树进行判断，如果有右子树，则将右子树压入栈中，如果有左子树，则将左子树压入栈中，最后再判断堆栈是否为空，如果不为空则继续上面的操作，如果为空，则遍历结束。

实现的算法为下：

//非递归方式实现前序遍历
    	public void nonRecursivePreorder(TreeNode<DataType> node)
    	{
    		Stack<TreeNode<DataType>> mystack=new Stack<TreeNode<DataType>>();
    		if(node!=null)
    		{
    			mystack.push(node);
    			while(!mystack.isEmpty())
    			{
    				TreeNode<DataType> temp=mystack.pop();
    				this.getNodeInfo(temp);
    				if(temp.getRight()!=null)
    				{
    					mystack.push(temp.getRight());
    				}
    				if(temp.getLeft()!=null)
    				{
    					mystack.push(temp.getLeft());
    				}
    			}
    		}
    	}

其次是中序遍历，算法实现如下：

//非递归方式实现中序遍历
    	public void nonRecursiveInorder(TreeNode<DataType> node)
    	{
    		Stack<TreeNode<DataType>> mystack=new Stack<TreeNode<DataType>>();
    		while(node!=null)
    		{
    			while(node!=null)
    			{
    				if(node.getRight()!=null)
    				{
    					mystack.push(node.getRight());
    				}
    				mystack.push(node);
    				node=node.getLeft();
    			}
    			node=mystack.pop();
    			while(!mystack.isEmpty()&&node.getRight()==null)
    			{
    				this.getNodeInfo(node);
    				node=mystack.pop();
    			}
    			this.getNodeInfo(node);
    			if(!mystack.isEmpty())
    			{
    				node=mystack.pop();
    			}else
    			{
    				node=null;
    			}
    		}
    	}

最后是后序遍历，算法实现如下：

//非递归方式实现后续遍历
    	public void nonRecursivePostorder(TreeNode<DataType> node)
    	{
    		Stack<TreeNode<DataType>> mystack=new Stack<TreeNode<DataType>>();
    		TreeNode<DataType> temp=node;
    		while(node!=null)
    		{
    			for(;node.getLeft()!=null;node=node.getLeft())
    			{
    				mystack.push(node);
    			}
    			while(node!=null&&(node.getRight()==null||node.getRight()==temp))
    			{
    				this.getNodeInfo(node);
    				temp=node;
    				if(mystack.isEmpty())
    					return;
    				node=mystack.pop();
    			}
    			mystack.push(node);
    			node=node.getRight();
    		}
    	}

运行结果如下所示：

递归方式实现前序遍历：
    H D B A C G F E 
    递归方式实现中序遍历：
    B A D C H G E F 
    递归方式实现后序遍历：
    A B C D E F G H 
    非递归方式实现前序遍历：
    H D B A C G F E 
    非递归方式实现中序遍历：
    B A D C H G E F 
    非递归方式实现后序遍历：
    A B C D E F G H

完整的程序如下所示：

package mianshiti;
    import java.util.*;
    
    public class BinarySearchTree<DataType> {
    	private TreeNode<DataType> root=null;//根节点
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		BinarySearchTree<Character> tree=new BinarySearchTree<Character>(init());
    		System.out.println("递归方式实现前序遍历：");
    		tree.preorder(tree.getRoot());
    		System.out.println();
    		System.out.println("递归方式实现中序遍历：");
    		tree.inorder(tree.getRoot());
    		System.out.println();
    		System.out.println("递归方式实现后序遍历：");
    		tree.postorder(tree.getRoot());
    		System.out.println();
    		System.out.println("非递归方式实现前序遍历：");
    		tree.nonRecursivePreorder(tree.getRoot());
    		System.out.println();
    		System.out.println("非递归方式实现中序遍历：");
    		tree.nonRecursiveInorder(tree.getRoot());
    		System.out.println();
    		System.out.println("非递归方式实现后序遍历：");
    		tree.nonRecursivePostorder(tree.getRoot());
    		System.out.println();
    	}
    	
    	//前序遍历
    	public void preorder(TreeNode<DataType> node)
    	{
    		if(node!=null)
    		{
    			this.getNodeInfo(node);
    			preorder(node.getLeft());
    			preorder(node.getRight());
    		}
    	}
    	//中序遍历
    	public void inorder(TreeNode<DataType> node)
    	{
    		if(node!=null)
    		{
    			inorder(node.getLeft());
    			this.getNodeInfo(node);
    			inorder(node.getRight());
    		}
    	}
    	//后序遍历
    	public void postorder(TreeNode<DataType> node)
    	{
    		if(node!=null)
    		{
    			postorder(node.getLeft());
    			postorder(node.getRight());
    			this.getNodeInfo(node);
    		}
    	}
    	//非递归方式实现前序遍历
    	public void nonRecursivePreorder(TreeNode<DataType> node)
    	{
    		Stack<TreeNode<DataType>> mystack=new Stack<TreeNode<DataType>>();
    		if(node!=null)
    		{
    			mystack.push(node);
    			while(!mystack.isEmpty())
    			{
    				TreeNode<DataType> temp=mystack.pop();
    				this.getNodeInfo(temp);
    				if(temp.getRight()!=null)
    				{
    					mystack.push(temp.getRight());
    				}
    				if(temp.getLeft()!=null)
    				{
    					mystack.push(temp.getLeft());
    				}
    			}
    		}
    	}
    	//非递归方式实现中序遍历
    	public void nonRecursiveInorder(TreeNode<DataType> node)
    	{
    		Stack<TreeNode<DataType>> mystack=new Stack<TreeNode<DataType>>();
    		while(node!=null)
    		{
    			while(node!=null)
    			{
    				if(node.getRight()!=null)
    				{
    					mystack.push(node.getRight());
    				}
    				mystack.push(node);
    				node=node.getLeft();
    			}
    			node=mystack.pop();
    			while(!mystack.isEmpty()&&node.getRight()==null)
    			{
    				this.getNodeInfo(node);
    				node=mystack.pop();
    			}
    			this.getNodeInfo(node);
    			if(!mystack.isEmpty())
    			{
    				node=mystack.pop();
    			}else
    			{
    				node=null;
    			}
    		}
    	}
    	//非递归方式实现后续遍历
    	public void nonRecursivePostorder(TreeNode<DataType> node)
    	{
    		Stack<TreeNode<DataType>> mystack=new Stack<TreeNode<DataType>>();
    		TreeNode<DataType> temp=node;
    		while(node!=null)
    		{
    			for(;node.getLeft()!=null;node=node.getLeft())
    			{
    				mystack.push(node);
    			}
    			while(node!=null&&(node.getRight()==null||node.getRight()==temp))
    			{
    				this.getNodeInfo(node);
    				temp=node;
    				if(mystack.isEmpty())
    					return;
    				node=mystack.pop();
    			}
    			mystack.push(node);
    			node=node.getRight();
    		}
    	}
    	//构造一个二叉树
    	public static TreeNode init()
    	{
    		TreeNode<Character> a=new TreeNode<Character>('A');
    		TreeNode<Character> b=new TreeNode<Character>('B',null,a);
    		TreeNode<Character> c=new TreeNode<Character>('C');
    		TreeNode<Character> d=new TreeNode<Character>('D',b,c);
    		TreeNode<Character> e=new TreeNode<Character>('E');
    		TreeNode<Character> f=new TreeNode<Character>('F',e,null);
    		TreeNode<Character> g=new TreeNode<Character>('G',null,f);
    		TreeNode<Character> h=new TreeNode<Character>('H',d,g);
    		return h;
    	}
    	//构造函数
    	public BinarySearchTree(TreeNode<DataType> root)
    	{
    		this.root=root;
    	}
    	
    	public TreeNode<DataType> getRoot()
    	{
    		return this.root;
    	}
    	
    	public void getNodeInfo(TreeNode<DataType> treenode)
    	{
    		if(treenode!=null)
    		{
    			System.out.print(treenode.getData()+" ");
    		}
    	}
    }
    
    class TreeNode<DataType>{
    	private DataType data;
    	private TreeNode<DataType> left;//左子节点
    	private TreeNode<DataType> right;//右子节点
    	//构造函数
    	public TreeNode(DataType data)
    	{
    		this(data,null,null);
    	}
    	
    	public TreeNode(DataType data,TreeNode<DataType> left,TreeNode<DataType> right)
    	{
    		this.data=data;
    		this.left=left;
    		this.right=right;
    	}
    	//公有方法
    	public DataType getData() {
    		return data;
    	}
    
    	public void setData(DataType data) {
    		this.data = data;
    	}
    
    	public TreeNode<DataType> getLeft() {
    		return left;
    	}
    
    	public void setLeft(TreeNode<DataType> left) {
    		this.left = left;
    	}
    
    	public TreeNode<DataType> getRight() {
    		return right;
    	}
    
    	public void setRight(TreeNode<DataType> right) {
    		this.right = right;
    	}
    
    }