Java 简单树的实现和具体实例 |
您所在的位置：网站首页 › java实现树的方式 › Java 简单树的实现和具体实例 |
Java 简单树的实现和具体实例
|
Java 数据结构基础 简单树的实现与实例##
树与二叉树的实现差不多，二叉树类变量里面有两个子节点，树的类里面有一个树类的链表，下面看具体的实现 public class MuxTree { private MyString data; public MuxTree parent; public List children; //... } //这里的MyString是我自己定义的类，用于解决后面的问题，也可以用模板类代替 //该类有父节点，和子节点的集合。构造函数： public MuxTree(){ this.data = new MyString(""); this.parent = null; this.children = new LinkedList(); } //该构造函数生成一个无子树的节点，因为涉及到后面题目的解决所以父节点的内容为空 public MuxTree(String data, MuxTree parent){ this.data = new MyString(data); this.parent = parent; this.children = new LinkedList(); } //该构造函数返回一个带有父节点，有数据的节点，用于添加节点函数用具体函数： public MuxTree insert(String data, MuxTree parent){ MuxTree child = new MuxTree(data, parent); parent.children.add(child); return child; } //向一个父节点添加一个子节点，该子节点由一个String生成 public MuxTree insert(MyString myString){ String s = myString.getParent().getString(); MuxTree parent = this.search(new MyString(s)); if(parent != null) return this.insert(myString.getString(), parent); else return null; } //现在就是为了解决后面题目所创建的添加函数，根据要插入节点的数据信息查找父节点并插入 //(search();函数在后面实现，它返回是否查找成功，成功返回查找对象，失败返回null) //就像"D:\新建文件夹"是在"D:\"文件夹下，也就是说要找到自己的父节点并插入到相应位置，找不到就直接返回null删除节点： public MuxTree delete(MuxTree parent, int index){ return parent.children.remove(index); } public boolean delete(MuxTree parent, MuxTree child){ return parent.children.remove(child); } //树类的子节点是List实现的，所以删除有两个方法 //一个根据下标索引返回被删除的对象，一个根据对象返回是否删除成功查找函数实现： public MuxTree search(MyString myString){ Queue queue = new LinkedList(); MuxTree p = this; String s = p.data.getString(); while(p != null){ if(p.data.getString().equals(myString.getString())){ return p; } if(p.children != null){ for(MuxTree temp : p.children){ ((LinkedList) queue).add(temp); } } p = queue.poll(); } return null; } //这是典型的广度优先遍历，由一个队列实现。 //从父节点开始便利，先判断是否与自己传入的参数相等，相等返回 //否则开始便利：将父节点add()进队列，如果该父节点有子节点 //就将父节点poll()，并将所有子节点add()进队列，之后执行上两步 //若找不到就直接返回null前序便利： public void preOrder(MuxTree temp){ if(temp == null) return; MuxTree p = temp; int parentNum = 0; if(p.parent != null){ while(p.parent != null){ parentNum += p.data.getString().length(); p = p.parent; } for(int i = 0; i < parentNum; i++){ System.out.print(" "); } System.out.println(temp.data); } for(MuxTree index : temp.children){ preOrder(index); } return ; } //这是深度优先遍历法，由传入的节点开始 //这里题目有一个要求，就是父节点和子节点有一个若干个空格距离的限制 //所以我才在类里引入了父节点，由当前节点开始，判断父节点是否为空 //不为空，则获取父节点的数据长度，重复上一步剩下的函数： public void preOrder(){ this.preOrder(this); return ; } @Override public String toString() { return "MuxTree{" + "data=" + data + '}'; }下面来看一个例题： 键盘键入一个String， 按要求输出 例： 输入： “CC BB AA BB03 AA02 AA03 AA01 AA0303 CC01 AA0304 DD01” 输出：
接着就是主函数了： 为节约时间，我直接用定义好的MyString生成树，并遍历： public static void main(String[] args) { MyString[] myStrings = new MyString[]{new MyString("CC"), new MyString("BB"), new MyString("AA"), new MyString("BB03"), new MyString("AA02"), new MyString("AA03"), new MyString("AA01"), new MyString("AA0303"), new MyString("CC01"), new MyString("AA0304"), new MyString("DD01")}; Arrays.sort(myStrings); MuxTree muxTree = new MuxTree(); for (MyString myString : myStrings) { muxTree.insert(myString); } muxTree.preOrder(); }至于键盘键入数据，将String转换成String[]就不写了。 源码链接： Github：https://github.com/cjf354075714/MuxTree.git |
(这里看到，DD01没有被打印出来，因为DD01没有合适的父目录) 思路：这是一个典型的树的应用题。首先，我们要判断插入的节点是否有自己的合适父节点，没有，则丢弃，有，则对应插入。用户键入的数据没有规律，如果“AA01” 在“AA”之前，则在遍历数组插入时，就会出现先遍历“AA01”，发现没有父节点，因为这时还没有插入“AA”，但之后“AA”是会被正常插入的，所以会出现露插入的情况。 那么怎么解决这个问题？ 我们可以对用户输入的String转化成为String数组(split())，再经行排序。 排序的大小标准是什么？ 首先，字符串长度较短的应该较小，因为一定是前面插入完了，后面才能正常插入。接着，相同长度，应该返回正常的String的比较大小。String的大小比较函数我们不能重载，所以我们新定义一个类实现Comparable接口，就是前面的MyString：【本文地址】
今日新闻 |
推荐新闻 |