Java中怎么实现一个二叉树

本篇文章为大家展示了Java中怎么实现一个二叉树，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

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中怎么实现一个二叉树，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注亿速云行业资讯频道。