java二叉树遍历的代码,二叉树层序遍历java

急求java实现二叉树遍历程序 多少分都行 啊

在JAVA中实现二叉树,程序如下(转载)

我们提供的服务有:网站设计制作、网站设计、微信公众号开发、网站优化、网站认证、驻马店ssl等。为成百上千企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的驻马店网站制作公司

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

//filename: BinaryTreeTest.java

//purpose: test a binarytree with java

//date: 2002/12/18

//author: flyfan

//ver: 0.1

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

public class BinaryTreeTest

{

public static void main(String args[])

{

BinaryTreeTest b=new BinaryTreeTest();

int data[]={12,11,34,45,67,89,56,43,22,98};

BinaryTree root =new BinaryTree(data[0]);

System.out.print("二叉树的中的数据: ");

for(int i=1;i{

root.insertTree(root,data[i]);

System.out.print(data[i-1]+";");

}

System.out.println(data[data.length-1]);

int key=Integer.parseInt(args[0]);

if(b.searchkey(root,key))

{

System.out.println("找到了:"+key);

}

else

{

System.out.println("没有找到:"+key);

}

}

public boolean searchkey(BinaryTree root, int key)

{

boolean bl=false;

if(root==null)

{

bl=false;

return bl;

}

else if(root.data==key)

{

bl=true;

return bl;

}

else if(key=root.data)

{

return searchkey(root.rightpoiter,key);

}

return searchkey(root.leftpoiter,key);

}

}

class BinaryTree

{

int data;

BinaryTree leftpoiter;

BinaryTree rightpoiter;

BinaryTree(int data)

{

this.data=data;

leftpoiter=null;

rightpoiter=null;

}

public void insertTree(BinaryTree root, int data)

{

if(data=root.data)

{

if(root.rightpoiter==null)

{

root.rightpoiter=new BinaryTree(data);

}

else

{

insertTree(root.rightpoiter,data);

}

}

else

{

if(root.leftpoiter==null)

{

root.leftpoiter=new BinaryTree(data);

}

else

{

insertTree(root.leftpoiter,data);

}

}

}

}

//end

二叉树的java实现与几种遍历

二叉树的定义

二叉树(binary tree)是结点的有限集合,这个集合或者空,或者由一个根及两个互不相交的称为这个根的左子树或右子树构成.

从定义可以看出,二叉树包括:1.空树 2.只有一个根节点 3.只有左子树   4.只有右子树  5.左右子树都存在    有且仅有这5种表现形式

二叉树的遍历分为三种:前序遍历 中序遍历 后序遍历

前序遍历:按照“根左右”,先遍历根节点,再遍历左子树 ,再遍历右子树

中序遍历:按照“左根右“,先遍历左子树,再遍历根节点,最后遍历右子树

后续遍历:按照“左右根”,先遍历左子树,再遍历右子树,最后遍历根节点

其中前,后,中指的是每次遍历时候的根节点被遍历的顺序

具体实现看下图:

写一个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 copy 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代码

import java.util.ArrayList;

// 树的一个节点

class TreeNode {

Object _value = null; // 他的值

TreeNode _parent = null; // 他的父节点,根节点没有PARENT

ArrayList _childList = new ArrayList(); // 他的孩子节点

public TreeNode( Object value, TreeNode parent ){

this._parent = parent;

this._value = value;

}

public TreeNode getParent(){

return _parent;

}

public String toString() {

return _value.toString();

}

}

public class Tree {

// 给出宽度优先遍历的值数组,构建出一棵多叉树

// null 值表示一个层次的结束

// "|" 表示一个层次中一个父亲节点的孩子输入结束

// 如:给定下面的值数组:

// { "root", null, "left", "right", null }

// 则构建出一个根节点,带有两个孩子("left","right")的树

public Tree( Object[] values ){

// 创建根

_root = new TreeNode( values[0], null );

// 创建下面的子节点

TreeNode currentParent = _root; // 用于待创建节点的父亲

//TreeNode nextParent = null;

int currentChildIndex = 0; // 表示 currentParent 是他的父亲的第几个儿子

//TreeNode lastNode = null; // 最后一个创建出来的TreeNode,用于找到他的父亲

for ( int i = 2; i values.length; i++ ){

// 如果null ,表示下一个节点的父亲是当前节点的父亲的第一个孩子节点

if ( values[i] == null ){

currentParent = (TreeNode)currentParent._childList.get(0);

currentChildIndex = 0;

continue;

}

// 表示一个父节点的所有孩子输入完毕

if ( values[i].equals("|") ){

if ( currentChildIndex+1 currentParent._childList.size() ){

currentChildIndex++;

currentParent = (TreeNode)currentParent._parent._childList.get(currentChildIndex);

}

continue;

}

TreeNode child = createChildNode( currentParent, values[i] );

}

}

TreeNode _root = null;

public TreeNode getRoot(){

return _root;

}

/**

// 按宽度优先遍历,打印出parent子树所有的节点

private void printSteps( TreeNode parent, int currentDepth ){

for ( int i = 0; i parent._childList.size(); i++ ){

TreeNode child = (TreeNode)parent._childList.get(i);

System.out.println(currentDepth+":"+child);

}

if ( parent._childList.size() != 0 ) System.out.println(""+null);// 为了避免叶子节点也会打印null

//打印 parent 同层的节点的孩子

if ( parent._parent != null ){ // 不是root

int i = 1;

while ( i parent._parent._childList.size() ){// parent 的父亲还有孩子

TreeNode current = (TreeNode)parent._parent._childList.get(i);

printSteps( current, currentDepth );

i++;

}

}

// 递归调用,打印所有节点

for ( int i = 0; i parent._childList.size(); i++ ){

TreeNode child = (TreeNode)parent._childList.get(i);

printSteps( child, currentDepth+1 );

}

}

// 按宽度优先遍历,打印出parent子树所有的节点

public void printSteps(){

System.out.println(""+_root);

System.out.println(""+null);

printSteps(_root, 1 );

}**/

// 将给定的值做为 parent 的孩子,构建节点

private TreeNode createChildNode( TreeNode parent, Object value ){

TreeNode child = new TreeNode( value , parent );

parent._childList.add( child );

return child;

}

public static void main(String[] args) {

Tree tree = new Tree( new Object[]{ "root", null,

"left", "right", null,

"l1","l2","l3", "|", "r1","r2",null } );

//tree.printSteps();

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(0) );

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(1) );

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(2) );

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(0) );

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(1) );

}

}

java:二叉树添加和查询方法

package arrays.myArray;

public class BinaryTree {

private Node root;

// 添加数据

public void add(int data) {

// 递归调用

if (null == root)

root = new Node(data, null, null);

else

addTree(root, data);

}

private void addTree(Node rootNode, int data) {

// 添加到左边

if (rootNode.data data) {

if (rootNode.left == null)

rootNode.left = new Node(data, null, null);

else

addTree(rootNode.left, data);

} else {

// 添加到右边

if (rootNode.right == null)

rootNode.right = new Node(data, null, null);

else

addTree(rootNode.right, data);

}

}

// 查询数据

public void show() {

showTree(root);

}

private void showTree(Node node) {

if (node.left != null) {

showTree(node.left);

}

System.out.println(node.data);

if (node.right != null) {

showTree(node.right);

}

}

}

class Node {

int data;

Node left;

Node right;

public Node(int data, Node left, Node right) {

this.data = data;

this.left = left;

this.right = right;

}

}

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

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二叉树遍历的代码,二叉树层序遍历java
路径分享:http://myzitong.com/article/hcgcgi.html