青海省住房和城乡建设厅门户网站,汉邦未来网站建设,网站制作价格情况,extract wordpress大意
示例标签串#xff1a;
处理结果#xff1a;
题目1 根据标签串创建树
需求
需求#xff1a;给出一个字符串#xff0c;将这个字符串转换为一棵树。 字符串可以在代码里见到#xff0c;是以#开头#xff0c;按照\分割的字符串。 你需要将这个字符串#xff0…大意
示例标签串
处理结果
题目1 根据标签串创建树
需求
需求给出一个字符串将这个字符串转换为一棵树。 字符串可以在代码里见到是以#开头按照\分割的字符串。 你需要将这个字符串按照树存储为几个长标签串。 请自行编写存储完成后的展示代码。
package com.urfread.review.algorithm.tree;
import org.junit.jupiter.api.Test;import java.util.List;
/*** 1.定义标签结点* 2.定义标签树* 3.根据标签串创建一棵树(你需要保证父标签id的正确性)* 4.输出一棵树的内容*/
class TagNode {Tag tag;ListTagNode children;
}
class Tag {String label;int parentId;int tagId;
}
class TagTree{Tag root;
}public class TreeBuild {Testpublic void buildTreeByStrTest(){// 示例标签串String tagString #计算机技术/编程语言/Java/注解/ #计算机技术/数据结构与算法分析/树/#难度/基础/ #重要程度/一般/;TagNode rootNode buildTreeByStr(tagString);// 自行编写输出展示的代码}public static TagNode buildTreeByStr(String str){TagNode rootNode new TagNode();// START// 请在此编写代码// ENDreturn rootNode;}
}实现思路
以下给出代码不能匹配这个练习题这是我实际开发的时候编写的代码 只能当做是伪代码
处理根节点。根节点不需要考虑标签内容直接创建即可。
// 创建根节点
TreeNode rootNode new TreeNode(null); // 根节点无需标签
rootNode.setTag(new Tag(0,,0));//但还是给一个以防空指针异常为了保证标签id的正确性所以做了特殊处理
int id 1; // 标签节点的ID从1开始
lastTagIdMap.put(rootNode, id);//在方法外定义的HashMap。含义为下一个被添加的结点的id。在开始处理字符串之前我们需要考虑这样一个问题如何在树中添加一个结点 我们需要知道一些特征添加到哪个结点的孩子中、添加的标签是什么。 比如现在我们已经创建了根结点那我们肯定会把下一个结点添加在根结点的孩子中 那么结点的内容怎么取 我们的标签是以#号开头的所以去掉#就可以了。但是后边还连着一堆按\分割的子标签那现在怎么办 我们首先按\将字符串分割为字符串数组现在就可以放心的处理第一个结点了。如何处理第二个结点 分情况我们是该另开辟一条路径还是接着刚才的结点往后续。 区分依据就是看这个标签开头是不是#如果是那么就应该另开辟一条路径如果不是就直接续。 也就是说我们需要保存上一个结点的引用不然就不知道该把当前结点添加给谁当孩子了。特殊情况处理
标签的id记着手动增长。其实到后边标签的id可以表示它加入到这课树中的顺序在存到数据库时可以进行特殊操作。
分叉如果遇到两个标签串前半部分一样后来分叉怎么处理如果一样只移动结点指针不再创建。
答案
package com.urfread.review.algorithm.tree;import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.Getter;
import lombok.NoArgsConstructor;
import org.junit.jupiter.api.Test;import java.util.List;
/*** 1.定义标签结点* 2.定义标签树* 3.根据标签串创建一棵树 (你需要保证父标签id的正确性)* 4.输出处理结果*/
Data
NoArgsConstructor
Getter
class TagNode {Tag tag;ListTagNode children;public TagNode(Tag tag) {this.tag tag;}public void addChild(TagNode child) {if (children null) {children new java.util.LinkedList();}children.add(child);}
}
Data
AllArgsConstructor
class Tag {int tagId;String label;int parentId;
}
class TagTree{Tag root;
}public class TreeBuild {Testpublic void buildTreeByStrTest(){// 示例标签串String tagString #计算机技术/编程语言/Java/注解/ #计算机技术/数据结构与算法分析/树/#难度/基础/ #重要程度/一般/;TagNode rootNode buildTreeByStr(tagString);// 自行编写输出展示的代码printTree(rootNode);}public static TagNode buildTreeByStr(String tagStr){TagNode rootNode new TagNode();// START// 请在此编写代码rootNode.setTag(new Tag(0,,0));int id1;String[]tagstagStr.split(/);TagNode currentNoderootNode;for(String tag:tags){if (tag.startsWith(#)){currentNoderootNode;tagtag.substring(1);}boolean isExistfalse;if(currentNode.getChildren()!null)// 判断是否已经插入for (TagNode child:currentNode.getChildren()){if (child.getTag().getLabel().equals(tag)){// 如果已经存在则只做移动指针的操作currentNodechild;isExisttrue;break;}}// 如果不存在才会继续添加if (!isExist){TagNode newTagNodenew TagNode(new Tag(id,tag,currentNode.getTag().getTagId()));currentNode.addChild(newTagNode);currentNodenewTagNode;}}// ENDreturn rootNode;}// 输出一棵树,请添加一些分级缩进public static void printTree(TagNode rootNode){// START// 请在此编写代码if (rootNode!nullrootNode.getChildren()!null)for (TagNode child:rootNode.getChildren()){printTree(child,1);}// END}public static void printTree(TagNode rootNode,int level){if (rootNode!null){for (int i0;ilevel;i){System.out.print( );}System.out.println(rootNode.getTag().getLabel());if (rootNode.getChildren()!null)for (TagNode child:rootNode.getChildren()){printTree(child,level1);}}}
}
