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

1。 二叉树接口

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); //设置树，用左右子节点
  }

2 节点类

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;
  }
  
}

3.二叉树实现

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设置树t

t.inorderstacktraverse();
system.out.println(t.getheight());
}
}

通过此文，希望能帮助到大家，谢谢大家对本站的支持！