java层次遍历二叉树

❶ 用java怎么构造一个二叉树呢

二叉树的相关操作，包括创建，中序、先序、后序（递归和非递归），其中重点的是java在先序创建二叉树和后序非递归遍历的的实现。
package com.algorithm.tree;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class Tree<T> {

private Node<T> root;

public Tree() {
}

public Tree(Node<T> root) {
this.root = root;
}

//创建二叉树
public void buildTree() {

Scanner scn = null;
try {
scn = new Scanner(new File("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
root = createTree(root,scn);
}
//先序遍历创建二叉树
private Node<T> createTree(Node<T> node,Scanner scn) {

String temp = scn.next();

if (temp.trim().equals("#")) {
return null;
} else {
node = new Node<T>((T)temp);
node.setLeft(createTree(node.getLeft(), scn));
node.setRight(createTree(node.getRight(), scn));
return node;
}

}

//中序遍历(递归)
public void inOrderTraverse() {
inOrderTraverse(root);
}

public void inOrderTraverse(Node<T> node) {
if (node != null) {
inOrderTraverse(node.getLeft());
System.out.println(node.getValue());
inOrderTraverse(node.getRight());
}
}

//中序遍历(非递归)
public void nrInOrderTraverse() {

Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
System.out.println(node.getValue());
node = node.getRight();

}

}
//先序遍历(递归)
public void preOrderTraverse() {
preOrderTraverse(root);
}

public void preOrderTraverse(Node<T> node) {
if (node != null) {
System.out.println(node.getValue());
preOrderTraverse(node.getLeft());
preOrderTraverse(node.getRight());
}
}

//先序遍历（非递归）
public void nrPreOrderTraverse() {

Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {
System.out.println(node.getValue());
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
node = node.getRight();
}

}

//后序遍历(递归)
public void postOrderTraverse() {
postOrderTraverse(root);
}

public void postOrderTraverse(Node<T> node) {
if (node != null) {
postOrderTraverse(node.getLeft());
postOrderTraverse(node.getRight());
System.out.println(node.getValue());
}
}

//后续遍历(非递归)
public void nrPostOrderTraverse() {

Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
Node<T> preNode = null;//表示最近一次访问的节点

while (node != null || !stack.isEmpty()) {

while (node != null) {
stack.push(node);
node = node.getLeft();
}

node = stack.peek();

if (node.getRight() == null || node.getRight() == preNode) {
System.out.println(node.getValue());
node = stack.pop();
preNode = node;
node = null;
} else {
node = node.getRight();
}

}

}

//按层次遍历
public void levelTraverse() {
levelTraverse(root);
}

public void levelTraverse(Node<T> node) {

Queue<Node<T>> queue = new LinkedBlockingQueue<Node<T>>();
queue.add(node);
while (!queue.isEmpty()) {

Node<T> temp = queue.poll();
if (temp != null) {
System.out.println(temp.getValue());
queue.add(temp.getLeft());
queue.add(temp.getRight());
}

}

}

}

//树的节点

class Node<T> {

private Node<T> left;
private Node<T> right;
private T value;

public Node() {
}
public Node(Node<T> left,Node<T> right,T value) {
this.left = left;
this.right = right;
this.value = value;
}

public Node(T value) {
this(null,null,value);
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}

}
测试代码：
package com.algorithm.tree;

public class TreeTest {

/**
* @param args
*/
public static void main(String[] args) {
Tree<Integer> tree = new Tree<Integer>();
tree.buildTree();
System.out.println("中序遍历");
tree.inOrderTraverse();
tree.nrInOrderTraverse();
System.out.println("后续遍历");
//tree.nrPostOrderTraverse();
tree.postOrderTraverse();
tree.nrPostOrderTraverse();
System.out.println("先序遍历");
tree.preOrderTraverse();
tree.nrPreOrderTraverse();

//
}

}

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

首先我想问为什么要用LinkedList 来建立二叉树呢? LinkedList 是线性表,
树是树形的, 似乎不太合适。

其实也可以用数组完成，而且效率更高.
关键是我觉得你这个输入本身就是一个二叉树啊，
String input = "ABCDE F G";
节点编号从0到8. 层次遍历的话:
对于节点i.
leftChild = input.charAt(2*i+1); //做子树
rightChild = input.charAt(2*i+2);//右子树

如果你要将带有节点信息的树存到LinkedList里面, 先建立一个节点类:
class Node{
public char cValue;
public Node leftChild;
public Node rightChild;
public Node(v){
this.cValue = v;
}
}

然后遍历input,建立各个节点对象.
LinkedList tree = new LinkedList();
for(int i=0;i< input.length;i++)
LinkedList.add(new Node(input.charAt(i)));

然后为各个节点设置左右子树:
for(int i=0;i<input.length;i++){
((Node)tree.get(i)).leftChild = (Node)tree.get(2*i+1);
((Node)tree.get(i)).rightChild = (Node)tree.get(2*i+2);

}

这样LinkedList 就存储了整个二叉树. 而第0个元素就是树根，思路大体是这样吧。

❹ 层序遍历二叉树

#include<stdio.h>
#include<stdlib.h>
#define m 100
typedef char etype;
typedef struct bitnode
{
etype data;
struct bitnode *lch,*rch;
}bitnode,*bitree;
bitree que[m];
int front=0,rear=0;
bitnode *creat_bt1();
bitnode *creat_bt2();
void preorder(bitnode *p);
void inorder(bitnode *p);
void postorder(bitnode *p);
void enqueue(bitree);
bitree delqueue();
void levorder(bitree);
int treedepth(bitree);
void prtbtree(bitree,int);
void exchange(bitree);
int leafcount(bitree);
void paintleaf(bitree);
bitnode *t;
int count=0;
void main()
{
char ch;int k;
do{
printf("\n\n\n");
printf("\n==========主菜单==============");
printf("\n 1.建立二叉树方法 1");
printf("\n 2.建立二叉树方法 2");
printf("\n 3.先序递归遍历二叉树");
printf("\n 4.中序递归遍历二叉树");
printf("\n 5.后序递归遍历二叉树");
printf("\n 6.层次遍历二叉树");
printf("\n 7.计算二叉树的高度");
printf("\n 8.计算二叉树中叶结点个数");
printf("\n 9.交换二叉树的左右子树");
printf("\n 10.打印二叉树");
printf("\n 0.结束程序运行");
printf("\n===============================");
printf("\n 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)");
scanf("%d",&k);
switch(k)
{case 1:t=creat_bt1();break;
case 2:printf("\n请输入二叉树各节点的值：");fflush(stdin);
t=creat_bt2();break;
case 3:if(t)
{printf("先序遍历二叉树：");
preorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 4:if(t)
{printf("中序遍历二叉树：");
inorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 5:if(t)
{printf("后序遍历二叉树：");
postorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 6:if(t)
{printf("层次遍历二叉树：");
levorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 7:if(t)
{printf("二叉树的高度为：%d",treedepth(t));
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 8:if(t)
{printf("二叉树的叶子结点数为：%d\n",leafcount(t));
printf("二叉树的叶结点数为：");paintleaf(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 9:if(t)
{printf("二叉树的左右子树：\n");
exchange(t);
prtbtree(t,0);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 10:if(t)
{printf("逆时针旋转90度输出的二叉树：\n");
prtbtree(t,0);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 0:exit(0);
}
}while(k>=1&&k<=10);
printf("\n再见! 按回车键，返回…\n");
ch=getchar();
}
bitnode *creat_bt1()
{
bitnode *t,*p,*v[20];int i,j;etype e;
printf("\n请输入二叉树各结点的编号和对应的值(如：1，a):");
scanf("%d,%c",&i,&e);
while(i!=0&&e!='#')
{
p=(bitnode *)malloc(sizeof(bitnode));
p->data=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if(i==1)t=p;
else
{j=i/2;
if(i%2==0) v[j]->lch=p;
else
v[j]->rch=p;
}
printf("\n 请继续输入二叉树各结点的编号和对应的值：");
scanf("%d,%c",&i,&e);
}
return(t);
}
bitnode *creat_bt2()
{
bitnode *t;etype e;
scanf("%c",&e);
if(e=='#')
t=NULL;
else
{
t=(bitnode *)malloc(sizeof(bitnode));
t->data=e;
t->lch=creat_bt2();
t->rch=creat_bt2();
}
return(t);
}
void preorder(bitnode *p){
if(p)
{
printf("%3c",p->data);
preorder(p->lch);
preorder(p->rch);
}
}
void inorder(bitnode *p)
{
if(p){

inorder(p->lch);
printf("%3c",p->data);
inorder(p->rch);
}
}
void postorder(bitnode *p)
{
if(p)
{
postorder(p->lch);
postorder(p->rch);
printf("%3c",p->data);
}
}
void enqueue(bitree T)
{
if(front!=(rear+1)%m)
{rear=(rear+1)%m;
que[rear]=T;}
}
bitree delqueue()
{
if(front==rear)return NULL;
front=(front+1)%m;
return(que[front]);
}
void levorder(bitree T)
{
bitree p;
if(T)
{
enqueue(T);
while(front!=rear)
{
p=delqueue();
printf("%3c",p->data);
if(p->lch!=NULL)enqueue(p->lch);
if(p->rch!=NULL)enqueue(p->rch);
}
}
}
int treedepth(bitree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=treedepth(bt->lch);
hr=treedepth(bt->rch);
max=(hl>hr)? hl:hr;
return(max+1);
}
else
return(0);
}
void prtbtree(bitree bt,int level)
{
int j;
if(bt){
prtbtree(bt->rch,level+1);
for(j=0;j<=6*level+1;j++)printf(" ");
printf("%c\n",bt->data);
prtbtree(bt->lch,level+1);
}
}
void exchange(bitree bt)
{
bitree p;
if(bt)
{p=bt->lch;bt->lch=bt->rch;bt->rch=p;
exchange(bt->lch);exchange(bt->rch);
}
}
int leafcount(bitree bt)
{
if(bt!=NULL)
{
leafcount(bt->lch);
leafcount(bt->rch);
if((bt->lch==NULL)&&(bt->rch==NULL))
count++;
}
return(count);
}
void paintleaf(bitree bt)
{
if(bt!=NULL)
{
if(bt->lch==NULL&&bt->rch==NULL)
printf("%3c",bt->data);
paintleaf(bt->lch);
paintleaf(bt->rch);
}
}

❺ 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)了。

❻ java构建二叉树算法

下面是你第一个问题的解法，是构建了树以后又把后序输出的程序。以前写的，可以把输出后序的部分删除，还有检验先序中序的输入是否合法的代码也可以不要。/*****TreeNode.java*********/public class TreeNode {
char elem;
TreeNode left;
TreeNode right;
}/*******PlantTree.java*********/import java.io.*;
public class PlantTree {
TreeNode root;
public static void main(String[] args) {
PlantTree seed=new PlantTree();
String preorder=null;
String inorder=null;
try {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please input the preorder");
preorder=br.readLine();
System.out.println("Please input the inorder");
inorder=br.readLine();
} catch (Exception e) {
// TODO: handle exception
}

if(preorder!=null&&seed.checkTree(preorder,inorder)) {

seed.root=new TreeNode();
seed.root.elem=preorder.charAt(0);
seed.makeTree(preorder,inorder,seed.root);
System.out.println("The tree has been planted,the postorder is:");
seed.printPostorder(seed.root);
}
}

void makeTree(String preorder,String inorder,TreeNode root) {
int i=inorder.lastIndexOf(root.elem);

if(i!=0) {//有左子树
String leftPre=preorder.substring(1, i+1);
String leftIn=inorder.substring(0,i);
TreeNode leftNode=new TreeNode();
leftNode.elem=leftPre.charAt(0);
root.left=leftNode;
makeTree(leftPre,leftIn,leftNode);
}
if(i!=inorder.length()-1) {//有右子树
String rightPre=preorder.substring(i+1,preorder.length());
String rightIn=inorder.substring(i+1,inorder.length());
TreeNode rightNode=new TreeNode();
rightNode.elem=rightPre.charAt(0);
root.right=rightNode;
makeTree(rightPre,rightIn,rightNode);
}

}
void printPostorder(TreeNode root) {
if(root.left!=null)
printPostorder(root.left);
if(root.right!=null)
printPostorder(root.right);
System.out.print(root.elem);

}
boolean checkTree(String a,String b) {
for(int i=0;i<a.length();i++) {
if(i!=a.lastIndexOf(a.charAt(i))) {
System.out.println("There are same element in the tree");
return false;
}
if(!b.contains(""+a.charAt(i))) {
System.out.println("Invalid input");
return false;
}

}
if(a.length()==b.length())
return true;
return false;
}
}

❼ 二叉树层次遍历怎么进行

设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
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构造二叉树，可以通过链表来构造，如下代码：

public class BinTree {public final static int MAX=40;BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点 int front;//层次遍历时队首 int rear;//层次遍历时队尾private Object data; //数据元数private BinTree left,right; //指向左,右孩子结点的链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(front<rear) { 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 == null&&right == 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 = leftHeight<rightHeight?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(leftLevel<0&&rightLevel<0) return -1; levelInTree = leftLevel<rightLevel?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(){ if(this == null) return; //若本节点是叶节点，则将其移走 if(left==null&&right == null) { System.out.print(this + " "); data = null; return; } //移走左子树若其存在 if(left!=null){ left.defoliate(); left = null; } //移走本节点，放在中间表示中跟移走... String 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());