二叉树的层次遍历java

① 二叉树的层次遍历

设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
void HierarchyBiTree(BiTree Root){
LinkQueue *Q; // 保存当前节点的左右孩子的队列

InitQueue(Q); // 初始化队列

if (Root == NULL) return ; //树为空则返回
BiNode *p = Root; // 临时保存树根Root到指针p中
Visit(p->data); // 访问根节点
if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列

while (!QueueEmpty(Q)) // 若队列不空，则层序遍历 { DeQueue(Q, p); // 出队列
Visit(p->data);// 访问当前节点

if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列
}

DestroyQueue(Q); // 释放队列空间
return ;
这个已经很详细了！你一定可以看懂的！加油啊！

② java层次遍历算法思路

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

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

publicclassBinaryTree{

intdata;//根节点数据
BinaryTreeleft;//左子树
BinaryTreeright;//右子树

publicBinaryTree(intdata)//实例化二叉树类
{
this.data=data;
left=null;
right=null;
}

publicvoidinsert(BinaryTreeroot,intdata){//向二叉树中插入子节点
if(data>root.data)//二叉树的左节点都比根节点小
{
if(root.right==null){
root.right=newBinaryTree(data);
}else{
this.insert(root.right,data);
}
}else{//二叉树的右节点都比根节点大
if(root.left==null){
root.left=newBinaryTree(data);
}else{
this.insert(root.left,data);
}
}
}
}
当建立好二叉树类后可以创建二叉树实例，并实现二叉树的先根遍历，中根遍历，后根遍历，代码如下：
packagepackage2;
publicclassBinaryTreePreorder{

publicstaticvoidpreOrder(BinaryTreeroot){//先根遍历
if(root!=null){
System.out.print(root.data+"-");
preOrder(root.left);
preOrder(root.right);
}
}

publicstaticvoidinOrder(BinaryTreeroot){//中根遍历

if(root!=null){
inOrder(root.left);
System.out.print(root.data+"--");
inOrder(root.right);
}
}

publicstaticvoidpostOrder(BinaryTreeroot){//后根遍历

if(root!=null){
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data+"---");
}
}

publicstaticvoidmain(String[]str){
int[]array={12,76,35,22,16,48,90,46,9,40};
BinaryTreeroot=newBinaryTree(array[0]);//创建二叉树
for(inti=1;i<array.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实现二叉树层次遍历

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(ArrayList<TreeNode> nodes){
if(nodes==null||nodes.size()==0){
return ;
}
level++;
ArrayList<TreeNode> 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);

ArrayList<TreeNode> nodes = new ArrayList<TreeNode>();
nodes.add(root);
findNodeByLevel(nodes);

}

}

⑥ 写一个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 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 实现二叉树的层次遍历

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

分块查找
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((k>nd[i].key)&&(i<=b) i++;
if(i>b) { printf("\nNot found");
return(0);
}
j=nd[i].link;
while((j<n)&&(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((j<M)&&(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((j<M)&&(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((j<M)&&(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(k>r[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 递归 算 二叉树 层级

层次遍历从方法上不具有递归的形式，所以一般不用递归实现。当然了，非要写成递归肯定也是可以的，大致方法如下。 void LevelOrder(BTree T, int cnt) { BTree level = malloc(sizeof(struct BTNode)*cnt); if(level==NULL) return; int i=0,rear=0; if(cnt==0) return; for(i=0; i<cnt; i++){ printf("%c ",T[i].data); if(T[i].lchild) level[rear++]=*T[i].lchild; if(T[i].rchild) level[rear++]=*T[i].rchild; } printf("\n"); LevelOrder(level, rear); free(level); } 补充一下，在main里面调用的时候就得用LevelOrder(T,1)了。