二叉樹層次遍歷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(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);

}

}

❷ 二叉樹的層次遍歷演算法

二叉樹的層次遍歷演算法有如下三種方法：

給定一棵二叉樹，要求進行分層遍歷，每層的節點值單獨列印一行，下圖給出事例結構：

之後大家就可以自己畫圖了，下面給出程序代碼：

[cpp] view plain

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

最後給出完成代碼的測試用例：124##57##8##3#6##

[cpp] view plain

#include<iostream>

#include<vector>

#include<deque>

using namespace std;

typedef struct tree_node_s {

char data;

struct tree_node_s *lchild;

struct tree_node_s *rchild;

}tree_node_t, *Tree;

void create_tree(Tree *T) {

char c = getchar();

if (c == '#') {

*T = NULL;

} else {

*T = (tree_node_t*)malloc(sizeof(tree_node_t));

(*T)->data = c;

create_tree(&(*T)->lchild);

create_tree(&(*T)->rchild);

}

}

void print_tree(Tree T) {

if (T) {

cout << T->data << " ";

print_tree(T->lchild);

print_tree(T->rchild);

}

}

int print_at_level(Tree T, int level) {

if (!T || level < 0)

return 0;

if (0 == level) {

cout << T->data << " ";

return 1;

}

return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);

}

void print_by_level_1(Tree T) {

int i = 0;

for (i = 0; ; i++) {

if (!print_at_level(T, i))

break;

}

cout << endl;

}

void print_by_level_2(Tree T) {

deque<tree_node_t*> q_first, q_second;

q_first.push_back(T);

while(!q_first.empty()) {

while (!q_first.empty()) {

tree_node_t *temp = q_first.front();

q_first.pop_front();

cout << temp->data << " ";

if (temp->lchild)

q_second.push_back(temp->lchild);

if (temp->rchild)

q_second.push_back(temp->rchild);

}

cout << endl;

q_first.swap(q_second);

}

}

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

int main(int argc, char *argv[]) {

Tree T = NULL;

create_tree(&T);

print_tree(T);

cout << endl;

print_by_level_3(T);

cin.get();

cin.get();

return 0;

}

❸ 怎樣使用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 實現二叉樹的層次遍歷

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 遞歸 算 二叉樹 層級

層次遍歷從方法上不具有遞歸的形式，所以一般不用遞歸實現。當然了，非要寫成遞歸肯定也是可以的，大致方法如下。 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)了。

❻ 二叉樹層次遍歷

/**
*層序遍歷
*/
voidLevelOrderTraversal(BinTree*BT){
	BinTree*T;
	T=BT;
	if(!T){
		return;
	}
	Queue*Q=InitQueue();	/*生成一個隊列*/
	EnQueue(Q,T);		/*根節點入隊*/
	while(!IsQueueEmpty(Q)){		/*隊列不為空,彈出一個元素*/
		T=DeQueue(Q);
		Visited(T);		/*訪問*/
		if(T->Left)		/*左子樹不為空入隊*/
			EnQueue(Q,T->Left);
		if(T->Right)	/*右子樹不為空入隊*/
			EnQueue(Q,T->Right);
	}
}

你的代碼貌似不對，原因是：你只是把根節點進了隊列！看看我寫的！

同時你也可以直接用網路搜索「C實現二叉樹（模塊化集成，遍歷的遞歸與非遞歸實現）」，這是博客園的一個博文，裡面有關二叉樹的前中後層遍歷的遞歸與非遞歸演算法，比較全面。

❼ 用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層次遍歷二叉樹,簡單點就可以,我要的是代碼,不是純文字說明

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層次遍歷演算法思路

找個例子看一下就有了。比如遞歸前序遍歷二叉樹，即先根遍歷。先遍歷根節點，之後向下又是一個跟節點，在遍歷做節點，在遍歷右節點，依次下去，知道沒有右節點結束。在遍歷右邊的部分，根節點，左節點，右節點，知道沒有右節點是為止。至此遍歷結束。書上有圖一看就知道了。其他的遍歷按照遍歷演算法一樣。建議看下數據結構的遍歷，講的很詳細。

❿ 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;
}
}