java 数据结构二叉树的实现代码

public interface BinaryTreeInterface<T> {  public T getRootData();  public int getHeight();  public int getNumberOfRoot();  public void clear();    public void setTree(T rootData); // 用rootData设置树  public void setTree(T rootData,BinaryTreeInterface<T> left,BinaryTreeInterface<T> right); //设置树，用左右子节点  }

package com.jimmy.impl;public class BinaryNode<T> {private T data;private BinaryNode<T> left;  //左子节点private BinaryNode<T> right; //右子节点public BinaryNode(){  this(null);}public BinaryNode(T data){  this(data,null,null);}public BinaryNode(T data,BinaryNode<T> left,BinaryNode<T> 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<T> getLeft() {    return left;  }  public void setLeft(BinaryNode<T> left) {    this.left = left;  }  public BinaryNode<T> getRight() {    return right;  }  public void setRight(BinaryNode<T> 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<T> 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;  }  }

package com.jimmy.impl;import java.util.Stack;import com.jimmy.BinaryTreeInterface;public class Binarytree<T> implements BinaryTreeInterface<T> {  private BinaryNode<T> root;    //只要一个数据节点就够了// 构造空树  public Binarytree(){  root=null;  }  // 用rootData构造树（有个根）  public Binarytree(T rootdata){    root=new BinaryNode<T>(rootdata) ;    }  // 用其他树构造树  public Binarytree(T rootdata,Binarytree<T> leftTree,Binarytree<T> rightTree){    root=new BinaryNode<T>(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<T>(rootData) ;      }// 用其他树设置树  public void setTree(T rootData, BinaryTreeInterface<T> left,BinaryTreeInterface<T> right) {    root=new BinaryNode<T>(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() {    if (root!=null)    return root.getData();    else      return null;  }  public BinaryNode<T> getRoot() {    return root;  }  public void setRoot(BinaryNode<T> root) {    this.root = root;  }  public int getNumOfNodes(){  return root.getNumOfNodes();  }  public void inOrderTraverse(){        inOrderTraverse(root);  }  //用栈方法遍历public void inOrderStackTraverse(){    Stack<BinaryNode> stack=new Stack<BinaryNode>();  BinaryNode cur=root;  //stack.push(root);  while(!stack.isEmpty()||(cur!=null)){    while(cur!=null)    {            stack.push(cur);      cur=cur.getLeft();                }    if(!stack.isEmpty())    {      BinaryNode tmp=stack.pop();      if(tmp!=null)      {System.out.println(tmp.getData());      cur=tmp.getRight();            }    }  }}// 递归遍历public void inOrderTraverse(BinaryNode<T> node){        if(node!=null)      {inOrderTraverse(node.getLeft());    System.out.println(node.getData());      inOrderTraverse(node.getRight());      }  }public static void main(String[] args) {Binarytree<String> t=new Binarytree<String>();Binarytree<String> t8=new Binarytree<String>("8");Binarytree<String> t7=new Binarytree<String>("7");t.setTree("6",t7,t8); //用t7,t8设置树tt.inOrderStackTraverse();System.out.println(t.getHeight());}}