Java中怎么实现一个二叉树
本篇文章为大家展示了Java中怎么实现一个二叉树，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。
创新互联建站专注于企业成都全网营销推广、网站重做改版、榆阳网站定制设计、自适应品牌网站建设、H5响应式网站、商城网站建设、集团公司官网建设、成都外贸网站制作、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为榆阳等各大城市提供网站开发制作服务。
public class BinaryTreeLinked implements BinTree {protected BinTreeNode root;protected Strategy strategy;public BinaryTreeLinked(){ this(null); }public BinaryTreeLinked(BinTreeNode root) { this(root,new DefaultStrategy());}public BinaryTreeLinked(BinTreeNode root, Strategy strategy){this.root = root; this.strategy = strategy;
}
//返回树的规模public int getSize() {return root==null?0:root.getSize();
}//判断树是否为空public boolean isEmpty() { return root==null;}//返回根结点引用public BinTreeNode getRoot() { return root;}//获取树的高度public int getHeight() { return isEmpty()?-1:root.getHeight();}//在树中查找元素e，返回其所在结点public BinTreeNode find(Object e) {return searchE(root,e);
}//递归查找元素eprivate BinTreeNode searchE(BinTreeNode rt, Object e) {if (rt==null) return null;//如果是根结点，返回根if (strategy.equal(rt.getData(),e)) return rt;//否则在左子树中找BinTreeNode v = searchE(rt.getLChild(),e); //没找到，在右子树中找if (v==null) v = searchE(rt.getRChild(),e); return v;
}
这里从e跳到c是难点，重要的是理解递归函数从最里层的递归函数，跳到最外层的函数。
//先序遍历二叉树public Iterator preOrder() {
LinkedList list = new LinkedListDLNode();
preOrderRecursion(this.root,list);return list.elements();
}//先序遍历的递归算法private void preOrderRecursion(BinTreeNode rt, LinkedList list){if (rt==null) return; //递归基,空树直接返回list.insertLast(rt); //访问根结点preOrderRecursion(rt.getLChild(),list); //遍历左子树preOrderRecursion(rt.getRChild(),list); //遍历右子树}//先序遍历的非递归算法private void preOrderTraverse(BinTreeNode rt, LinkedList list){if (rt==null) return;
BinTreeNode p = rt;Stack s = new StackSLinked();while (p!=null){while (p!=null){ //向左走到尽头list.insertLast(p); //访问根if (p.hasRChild()) s.push(p.getRChild()); //右子树根结点入栈p = p.getLChild();
}if (!s.isEmpty()) p = (BinTreeNode)s.pop(); //右子树根退栈遍历右子树}
}
//中序遍历二叉树 public Iterator inOrder(){ LinkedList list = new LinkedListDLNode(); inOrderRecursion(this.root,list); return list.elements(); } //中序遍历的递归算法 private void inOrderRecursion(BinTreeNode rt, LinkedList list){ if (rt==null) return; //递归基,空树直接返回 inOrderRecursion(rt.getLChild(),list); //遍历左子树 list.insertLast(rt); //访问根结点 inOrderRecursion(rt.getRChild(),list); //遍历右子树 } //中序遍历的非递归算法 private void inOrderTraverse(BinTreeNode rt, LinkedList list){ if (rt==null) return; BinTreeNode p = rt; Stack s = new StackSLinked(); while (p!=null||!s.isEmpty()){ while (p!=null){ //一直向左走 s.push(p); //将根结点入栈 p = p.getLChild(); } if (!s.isEmpty()){ p = (BinTreeNode)s.pop();//取出栈顶根结点访问之 list.insertLast(p); p = p.getRChild(); //转向根的右子树进行遍历 }//if }//out while } //后序遍历二叉树 public Iterator postOrder(){ LinkedList list = new LinkedListDLNode(); postOrderRecursion(this.root,list); return list.elements(); } //后序遍历的递归算法 private void postOrderRecursion(BinTreeNode rt, LinkedList list){ if (rt==null) return; //递归基,空树直接返回 postOrderRecursion(rt.getLChild(),list);//遍历左子树 postOrderRecursion(rt.getRChild(),list);//遍历右子树 list.insertLast(rt); //访问根结点 } //后序遍历的非递归算法 private void postOrderTraverse(BinTreeNode rt, LinkedList list){ if (rt==null) return; BinTreeNode p = rt; Stack s = new StackSLinked(); while(p!=null||!s.isEmpty()){ while (p!=null){ //先左后右不断深入 s.push(p); //将根节点入栈 if (p.hasLChild()) p = p.getLChild(); else p = p.getRChild(); } if (!s.isEmpty()){ p = (BinTreeNode)s.pop(); //取出栈顶根结点访问之 list.insertLast(p); } //满足条件时，说明栈顶根节点右子树已访问，应出栈访问之 while (!s.isEmpty()&&((BinTreeNode)s.peek()).getRChild()==p){ p = (BinTreeNode)s.pop(); list.insertLast(p); } //转向栈顶根结点的右子树继续后序遍历 if (!s.isEmpty()) p = ((BinTreeNode)s.peek()).getRChild(); else p = null; } } //按层遍历二叉树 public Iterator levelOrder(){ LinkedList list = new LinkedListDLNode(); levelOrderTraverse(this.root,list); return list.elements(); } //使用对列完成二叉树的按层遍历 private void levelOrderTraverse(BinTreeNode rt, LinkedList list){ if (rt==null) return; Queue q = new QueueArray(); q.enqueue(rt); //根结点入队 while (!q.isEmpty()){ BinTreeNode p = (BinTreeNode)q.dequeue(); //取出队首结点p并访问 list.insertLast(p); if (p.hasLChild()) q.enqueue(p.getLChild());//将p的非空左右孩子依次入队 if (p.hasRChild()) q.enqueue(p.getRChild()); } } }
package dsa.adt;import dsa.adt.List;public interface BinTree {//返回树的规模public int getSize();//判断树是否为空public boolean isEmpty();//返回根结点引用public BinTreeNode getRoot();//获取树的高度public int getHeight();//在树中查找元素e，返回其所在结点public BinTreeNode find(Object e);//先序遍历二叉树public Iterator preOrder();//中序遍历二叉树public Iterator inOrder();//后序遍历二叉树public Iterator postOrder();//按层遍历二叉树public Iterator levelOrder();
}public class BinTreeNode implements Node {private Object data; //数据域private BinTreeNode parent; //父结点private BinTreeNode lChild; //左孩子private BinTreeNode rChild; //右孩子private int height; //以该结点为根的子树的高度private int size; //该结点子孙数（包括结点本身）
public BinTreeNode() {this(null);
}public BinTreeNode(Object e) {
data = e;
parent = lChild = rChild = null;
height = 0;
size = 1;
}
//获得数据域public Object getData() { return data; }
//判断是否有父亲public boolean hasParent(){ return parent!=null;}
//判断是否有右孩子public boolean hasRChild(){ return rChild!=null;}//判断是否为某结点的左孩子public boolean isLChild(){ return (hasParent()&&this==parent.lChild);}//判断是否为某结点的右孩子public boolean isRChild(){ return (hasParent()&&this==parent.rChild);}//取结点的高度,即以该结点为根的树的高度public int getHeight() { return height; }//更新当前结点及其祖先的高度public void updateHeight(){int newH = 0;//新高度初始化为0,高度等于左右子树高度加1中大的if (hasLChild()) newH = Math.max(newH,1+getLChild().getHeight());if (hasRChild()) newH = Math.max(newH,1+getRChild().getHeight());if (newH==height) return; //高度没有发生变化则直接返回height = newH; //否则更新高度if (hasParent()) getParent().updateHeight(); //递归更新祖先的高度}这个更新高度的方法主要用于添加和删除结点，递归的思想在这里使得代码特别简介优美。如果看不懂请结合下面的getParent、getLChild、getRChild方法来看。
//取以该结点为根的树的结点数public int getSize() { return size; }//更新当前结点及其祖先的子孙数public void updateSize(){
size = 1; //初始化为1,结点本身if (hasLChild()) size += getLChild().getSize(); //加上左子树规模if (hasRChild()) size += getRChild().getSize(); //加上右子树规模if (hasParent()) getParent().updateSize(); //递归更新祖先的规模}updateSize和updateHeight是一对兄弟方法。
//取父结点public BinTreeNode getParent() { return parent; }//断开与父亲的关系public void sever(){if (!hasParent()) return;//如果没有父节点则直接结束if (isLChild()) parent.lChild = null;//如果是左孩子则，父节点的左孩子设置为nullelse parent.rChild = null;parent.updateHeight(); //更新父结点及其祖先高度parent.updateSize(); //更新父结点及其祖先规模parent = null;
}
//取左孩子public BinTreeNode getLChild() { return lChild; }//设置当前结点的左孩子,返回原左孩子public BinTreeNode setLChild(BinTreeNode lc){
BinTreeNode oldLC = this.lChild;if (hasLChild()) { lChild.sever();} //断开当前左孩子与结点的关系if (lc!=null){
lc.sever(); //断开lc与其父结点的关系this.lChild = lc; //确定父子关系lc.parent = this;this.updateHeight(); //更新当前结点及其祖先高度this.updateSize(); //更新当前结点及其祖先规模}return oldLC; //返回原左孩子}
//取右孩子public BinTreeNode getRChild() { return rChild; }//设置当前结点的右孩子,返回原右孩子public BinTreeNode setRChild(BinTreeNode rc){
BinTreeNode oldRC = this.rChild;if (hasRChild()) { rChild.sever();} //断开当前右孩子与结点的关系if (rc!=null){
rc.sever(); //断开lc与其父结点的关系this.rChild = rc; //确定父子关系rc.parent = this;this.updateHeight(); //更新当前结点及其祖先高度this.updateSize(); //更新当前结点及其祖先规模}return oldRC; //返回原右孩子}
}设置右孩子方法与设置左孩子方法类似，请参考setLChild方法。
package dsa.adt;public interface Node {//获取结点数据域public Object getData();//设置结点数据域public void setData(Object obj);
}package dsa.strategy;public interface Strategy {//判断两个数据元素是否相等public boolean equal(Object obj1, Object obj2);/** * 比较两个数据元素的大小 * 如果obj1 < obj2 返回-1 * 如果obj1 = obj2 返回0 * 如果obj1 > obj2 返回1 */public int compare(Object obj1, Object obj2);
}package dsa.strategy;public final class DefaultStrategy implements Strategy {public boolean equal(Object obj1, Object obj2)
{return obj1.toString().equals(obj2.toString());
}public int compare(Object obj1, Object obj2)
{int comp = obj1.toString().compareTo(obj2.toString());if (comp==0) return 0;else if (comp>0) return 1;else return -1;
}
}上述内容就是Java中怎么实现一个二叉树，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注创新互联行业资讯频道。
网页名称：Java中怎么实现一个二叉树
网页URL：http://myzitong.com/article/gddojs.html