189 8069 5689
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中实现二叉树，程序如下（转载）
//********************************************************************
//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
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;
}
}
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