「java二叉树的遍历」二叉树遍历java代码

今天给各位分享java二叉树的遍历的知识，其中也会对二叉树遍历java代码进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、java实现二叉树层次遍历
• 2、用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。
• 3、写一个java层次遍历二叉树,简单点就可以,我要的是代码,不是纯文字说明
• 4、java中的遍历是什么意思？
• 5、java 二叉树前序遍历
• 6、java Map 怎么遍历

java实现二叉树层次遍历

import java.util.ArrayList;

public class TreeNode {

private TreeNode leftNode;

private TreeNode rightNode;

private String nodeName;

public TreeNode getLeftNode() {

return leftNode;

}

public void setLeftNode(TreeNode leftNode) {

this.leftNode = leftNode;

}

public TreeNode getRightNode() {

return rightNode;

}

public void setRightNode(TreeNode rightNode) {

this.rightNode = rightNode;

}

public String getNodeName() {

return nodeName;

}

public void setNodeName(String nodeName) {

this.nodeName = nodeName;

}

public static int level=0;

public static void findNodeByLevel(ArrayListTreeNode nodes){

if(nodes==null||nodes.size()==0){

return ;

}

level++;

ArrayListTreeNode temp = new ArrayList();

for(TreeNode node:nodes){

System.out.println("第"+level+"层:"+node.getNodeName());

if(node.getLeftNode()!=null){

temp.add(node.getLeftNode());

}

if(node.getRightNode()!=null){

temp.add(node.getRightNode());

}

}

nodes.removeAll(nodes);

findNodeByLevel(temp);

}

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

TreeNode root = new TreeNode();

root.setNodeName("root");

TreeNode node1 = new TreeNode();

node1.setNodeName("node1");

TreeNode node3 = new TreeNode();

node3.setNodeName("node3");

TreeNode node7 = new TreeNode();

node7.setNodeName("node7");

TreeNode node8 = new TreeNode();

node8.setNodeName("node8");

TreeNode node4 = new TreeNode();

node4.setNodeName("node4");

TreeNode node2 = new TreeNode();

node2.setNodeName("node2");

TreeNode node5 = new TreeNode();

node5.setNodeName("node5");

TreeNode node6 = new TreeNode();

node6.setNodeName("node6");

root.setLeftNode(node1);

node1.setLeftNode(node3);

node3.setLeftNode(node7);

node3.setRightNode(node8);

node1.setRightNode(node4);

root.setRightNode(node2);

node2.setLeftNode(node5);

node2.setRightNode(node6);

ArrayListTreeNode nodes = new ArrayListTreeNode();

nodes.add(root);

findNodeByLevel(nodes);

}

}

用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。

先序非递归算法

【思路】

假设：T是要遍历树的根指针，若T != NULL

对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。

问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？

方法1：访问T-data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。

方法2：访问T-data后，将T-rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T-rchild，出栈，遍历以该指针为根的子树。

【算法1】

void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基于方法一

InitStack(S);

while ( T!=NULL || !StackEmpty(S)){

while ( T != NULL ){

Visit(T-data) ;

Push(S,T);

T = T-lchild;

}

if( !StackEmpty(S) ){

Pop(S,T);

T = T-rchild;

}

}

}

【算法2】

void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基于方法二

InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){

while ( T != NULL ){

Visit(T-data);

Push(S, T-rchild);

T = T-lchild;

}

if ( !StackEmpty(S) ){

Pop(S,T);

}

}

}

进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。

中序非递归算法

【思路】

T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。

问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？

方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T-data，再中序遍历T的右子树。

【算法】

void InOrder(BiTree T, Status ( *Visit ) (ElemType e))

{

InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){

while ( T != NULL ){

Push(S,T);

T = T-lchild;

}

if( !StackEmpty(S) ){

Pop(S, T);

Visit(T-data);

T = T-rchild;

}

}

}

进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。

后序非递归算法

【思路】

T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。

可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。

首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。 [Page]

typedef struct stackElement{

Bitree data;

char tag;

}stackElemType;

【算法】

void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))

{

InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){

while ( T != NULL ){

Push(S,T,0);

T = T-lchild;

}

while ( !StackEmpty(S) GetTopTag(S)==1){

Pop(S, T);

Visit(T-data);

}

if ( !StackEmpty(S) ){

SetTopTag(S, 1); // 设置栈顶标记

T = GetTopPointer(S); // 取栈顶保存的指针

T = T-rchild;

}else break;

}

}

写一个java层次遍历二叉树,简单点就可以,我要的是代码,不是纯文字说明

public class BinaryNode {

Object element;

BinaryNode left;

BinaryNode right;

}

import java.util.*;

public class Queue {

protected LinkedList list;

// Postcondition: this Queue object has been initialized.

public Queue() {

list = new LinkedList();

} // default constructor

// Postcondition: the number of elements in this Queue object has been

// returned.

public int size() {

return list.size();

} // method size

// Postcondition: true has been returned if this Queue object has no

// elements. Otherwise, false has been returned.

public boolean isEmpty() {

return list.isEmpty();

} // method isEmpty

// Postconditon: A copy of element has been inserted at the back of this

// Queue object. The averageTime (n) is constant and

// worstTime (n) is O (n).

public void enqueue(Object element) {

list.addLast(element);

} // method enqueue

// Precondition: this Queue object is not empty. Otherwise,

// NoSuchElementException will be thrown.

// Postcondition: The element that was at the front of this Queue object -

// just before this method was called -- has been removed

// from this Queue object and returned.

public Object dequeue() {

return list.removeFirst();

} // method dequeue

// Precondition: this Queue object is not empty. Otherwise,

// NoSuchElementException will be thrown.

// Postcondition: the element at index 0 in this Queue object has been

// returned.

public Object front() {

return list.getFirst();

} // method front

} // Queue class

import java.io.IOException;

public class BinaryTree {

BinaryNode root;

public BinaryTree() {

super();

// TODO 自动生成构造函数存根

root=this.createPre();

}

public BinaryNode createPre()

//按照先序遍历的输入方法，建立二叉树

{

BinaryNode t=null;

char ch;

try {

ch = (char)System.in.read();

if(ch==' ')

t=null;

else

{

t=new BinaryNode();

t.element=(Object)ch;

t.left=createPre();

t.right=createPre();

}

} catch (IOException e) {

// TODO 自动生成 catch 块

e.printStackTrace();

}

return t;

}

public void inOrder()

{

this.inOrder(root);

}

public void inOrder(BinaryNode t)

//中序遍历二叉树

{

if(t!=null)

{

inOrder(t.left);

System.out.print(t.element);

inOrder(t.right);

}

}

public void postOrder()

{

this.postOrder(root);

}

public void postOrder(BinaryNode t)

//后序遍历二叉树

{

if(t!=null)

{

postOrder(t.left);

System.out.print(t.element);

postOrder(t.right);

}

}

public void preOrder()

{

this.preOrder(root);

}

public void preOrder(BinaryNode t)

//前序遍历二叉树

{

if(t!=null)

{

System.out.print(t.element);

preOrder(t.left);

preOrder(t.right);

}

}

public void breadthFirst()

{

Queue treeQueue=new Queue();

BinaryNode p;

if(root!=null)

treeQueue.enqueue(root);

while(!treeQueue.isEmpty())

{

System.out.print(((BinaryNode)(treeQueue.front())).element);

p=(BinaryNode)treeQueue.dequeue();

if(p.left!=null)

treeQueue.enqueue(p.left);

if(p.right!=null)

treeQueue.enqueue(p.right);

}

}

}

public class BinaryTreeTest {

/**

* @param args

*/

public static void main(String[] args) {

// TODO 自动生成方法存根

BinaryTree tree = new BinaryTree();

System.out.println("先序遍历：");

tree.preOrder();

System.out.println();

System.out.println("中序遍历：");

tree.inOrder();

System.out.println();

System.out.println("后序遍历：");

tree.postOrder();

System.out.println();

System.out.println("层次遍历：");

tree.breadthFirst();

System.out.println();

}

}

java中的遍历是什么意思？

遍历就是把每个元素都访问一次.比如一个二叉树,遍历二叉树意思就是把二叉树中的每个元素都访问一次

java 二叉树前序遍历

//类Node定义二叉树结点的数据结构;

//一个结点应包含结点值，左子结点的引用和右子结点的引用

class Node{

public Node left; //左子结点

public Node right; //右子结点

public int value; //结点值

public Node(int val){

value = val;

}

}

public class Traversal

{

//read()方法将按照前序遍历的方式遍历输出二叉树的结点值

//此处采用递归算法会比较简单，也容易理解，当然也可以用

//循环的方法遍历，但会比较复杂，也比较难懂。二叉树遍历

//用递归算法最为简单，因为每个结点的遍历方式都是，根，

//左，右，递归的调用可以让每个结点以这种方式遍历

public static void read(Node node){

if(node != null){

System.out.println(node.value);//输出当前结点的值

if(node.left != null)

read(node.left); //递归调用 先读左结点

if(node.right != null)

read(node.right); //递归调用 后读右结点

}

}

public static void main(String[] args){

//初始化5个结点，分别初始值为1，2，3，4，5

Node n1 = new Node(1);

Node n2 = new Node(2);

Node n3 = new Node(3);

Node n4 = new Node(4);

Node n5 = new Node(5);

//构建二叉树，以n1为根结点

n1.left = n2;

n1.right = n5;

n2.left = n3;

n2.right = n4;

read(n1);

}

}

注释和代码都是我自己写的，如果楼主觉得有的注释多余可以自己删除一些！代码我都编译通过，并且运行结果如你提的要求一样！你只要把代码复制编译就可以了，注意要以文件名Traversal.java来保存，否则编译不通过，因为main函数所在的类是public类型的！

java Map 怎么遍历

java Map 遍历一般有四种方式

方式一: 这是最常见的并且在大多数情况下也是最可取的遍历方式。在键值都需要时使用。

方式二： 在for-each循环中遍历keys或values。

如果只需要map中的键或者值，你可以通过keySet或values来实现遍历，而不是用entrySet。

该方法比entrySet遍历在性能上稍好（快了10%），而且代码更加干净。

方式三：使用Iterator遍历

使用泛型：

不使用泛型：

你也可以在keySet和values上应用同样的方法。

方法四:  通过键找值遍历（效率低）

作为方法一的替代，这个代码看上去更加干净；但实际上它相当慢且无效率。

因为从键取值是耗时的操作（与方法一相比，在不同的Map实现中该方法慢了20%~200%）。如果安装了FindBugs，它会做出检查并警告你关于哪些是低效率的遍历。所以尽量避免使用。

总结:

如果仅需要键(keys)或值(values)使用方法二。

如果所使用的语言版本低于java 5，或是打算在遍历时删除entries，必须使用方法三。

否则使用方法一(键值都要)。

扩展资料：

类似的遍历算法：

二叉树的遍历算法

1、先（根）序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

⑴ 访问根结点；

⑵ 遍历左子树；

⑶ 遍历右子树。

2、中（根）序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

⑴遍历左子树；

⑵访问根结点；

⑶遍历右子树。

3、后（根）序遍历得递归算法定义：

若二叉树非空，则依次执行如下操作：

⑴遍历左子树；

⑵遍历右子树；

⑶访问根结点。

参考资料：百度百科——Java

关于java二叉树的遍历和二叉树遍历java代码的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。