java数据结构之二叉树(一)

1。 二叉树接口
public interface BinaryTreeInterface {
public T getRootData();
public int getHeight();
public int getNumberOfRoot();
public void clear();

public void setTree(T rootData); // 用rootData设置树
public void setTree(T rootData,BinaryTreeInterface left,BinaryTreeInterface right); //设置树，用左右子节点
}
2 节点类
package com.jimmy.impl;

public class BinaryNode {
private T data;
private BinaryNode left; //左子节点
private BinaryNode right; //右子节点
public BinaryNode(){
this(null);
}
public BinaryNode(T data){
this(data,null,null);
}
public BinaryNode(T data,BinaryNode left,BinaryNode right){
this.data=data;
this.left=left;
this.right=right;
}
public T getData()
{
return data;
}
public void setData(T data)
{
this.data= data;
}
public BinaryNode getLeft() {
return left;
}
public void setLeft(BinaryNode left) {
this.left = left;
}
public BinaryNode getRight() {
return right;
}
public void setRight(BinaryNode right) {
this.right = right;
}

public boolean hasLeft()
{return left!=null;

}
public boolean hasRight()
{return right!=null;

}
public boolean isLeaf()
{return (left==null)&&(right==null);

}
public int getHeight()
{
return getHeight(this);
}
public int getHeight(BinaryNode node)
{
int h=0;
if(node!=null)
h=1+Math.max(node.getHeight(node.left),node.getHeight(node.right));

return h;
}
public int getNumOfNodes(){
int lnum=0,rnum=0;
if(left!=null)
lnum=left.getNumOfNodes();
if(right!=null)
rnum=right.getNumOfNodes();
return lnum+rnum+1;
}

}

3.二叉树实现

package com.jimmy.impl;

import java.util.Stack;

import com.jimmy.BinaryTreeInterface;

public class Binarytree implements BinaryTreeInterface {

private BinaryNode root; //只要一个数据节点就够了
// 构造空树
public Binarytree(){
root=null;
}

// 用rootData构造树（有个根）
public Binarytree(T rootdata){
root=new BinaryNode(rootdata) ;
}
// 用其他树构造树
public Binarytree(T rootdata,Binarytree leftTree,Binarytree rightTree){
root=new BinaryNode(rootdata) ;
if(leftTree!=null){
root.setLeft(leftTree.root);
}

if(rightTree!=null){
root.setRight(rightTree.root);
}
}
// 用rootData设置树（有个根）
@Override
public void setTree(T rootData) {
root=new BinaryNode(rootData) ;

}
// 用其他树设置树
public void setTree(T rootData, BinaryTreeInterface left,BinaryTreeInterface right) {
root=new BinaryNode(rootData) ;
Binarytree leftTree=null;
Binarytree rightTree=null;
if((leftTree=(Binarytree)left)!=null){
root.setLeft(leftTree.root);
}

if((rightTree=(Binarytree)right)!=null){
root.setRight(rightTree.root);
}
}

@Override
public void clear() {
root=null;
}

@Override
public int getHeight() {
// TODO Auto-generated method stub
return root.getHeight();
}

@Override
public int getNumberOfRoot() {
// TODO Auto-generated method stub
return 0;
}

@Override
public T getRootData() {