Java 二叉树 java 数据结构二叉树的实现代码
人气:0想了解java 数据结构二叉树的实现代码的相关内容吗,在本文为您仔细讲解Java 二叉树的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:java,数据结构二叉树,java,二叉树,java,实现二叉树,下面大家一起来学习吧。
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()); } }
通过此文,希望能帮助到大家,谢谢大家对本站的支持!
加载全部内容