java搜索二叉树代码 二叉搜索树 java

用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(frontrear)

{

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 == nullright == 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 = leftHeightrightHeight?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(leftLevel0rightLevel0)

return -1;

levelInTree = leftLevelrightLevel?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==nullright == 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());

}

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

在JAVA中实现二叉树，程序如下（转载）

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

//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代码

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实现二叉树

import java.util.List;

import java.util.LinkedList;

public class Bintrees {

private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};

private static ListNode nodeList = null;

private static class Node {

Node leftChild;

Node rightChild;

int data;

Node(int newData) {

leftChild = null;

rightChild = null;

data = newData;

}

}

// 创建二叉树

public void createBintree() {

nodeList = new LinkedListNode();

// 将数组的值转换为node

for (int nodeIndex = 0; nodeIndex array.length; nodeIndex++) {

nodeList.add(new Node(array[nodeIndex]));

}

// 对除最后一个父节点按照父节点和孩子节点的数字关系建立二叉树

for (int parentIndex = 0; parentIndex array.length / 2 - 1; parentIndex++) {

nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);

nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);

}

// 最后一个父节点

int lastParentIndex = array.length / 2 - 1;

// 左孩子

nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);

// 如果为奇数，建立右孩子

if (array.length % 2 == 1) {

nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);

}

}

// 前序遍历

public static void preOrderTraverse(Node node) {

if (node == null) {

return;

}

System.out.print(node.data + " ");

preOrderTraverse(node.leftChild);

preOrderTraverse(node.rightChild);

}

// 中序遍历

public static void inOrderTraverse(Node node) {

if (node == null) {

return;

}

inOrderTraverse(node.leftChild);

System.out.print(node.data + " ");

inOrderTraverse(node.rightChild);

}

// 后序遍历

public static void postOrderTraverse(Node node) {

if (node == null) {

return;

}

postOrderTraverse(node.leftChild);

postOrderTraverse(node.rightChild);

System.out.print(node.data + " ");

}

public static void main(String[] args) {

Bintrees binTree = new Bintrees();

binTree.createBintree();

Node root = nodeList.get(0);

System.out.println("前序遍历：");

preOrderTraverse(root);

System.out.println();

System.out.println("中序遍历：");

inOrderTraverse(root);

System.out.println();

System.out.println("后序遍历：");

postOrderTraverse(root);

}

}

输出结果：

前序遍历：

1 2 4 8 9 5 3 6 7

中序遍历：

8 4 9 2 5 1 6 3 7

后序遍历：

8 9 4 5 2 6 7 3 1