快捷導(dǎo)航

java 數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的實(shí)現(xiàn)代碼

更新時(shí)間：2016年09月29日 14:10:51 投稿：lqh

這篇文章主要介紹了java 數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的實(shí)現(xiàn)代碼的相關(guān)資料,需要的朋友可以參考下

1。二叉樹(shù)接口

public interface BinaryTreeInterface<T> {
  public T getRootData();
  public int getHeight();
  public int getNumberOfRoot();
  public void clear();
  
  public void setTree(T rootData); // 用rootData設(shè)置樹(shù)
  public void setTree(T rootData,BinaryTreeInterface<T> left,BinaryTreeInterface<T> right); //設(shè)置樹(shù)，用左右子節(jié)點(diǎn)
  }

2 節(jié)點(diǎn)類

package com.jimmy.impl;

public class BinaryNode<T> {
private T data;
private BinaryNode<T> left;  //左子節(jié)點(diǎn)
private BinaryNode<T> right; //右子節(jié)點(diǎn)
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.二叉樹(shù)實(shí)現(xiàn)

package com.jimmy.impl;

import java.util.Stack;

import com.jimmy.BinaryTreeInterface;

public class Binarytree<T> implements BinaryTreeInterface<T> {

  private BinaryNode<T> root;    //只要一個(gè)數(shù)據(jù)節(jié)點(diǎn)就夠了
// 構(gòu)造空樹(shù)
  public Binarytree(){
  root=null;
  }
  

// 用rootData構(gòu)造樹(shù)（有個(gè)根）
  public Binarytree(T rootdata){
    root=new BinaryNode<T>(rootdata) ;
    }
  // 用其他樹(shù)構(gòu)造樹(shù)
  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設(shè)置樹(shù)（有個(gè)根）
  @Override
  public void setTree(T rootData) {
    root=new BinaryNode<T>(rootData) ;
    
  }
// 用其他樹(shù)設(shè)置樹(shù)
  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設(shè)置樹(shù)t

t.inOrderStackTraverse();
System.out.println(t.getHeight());
}
}

通過(guò)此文，希望能幫助到大家，謝謝大家對(duì)本站的支持！

您可能感興趣的文章: