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装饰者模式