Java实现多叉树查找

您的位置：
门户
>> 文章精选
>> 软件开发专栏
>> Java
>> 查看资讯

发表于：2016-8-26 11:09

字体：大中小 | 上一篇 | 下一篇 | 我要投稿

作者：华不摇曳来源：51Testing软件测试网采编

软件开发

java

　　1 package tree;

　　3 import java.util.List;

　　4 import java.util.ArrayList;

　　5 import java.io.Serializable;

　　7 public class TreeNode implements Serializable {

　　8 private int parentId;

　　9 private int selfId;

　　10 protected String nodeName;

　　11 protected Object obj;

　　12 protected TreeNode parentNode;

　　13 protected List<TreeNode> childList;

　　15 public TreeNode() {

　　16 initChildList();

　　17 }

　　19 public TreeNode(TreeNode parentNode) {

　　20 this.getParentNode();

　　21 initChildList();

　　22 }

　　24 public boolean isLeaf() {

　　25 if (childList == null) {

　　26 return true;

　　27 } else {

　　28 if (childList.isEmpty()) {

　　29 return true;

　　30 } else {

　　31 return false;

　　32 }

　　33 }

　　34 }

　　36 /* 插入一个child节点到当前节点中 */

　　37 public void addChildNode(TreeNode treeNode) {

　　38 initChildList();

　　39 childList.add(treeNode);

　　40 }

　　42 public void initChildList() {

　　43 if (childList == null)

　　44 childList = new ArrayList<TreeNode>();

　　45 }

　　47 public boolean isValidTree() {

　　48 return true;

　　49 }

　　51 /* 返回当前节点的父辈节点集合 */

　　52 public List<TreeNode> getElders() {

　　53 List<TreeNode> elderList = new ArrayList<TreeNode>();

　　54 TreeNode parentNode = this.getParentNode();

　　55 if (parentNode == null) {

　　56 return elderList;

　　57 } else {

　　58 elderList.add(parentNode);

　　59 elderList.addAll(parentNode.getElders());

　　60 return elderList;

　　61 }

　　62 }

　　64 /* 返回当前节点的晚辈集合 */

　　65 public List<TreeNode> getJuniors() {

　　66 List<TreeNode> juniorList = new ArrayList<TreeNode>();

　　67 List<TreeNode> childList = this.getChildList();

　　68 if (childList == null) {

　　69 return juniorList;

　　70 } else {

　　71 int childNumber = childList.size();

　　72 for (int i = 0; i < childNumber; i++) {

　　73 TreeNode junior = childList.get(i);

　　74 juniorList.add(junior);

　　75 juniorList.addAll(junior.getJuniors());

　　76 }

　　77 return juniorList;

　　78 }

　　79 }

　　81 /* 返回当前节点的孩子集合 */

　　82 public List<TreeNode> getChildList() {

　　83 return childList;

　　84 }

　　86 /* 删除节点和它下面的晚辈 */

　　87 public void deleteNode() {

　　88 TreeNode parentNode = this.getParentNode();

　　89 int id = this.getSelfId();

　　91 if (parentNode != null) {

　　92 parentNode.deleteChildNode(id);

　　93 }

　　94 }

　　96 /* 删除当前节点的某个子节点 */

　　97 public void deleteChildNode(int childId) {

　　98 List<TreeNode> childList = this.getChildList();

　　99 int childNumber = childList.size();

　　100 for (int i = 0; i < childNumber; i++) {

　　101 TreeNode child = childList.get(i);

　　102 if (child.getSelfId() == childId) {

　　103 childList.remove(i);

　　104 return;

　　105 }

　　106 }

　　107 }

　　108

　　109 /* 动态的插入一个新的节点到当前树中 */

　　110 public boolean insertJuniorNode(TreeNode treeNode) {

　　111 int juniorParentId = treeNode.getParentId();

　　112 if (this.parentId == juniorParentId) {

　　113 addChildNode(treeNode);

　　114 return true;

　　115 } else {

　　116 List<TreeNode> childList = this.getChildList();

　　117 int childNumber = childList.size();

　　118 boolean insertFlag;

　　119

　　120 for (int i = 0; i < childNumber; i++) {

　　121 TreeNode childNode = childList.get(i);

　　122 insertFlag = childNode.insertJuniorNode(treeNode);

　　123 if (insertFlag == true)

　　124 return true;

　　125 }

　　126 return false;

　　127 }

　　128 }

　　129

　　130 /* 找到一颗树中某个节点 */

　　131 public TreeNode findTreeNodeById(int id) {

　　132 if (this.selfId == id)

　　133 return this;

　　134 if (childList.isEmpty() || childList == null) {

　　135 return null;

　　136 } else {

　　137 int childNumber = childList.size();

　　138 for (int i = 0; i < childNumber; i++) {

　　139 TreeNode child = childList.get(i);

　　140 TreeNode resultNode = child.findTreeNodeById(id);

　　141 if (resultNode != null) {

　　142 return resultNode;

　　143 }

　　144 }

　　145 return null;

　　146 }

　　147 }

　　148

　　149 /* 遍历一棵树，层次遍历 */

　　150 public void traverse() {

　　151 if (selfId < 0)

　　152 return;

　　153 print(this.selfId);

　　154 if (childList == null || childList.isEmpty())

　　155 return;

　　156 int childNumber = childList.size();

　　157 for (int i = 0; i < childNumber; i++) {

　　158 TreeNode child = childList.get(i);

　　159 child.traverse();

　　160 }

　　161 }

　　162

　　163 public void print(String content) {

　　164 System.out.println(content);

　　165 }

　　166

　　167 public void print(int content) {

　　168 System.out.println(String.valueOf(content));

　　169 }

　　170

　　171 public void setChildList(List<TreeNode> childList) {

　　172 this.childList = childList;

　　173 }

　　174

　　175 public int getParentId() {

　　176 return parentId;

　　177 }

　　178

　　179 public void setParentId(int parentId) {

　　180 this.parentId = parentId;

　　181 }

　　182

　　183 public int getSelfId() {

　　184 return selfId;

　　185 }

　　186

　　187 public void setSelfId(int selfId) {

　　188 this.selfId = selfId;

　　189 }

　　190

　　191 public TreeNode getParentNode() {

　　192 return parentNode;

　　193 }

　　194

　　195 public void setParentNode(TreeNode parentNode) {

　　196 this.parentNode = parentNode;

　　197 }

　　198

　　199 public String getNodeName() {

　　200 return nodeName;

　　201 }

　　202

　　203 public void setNodeName(String nodeName) {

　　204 this.nodeName = nodeName;

　　205 }

　　206

　　207 public Object getObj() {

　　208 return obj;

　　209 }

　　210

　　211 public void setObj(Object obj) {

　　212 this.obj = obj;

　　213 }

　　214 }

《2023软件测试行业现状调查报告》独家发布~

搜索风云榜

测试技术了解

2023测试行业调查报告

挣点稿费

AI与软件测试

文章资料精选