Java 语言中 二叉树的遍历

很直观的思想，照做就可以了，下面是抄袭自 的样列代码 ：）

公司专注于为企业提供成都网站设计、网站制作、微信公众号开发、成都做商城网站，微信小程序定制开发，软件专业公司等一站式互联网企业服务。凭借多年丰富的经验，我们会仔细了解各客户的需求而做出多方面的分析、设计、整合，为客户设计出具风格及创意性的商业解决方案，创新互联公司更提供一系列网站制作和网站推广的服务。

// 广度优先遍历，给出图邻接矩阵和开始遍历的节点

public static void traverse_BFS(int[][] arcs_in, int begin) {

pre = begin;

if (arcs_in == null || arcs_in.length == 0 ||

arcs_in.length != arcs_in[0].length || begin 0) {

System.err.println("wrong arcs[][] or begin!");

return;

}

arcs = arcs_in;

num = arcs.length;

hasVisit = new boolean[num];

Queue queue = new Queue();

hasVisit[begin] = true;

queue.enQueue(begin);

int temp, min, n = 0;

while (!queue.isEmpty()) {

temp = ( (Integer) queue.deQueue()).intValue();

for (int i = 1; i num; i++) {

// 距离最短的优先入队

min = Integer.MAX_VALUE;

for (int j = 0; j num; j++) {

if (!hasVisit[j] arcs[temp][j] != -1 arcs[temp][j] min) {

min = arcs[temp][j];

n = j;

}

}

if (min == Integer.MAX_VALUE) {

break;

}

else {

hasVisit[n] = true;

queue.enQueue(n);

Main.Q_BFS.enQueue(n);

Main.length_BFS += Main.arcs[pre][n];

pre = n;

}

}

}

}

怎样使用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语言实现二叉树的层次遍历的非递归算法及查找算法。

先序非递归算法

【思路】

假设：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中的遍历是什么意思

标准解释很多地方都有就不贴了。

通俗地解释一下方便理解：

遍，就是全部，历，就是经历，可以理解为查看或者取出。

简单的理解就是全部内容都看一遍。

比如一个数组a包含[1,2,3,4,5]，遍历数组就是指用一个循环或迭代器，把这5个数一个个取出来，打印或者做点其它什么操作。

数组遍历就是数组的全部元素看一遍

树遍历就树的所有节点都看一遍

链表遍历就是链表全部节点都看一遍

刚学的时候我也有这样的疑惑，遍历是什么意思，定义的文字太多，描述的概念太深奥看不懂，理解以后才发现，写个for循环把数组打印出来就算遍历一次了，遍历就是在做这么简单的一件事。

希望我的解释对你的理解有帮助。

分享标题：java代码树的遍历 树的层序遍历java
文章转载：http://azwzsj.com/article/hghspj.html