java 数据结构二叉树的实现代码
1。二叉树接口
publicinterfaceBinaryTreeInterface<T>{
publicTgetRootData();
publicintgetHeight();
publicintgetNumberOfRoot();
publicvoidclear();
publicvoidsetTree(TrootData);//用rootData设置树
publicvoidsetTree(TrootData,BinaryTreeInterface<T>left,BinaryTreeInterface<T>right);//设置树，用左右子节点
}
2节点类
packagecom.jimmy.impl;
publicclassBinaryNode<T>{
privateTdata;
privateBinaryNode<T>left;//左子节点
privateBinaryNode<T>right;//右子节点
publicBinaryNode(){
this(null);
}
publicBinaryNode(Tdata){
this(data,null,null);
}
publicBinaryNode(Tdata,BinaryNode<T>left,BinaryNode<T>right){
this.data=data;
this.left=left;
this.right=right;
}
publicTgetData()
{
returndata;
}
publicvoidsetData(Tdata)
{
this.data=data;
}
publicBinaryNode<T>getLeft(){
returnleft;
}
publicvoidsetLeft(BinaryNode<T>left){
this.left=left;
}
publicBinaryNode<T>getRight(){
returnright;
}
publicvoidsetRight(BinaryNode<T>right){
this.right=right;
}
publicbooleanhasLeft()
{returnleft!=null;
}
publicbooleanhasRight()
{returnright!=null;
}
publicbooleanisLeaf()
{return(left==null)&&(right==null);
}
publicintgetHeight()
{
returngetHeight(this);
}
publicintgetHeight(BinaryNode<T>node)
{
inth=0;
if(node!=null)
h=1+Math.max(node.getHeight(node.left),node.getHeight(node.right));
returnh;
}
publicintgetNumOfNodes(){
intlnum=0,rnum=0;
if(left!=null)
lnum=left.getNumOfNodes();
if(right!=null)
rnum=right.getNumOfNodes();
returnlnum+rnum+1;
}
}
3.二叉树实现
packagecom.jimmy.impl;
importjava.util.Stack;
importcom.jimmy.BinaryTreeInterface;
publicclassBinarytree<T>implementsBinaryTreeInterface<T>{
privateBinaryNode<T>root;//只要一个数据节点就够了
//构造空树
publicBinarytree(){
root=null;
}
//用rootData构造树（有个根）
publicBinarytree(Trootdata){
root=newBinaryNode<T>(rootdata);
}
//用其他树构造树
publicBinarytree(Trootdata,Binarytree<T>leftTree,Binarytree<T>rightTree){
root=newBinaryNode<T>(rootdata);
if(leftTree!=null){
root.setLeft(leftTree.root);
}
if(rightTree!=null){
root.setRight(rightTree.root);
}
}
//用rootData设置树（有个根）
@Override
publicvoidsetTree(TrootData){
root=newBinaryNode<T>(rootData);
}
//用其他树设置树
publicvoidsetTree(TrootData,BinaryTreeInterface<T>left,BinaryTreeInterface<T>right){
root=newBinaryNode<T>(rootData);
BinarytreeleftTree=null;
BinarytreerightTree=null;
if((leftTree=(Binarytree)left)!=null){
root.setLeft(leftTree.root);
}
if((rightTree=(Binarytree)right)!=null){
root.setRight(rightTree.root);
}
}
@Override
publicvoidclear(){
root=null;
}
@Override
publicintgetHeight(){
//TODOAuto-generatedmethodstub
returnroot.getHeight();
}
@Override
publicintgetNumberOfRoot(){
//TODOAuto-generatedmethodstub
return0;
}
@Override
publicTgetRootData(){
if(root!=null)
returnroot.getData();
else
returnnull;
}
publicBinaryNode<T>getRoot(){
returnroot;
}
publicvoidsetRoot(BinaryNode<T>root){
this.root=root;
}
publicintgetNumOfNodes(){
returnroot.getNumOfNodes();
}
publicvoidinOrderTraverse(){
inOrderTraverse(root);
}
//用栈方法遍历
publicvoidinOrderStackTraverse(){
Stack<BinaryNode>stack=newStack<BinaryNode>();
BinaryNodecur=root;
//stack.push(root);
while(!stack.isEmpty()||(cur!=null)){
while(cur!=null)
{
stack.push(cur);
cur=cur.getLeft();
}
if(!stack.isEmpty())
{
BinaryNodetmp=stack.pop();
if(tmp!=null)
{System.out.println(tmp.getData());
cur=tmp.getRight();
}
}
}
}
//递归遍历
publicvoidinOrderTraverse(BinaryNode<T>node){
if(node!=null)
{inOrderTraverse(node.getLeft());
System.out.println(node.getData());
inOrderTraverse(node.getRight());
}
}
publicstaticvoidmain(String[]args){
Binarytree<String>t=newBinarytree<String>();
Binarytree<String>t8=newBinarytree<String>("8");
Binarytree<String>t7=newBinarytree<String>("7");
t.setTree("6",t7,t8);//用t7,t8设置树t
t.inOrderStackTraverse();
System.out.println(t.getHeight());
}
}
通过此文，希望能帮助到大家，谢谢大家对本站的支持！