「java层级遍历」java层次遍历

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

本文目录一览：

• 1、java实现二叉树层次遍历
• 2、java Map 怎么遍历
• 3、用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。
• 4、java 实现二叉树的层次遍历
• 5、java层次遍历算法思路?
• 6、怎样使用java对二叉树进行层次遍历

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 Map 怎么遍历

关于java中遍历map具体有四种方式，请看下文详解。

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

MapInteger, Integer map = new HashMapInteger, Integer();

for (Map.EntryInteger, Integer entry : map.entrySet()) {

System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());

}

2、在for-each循环中遍历keys或values。

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

MapInteger, Integer map = new HashMapInteger, Integer();

for (Integer key : map.keySet()) {

System.out.println("Key = " + key);

}

for (Integer value : map.values()) {

System.out.println("Value = " + value);

}

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

3、使用Iterator遍历

使用泛型：

MapInteger, Integer map = new HashMapInteger, Integer();

IteratorMap.EntryInteger, Integer entries = map.entrySet().iterator();

while (entries.hasNext()) {

Map.EntryInteger, Integer entry = entries.next();

System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());

}

不使用泛型：

Map map = new HashMap();

Iterator entries = map.entrySet().iterator();

while (entries.hasNext()) {

Map.Entry entry = (Map.Entry) entries.next();

Integer key = (Integer)entry.getKey();

Integer value = (Integer)entry.getValue();

System.out.println("Key = " + key + ", Value = " + value);

}

4、通过键找值遍历（效率低）

MapInteger, Integer map = new HashMapInteger, Integer();

for (Integer key : map.keySet()) {

Integer value = map.get(key);

System.out.println("Key = " + key + ", Value = " + value);

}

假设Map中的键值对为1=11,2=22,3=33,现用方法1来遍历Map代码和调试结果如下：

扩展资料：

1、HashMap的重要参数

HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。

加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

在Java编程语言中，加载因子默认值为0.75，默认哈希表元为101。

2、HashMap的同步机制

注意，此实现不是同步的。 如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。

（结构上的修改是指添加或删除一个或多个映射关系的任何操作；以防止对映射进行意外的非同步访问，如下：

Map m = Collections.synchronizedMap(new HashMap(...));

参考资料：百度百科-Hashmap

用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 实现二叉树的层次遍历

class TreeNode {

public TreeNode left;

public TreeNode right;

public int value;

public TreeNode(TreeNode left, TreeNode right, int value) {

this.left = left;

this.right = right;

this.value = value;

}

}

public class BinaryTree {

public static int getTreeHeight(TreeNode root) {

if (root == null)

return 0;

if (root.left == null root.right == null)

return 1;

return 1 + Math

.max(getTreeHeight(root.left), getTreeHeight(root.right));

}

public static void recursePreOrder(TreeNode root) {

if (root == null)

return;

System.out.println(root.value);

if (root.left != null)

recursePreOrder(root.left);

if (root.right != null)

recursePreOrder(root.right);

}

public static void stackPreOrder(TreeNode root) {

Stack stack = new Stack();

if (root == null)

return;

stack.push(root);

System.out.println(root.value);

TreeNode temp = root.left;

while (temp != null) {

stack.push(temp);

System.out.println(temp.value);

temp = temp.left;

}

temp = (TreeNode) stack.pop();

while (temp != null) {

temp = temp.right;

while (temp != null) {

stack.push(temp);

System.out.println(temp.value);

temp = temp.left;

}

if (stack.empty())

break;

temp = (TreeNode) stack.pop();

}

}

public static void recurseInOrder(TreeNode root) {

if (root == null)

return;

if (root.left != null)

recurseInOrder(root.left);

System.out.println(root.value);

if (root.right != null)

recurseInOrder(root.right);

}

public static void stackInOrder(TreeNode root) {

Stack stack = new Stack();

if (root == null)

return;

else

stack.push(root);

TreeNode temp = root.left;

while (temp != null) {

stack.push(temp);

temp = temp.left;

}

temp = (TreeNode) stack.pop();

while (temp != null) {

System.out.println(temp.value);

temp = temp.right;

while (temp != null) {

stack.push(temp);

temp = temp.left;

}

if (stack.empty())

break;

temp = (TreeNode) stack.pop();

}

}

public static void main(String[] args) {

TreeNode node1 = new TreeNode(null, null, 1);

TreeNode node2 = new TreeNode(null, node1, 2);

TreeNode node3 = new TreeNode(null, null, 3);

TreeNode node4 = new TreeNode(node2, node3, 4);

TreeNode node5 = new TreeNode(null, null, 5);

TreeNode root = new TreeNode(node4, node5, 0);

System.out.println("Tree Height is " + getTreeHeight(root));

System.out.println("Recurse In Order Traverse");

recurseInOrder(root);

System.out.println("Stack In Order Traverse");

stackInOrder(root);

System.out.println("Recurse Pre Order Traverse");

recursePreOrder(root);

System.out.println("Stack Pre Order Traverse");

stackPreOrder(root);

}

}

可以做个参考

java层次遍历算法思路?

找个例子看一下就有了。比如递归前序遍历二叉树，即先根遍历。先遍历根节点，之后向下又是一个跟节点，在遍历做节点，在遍历右节点，依次下去，知道没有右节点结束。在遍历右边的部分，根节点，左节点，右节点，知道没有右节点是为止。至此遍历结束。书上有图一看就知道了。其他的遍历按照遍历算法一样。建议看下数据结构的遍历，讲的很详细。

怎样使用java对二叉树进行层次遍历

public class BinaryTree {

 int data;      //根节点数据

 BinaryTree left;    //左子树

 BinaryTree right;   //右子树

 public BinaryTree(int data)    //实例化二叉树类

 {

  this.data = data;

  left = null;

  right = null;

 }

 public void insert(BinaryTree root,int data){     //向二叉树中插入子节点

  if(dataroot.data)                               //二叉树的左节点都比根节点小

  {

   if(root.right==null){

    root.right = new BinaryTree(data);

   }else{

    this.insert(root.right, data);

   }

  }else{                                          //二叉树的右节点都比根节点大

   if(root.left==null){

    root.left = new BinaryTree(data);

   }else{

    this.insert(root.left, data);

   }

  }

 }

}

当建立好二叉树类后可以创建二叉树实例，并实现二叉树的先根遍历，中根遍历，后根遍历，代码如下：

package package2;

public class BinaryTreePreorder {

 public static void preOrder(BinaryTree root){  //先根遍历

  if(root!=null){

   System.out.print(root.data+"-");

   preOrder(root.left);

   preOrder(root.right);

  }

 }

 public static void inOrder(BinaryTree root){     //中根遍历

  if(root!=null){

   inOrder(root.left);

   System.out.print(root.data+"--");

   inOrder(root.right);

  }

 }

 public static void postOrder(BinaryTree root){    //后根遍历

  if(root!=null){

   postOrder(root.left);

   postOrder(root.right);

   System.out.print(root.data+"---");

  }

 }

 public static void main(String[] str){

  int[] array = {12,76,35,22,16,48,90,46,9,40};

  BinaryTree root = new BinaryTree(array[0]);   //创建二叉树

  for(int i=1;iarray.length;i++){

   root.insert(root, array[i]);       //向二叉树中插入数据

  }

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

  preOrder(root);

  System.out.println();

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

  inOrder(root);

  System.out.println();

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

  postOrder(root);

java层级遍历的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java层次遍历、java层级遍历的信息别忘了在本站进行查找喔。