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()); } }
通过此文,希望能帮助到大家,谢谢大家对本站的支持!