欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-03-13 12:14:03
1。 二叉树接口 public interface binarytreeinterface { public t getrootdat...

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



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

上一篇: 轻松掌握java装饰者模式

下一篇: