「二叉树的遍历算法java」二叉树的遍历算法图解

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

本文目录一览：

• 1、java中的遍历是什么意思？
• 2、java Map 怎么遍历
• 3、java构建二叉树算法
• 4、用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。
• 5、java 二叉树前序遍历
• 6、java实现二叉树层次遍历

java中的遍历是什么意思？

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

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构建二叉树算法

//******************************************************************************************************//

//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//

//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//

//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//

//*******************************CopyRight By phoenix*******************************************//

//************************************Jan 12,2008*************************************************//

//****************************************************************************************************//

public class BinTree {

public final static int MAX=40;

private Object data; //数据元数

private BinTree left,right; //指向左,右孩子结点的链

BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点

int front;//层次遍历时队首

int rear;//层次遍历时队尾

public BinTree()

{

}

public BinTree(Object data)

{ //构造有值结点

this.data = data;

left = right = null;

}

public BinTree(Object data,BinTree left,BinTree right)

{ //构造有值结点

this.data = data;

this.left = left;

this.right = right;

}

public String toString()

{

return data.toString();

}//前序遍历二叉树

public static void preOrder(BinTree parent){

if(parent == null)

return;

System.out.print(parent.data+" ");

preOrder(parent.left);

preOrder(parent.right);

}//中序遍历二叉树

public void inOrder(BinTree parent){

if(parent == null)

return;

inOrder(parent.left);

System.out.print(parent.data+" ");

inOrder(parent.right);

}//后序遍历二叉树

public void postOrder(BinTree parent){

if(parent == null)

return;

postOrder(parent.left);

postOrder(parent.right);

System.out.print(parent.data+" ");

}// 层次遍历二叉树

public void LayerOrder(BinTree parent)

{

elements[0]=parent;

front=0;rear=1;

while(frontrear)

{

try

{

if(elements[front].data!=null)

{

System.out.print(elements[front].data + " ");

if(elements[front].left!=null)

elements[rear++]=elements[front].left;

if(elements[front].right!=null)

elements[rear++]=elements[front].right;

front++;

}

}catch(Exception e){break;}

}

}//返回树的叶节点个数

public int leaves()

{

if(this == null)

return 0;

if(left == nullright == null)

return 1;

return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());

}//结果返回树的高度

public int height()

{

int heightOfTree;

if(this == null)

return -1;

int leftHeight = (left == null ? 0 : left.height());

int rightHeight = (right == null ? 0 : right.height());

heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;

return 1 + heightOfTree;

}

//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层

public int level(Object object)

{

int levelInTree;

if(this == null)

return -1;

if(object == data)

return 1;//规定根节点为第一层

int leftLevel = (left == null?-1:left.level(object));

int rightLevel = (right == null?-1:right.level(object));

if(leftLevel0rightLevel0)

return -1;

levelInTree = leftLevelrightLevel?rightLevel:leftLevel;

return 1+levelInTree;

}

//将树中的每个节点的孩子对换位置

public void reflect()

{

if(this == null)

return;

if(left != null)

left.reflect();

if(right != null)

right.reflect();

BinTree temp = left;

left = right;

right = temp;

}// 将树中的所有节点移走,并输出移走的节点

public void defoliate()

{

String innerNode = "";

if(this == null)

return;

//若本节点是叶节点，则将其移走

if(left==nullright == null)

{

System.out.print(this + " ");

data = null;

return;

}

//移走左子树若其存在

if(left!=null){

left.defoliate();

left = null;

}

//移走本节点，放在中间表示中跟移走...

innerNode += this + " ";

data = null;

//移走右子树若其存在

if(right!=null){

right.defoliate();

right = null;

}

}

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

BinTree e = new BinTree("E");

BinTree g = new BinTree("G");

BinTree h = new BinTree("H");

BinTree i = new BinTree("I");

BinTree d = new BinTree("D",null,g);

BinTree f = new BinTree("F",h,i);

BinTree b = new BinTree("B",d,e);

BinTree c = new BinTree("C",f,null);

BinTree tree = new BinTree("A",b,c);

System.out.println("前序遍历二叉树结果: ");

tree.preOrder(tree);

System.out.println();

System.out.println("中序遍历二叉树结果: ");

tree.inOrder(tree);

System.out.println();

System.out.println("后序遍历二叉树结果: ");

tree.postOrder(tree);

System.out.println();

System.out.println("层次遍历二叉树结果: ");

tree.LayerOrder(tree);

System.out.println();

System.out.println("F所在的层次: "+tree.level("F"));

System.out.println("这棵二叉树的高度: "+tree.height());

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

tree.reflect();

System.out.println("交换每个节点的孩子节点后......");

System.out.println("前序遍历二叉树结果: ");

tree.preOrder(tree);

System.out.println();

System.out.println("中序遍历二叉树结果: ");

tree.inOrder(tree);

System.out.println();

System.out.println("后序遍历二叉树结果: ");

tree.postOrder(tree);

System.out.println();

System.out.println("层次遍历二叉树结果: ");

tree.LayerOrder(tree);

System.out.println();

System.out.println("F所在的层次: "+tree.level("F"));

System.out.println("这棵二叉树的高度: "+tree.height());

}

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

分块查找

typedef struct

{ int key;

int link;

}SD;

typedef struct

{ int key;

float info;

}JD;

int blocksrch(JD r[],SD nd[],int b,int k,int n)

{ int i=1,j;

while((knd[i].key)(i=b) i++;

if(ib) { printf("\nNot found");

return(0);

}

j=nd[i].link;

while((jn)(k!=r[j].key)(r[j].key=nd[i].key))

j++;

if(k!=r[j].key) { j=0; printf("\nNot found"); }

return(j);

}

哈希查找算法实现

#define M 100

int h(int k)

{ return(k%97);

}

int slbxxcz(int t[],int k)

{ int i,j=0;

i=h(k);

while((jM)(t[(i+j)%M]!=k)(t[(i+j}%M]!=0))

j++;

i=(i+j)%M;

if(t[i]==k) return(i);

else return(-1);

}

int slbxxcr(int t[],int k)

{ int i,j=0;

i=h(k);

while((jM)(t[(i+j)%M]!=k)(t[(i+j}%M]0))

j++;

if(j==M) return(0);

i=(i+j)%M;

if(t[i]=0)

{ t[i]=k; return(1); }

if(t[i]==k) return(1);

}

int slbxxsc(int t[],int k)

{ int i,j=0;

i=h(k);

while((jM)(t[(i+j)%M]!=k)(t[(i+j}%M]!=0))

j++;

i=(i+j)%M;

if(t[i]==k)

{ t[i]=-1; return(1); }

return(0);

}

顺序查找

#define M 500

typedef struct

{ int key;

float info;

}JD;

int seqsrch(JD r[],int n,int k)

{ int i=n;

r[0].key=k;

while(r[i].key!=k)

i--;

return(i);

}

折半查找

int binsrch(JD r[],int n,int k)

{ int low,high,mid,found;

low=1; high=n; found=0;

while((low=high)(found==0))

{ mid=(low+high)/2;

if(kr[mid].key) low=mid+1;

else if(k==r[mid].key) found=1;

else high=mid-1;

}

if(found==1)

return(mid);

else

return(0);

}

虽然都是C++写的，万变不离其中，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实现二叉树层次遍历

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的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于二叉树的遍历算法图解、二叉树的遍历算法java的信息别忘了在本站进行查找喔。