当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-二叉树的遍历-先序、中序、后序(递归和非递归)、层次遍历

发表于: 2012-01-14   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.LinkedList; import java.util.List; import java.util.Stack; public class BinTreeTraverse { //private int[] array={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }; private int[] array={ 10,6,
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;


public class BinTreeTraverse {
	//private int[] array={ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	private int[] array={ 10,6,14,4,8,12,16};//BinarySearchTree
	private static List<Node> nodeList=null;


	public static void main(String[] args) {
		BinTreeTraverse tree=new BinTreeTraverse();
		tree.createBinTree();
		
		preOrder(nodeList.get(0));
		System.out.println();
		preOrderStack(nodeList.get(0));
		System.out.println();
		
		inOrder(nodeList.get(0));
		System.out.println();
		inOrderStack(nodeList.get(0));
		System.out.println();
		
		postOrder(nodeList.get(0));
		System.out.println();
		postOrderStack(nodeList.get(0));
		System.out.println();
		
		levelOrderStack(nodeList.get(0));
	}
	
	
	public static void visit(Node node){
		System.out.print(node.getData()+" ");
	}
	
	//create binary tree from array.the data stored in level-order
	public void createBinTree(){
		
		nodeList=new LinkedList<Node>();
		for(int i=0,len=array.length;i<len;i++){
			nodeList.add(new Node(array[i]));
		}
		
		int len=array.length;
		int lastRootIndex=(len>>1)-1;
		for(int i=lastRootIndex;i>=0;i--){
			Node root=nodeList.get(i);
			int leftIndex=i*2+1;
			Node leftNode=nodeList.get(leftIndex);
			//Node leftNode=new Node(array[leftIndex]);//this is wrong
			root.setLeft(leftNode);
			//最后的那个根节点一定是有左孩子的。右孩子则不一定
			int rightIndex=leftIndex+1;
			if(rightIndex<=len-1){
				Node rightNode=nodeList.get(rightIndex);
				root.setRight(rightNode);
			}
			
		}
	}

	//nonRecursion perOrder Traverse
	public static void preOrderStack(Node root){
		
		Stack<Node> stack=new Stack<Node>();
		Node p=root;
		if(p!=null){
			stack.push(p);
			while(!stack.isEmpty()){
				p=stack.pop();
				visit(p);
				if(p.getRight()!=null)stack.push(p.getRight());
				if(p.getLeft()!=null)stack.push(p.getLeft());
			}
		}
	}
	//nonRecursion inOrder Traverse
	public static void inOrderStack(Node p){
		Stack<Node> stack=new Stack<Node>();
		while(p!=null||!stack.isEmpty()){
			//push all LeftChild,when p has no LeftChild,that means it's root,it should be visited
			while(p!=null){
				stack.push(p);
				p=p.getLeft();
			}
			if(!stack.isEmpty()){
				p=stack.pop();
				visit(p);
				p=p.getRight();
			}
		}
	}
	
	//nonRecursion postOrder Traverse
	public static void postOrderStack(Node p){
		Stack<Node> stack=new Stack<Node>();
		Node q=p;//q,is the latest Node that has been visited
		while(p!=null){
			while(p.getLeft()!=null){
				stack.push(p);
				p=p.getLeft();
			}
			/*
			 while(p!=null){//wrong.when 'while' ends,p=null
				stack.push(p);
				p=p.getLeft();
			}
			 */
			/*left-right-root
			 *when a node:
			 *1.has no right-child -->p.getRight()==null
			 *2.right-child has been visited -->p.getRight()==q
			 *it's time to visit this node.
			 */
			while(p!=null&&(p.getRight()==null||p.getRight()==q)){
				visit(p);
				q=p;
				if(stack.isEmpty())return;
				p=stack.pop();
			}
			stack.push(p);
			p=p.getRight();
		}
	}
	//level order
	public static void levelOrderStack(Node p){
		if(p==null)return;
		List<Node> queue=new LinkedList<Node>();
		queue.add(p);
		while(!queue.isEmpty()){
			Node temp=queue.remove(0);
			System.out.print(temp.data+" ");
			if(temp.left!=null){
				queue.add(temp.left);
			}
			if(temp.right!=null){
				queue.add(temp.right);
			}
		}
		System.out.println();
	}
	
	public static void preOrder(Node root){
		if(root==null){return;}
		System.out.print(root.getData()+" ");
		preOrder(root.getLeft());
		preOrder(root.getRight());
	}
	public static void inOrder(Node root){
		if(root==null){return;}
		inOrder(root.getLeft());
		System.out.print(root.getData()+" ");
		inOrder(root.getRight());
	}
	public static void postOrder(Node root){
		if(root==null){return;}
		postOrder(root.getLeft());
		postOrder(root.getRight());
		System.out.print(root.getData()+" ");
	}

	private static class Node{
		private Node left;
		private Node right;
		private int data;
		Node(int iData){
			data=iData;
			left=null;
			right=null;
		}
		public void setLeft(Node leftNode){
			this.left=leftNode;
		}
		public void setRight(Node rightNode){
			this.right=rightNode;
		}
		public Node getLeft(){
			return left;
		}
		public Node getRight(){
			return right;
		}
		public int getData(){
			return data;
		}
		
	}
	
}

java-二叉树的遍历-先序、中序、后序(递归和非递归)、层次遍历

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1、先、中、后递归遍历 其中(1)(2)(3)位置上分别表示先、中、后。 2、先、中、后非递归遍历
先序遍历:若二叉树为空,则空操作;否则访问根节点;先序遍历左子树;先序遍历右子树。 中序遍历:
#include "stdafx.h" #include <iostream> using namespace std; const int MAXSIZE = 20; //
// 二叉树的遍历.cpp : Defines the entry point for the console application. // #include <ST
一、基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒。 性质: 1、非空二叉树的
PS:输入测试数据时候采用先序遍历的方式用#作为分隔符来输入,例如:此二叉树 用这种方式输入ABC##
一、基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒。 性质: 1、非空二叉树的
在自考中一直在头疼二叉树的遍历问题,先序中序后序,先根后根傻傻分不清楚。在这里就来谈谈着三种
开始复习下数据结构,学习二叉树将二叉树的遍历方式实现了一遍,非递归相对有点难度,通过收集资料
#include <iostream> #include <stack> using namespace std; struct Node{ char data;
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号