由于没有系统的学习过，所以最近在看算法方面的基础知识点，正好看见数据结构中的树，以前也没有用过，正好写一下。
首先构建一棵树，只创建了子节点属性
public class TreeNode {
Listchildren =new ArrayList();
public ListgetChildren() {
return children;
}
public void setChildren(List children) {
this.children = children;
}
public static ListgetCildren(TreeNode parent){
return parent.getChildren();
}
}
说道遍历，就不得不提深度和广度的问题，广度遍历就是先把同一深度的所有节点遍历完成，如果这些节点中存在子节点，那么再同一遍历下一层深度的所有节点，知道完成为止，而深度遍历呢就是把一条分支一直遍历到终点，再也找不到子级为止，再找上一级有没有同级节点，继续向下遍历
因为不知道树到底有多深，所以首先想到的就是递归，那么递归，先想到了深度递归，这个比较简单：
//深度递归
public void depthRecursion(){
//输入List
List trees =new ArrayList();
if(trees !=null && trees.size()>0){
for(TreeNode child : trees){
//TODD
recursionDepth(child);
}
}
//输入树节点
TreeNode tree =new TreeNode();
recursionDepth(tree);
}
public void recursionDepth(TreeNode tree){
List children = TreeNode.getCildren(tree);
if(children !=null && children.size()>0){
for(TreeNode child : children){
//TODD
recursionDepth(child);
}
}
}
那优先遍历广度呢？广度的话，就想到了用循环，for循环？不行，用for的话循环次数是已知的，但是从第二次循环开始我们就不知道需要循环多少次了，所以使用while循环，可以无限循环，而且也能很方便结束循环
//广度遍历树
public void traverseFor(){
TreeNode parent =new TreeNode();
List children = TreeNode.getCildren(parent);
while (children !=null && children.size()>0){
List curentTreeNode,
allChildren =new ArrayList();
for (TreeNode child : children){
//TODD
curentTreeNode = TreeNode.getCildren(child);
if(curentTreeNode !=null && curentTreeNode.size()>0){
allChildren.addAll(curentTreeNode);
}
}
children = allChildren;
}
}
当然，上面这个遍历也能使用递归实现，只是使用递归替换了while的功能
//广度递归
public void widthRecursion(){
//输入List
List trees =new ArrayList();
recursionWidth(trees);
//输入树节点
TreeNode tree =new TreeNode();
recursionWidth(TreeNode.getCildren(tree));
}
public void recursionWidth(List trees){
List curentTreeNode,
allChildren =new ArrayList();
for (TreeNode child : trees){
//TODD
curentTreeNode = TreeNode.getCildren(child);
if(curentTreeNode !=null && curentTreeNode.size()>0){
allChildren.addAll(curentTreeNode);
}
}
if(allChildren !=null && allChildren.size()>0){
recursionWidth(allChildren);
}
}
树好像有且只有一个根节点。囧。。。反正是为了遍历。就当是多棵树好了。哈哈！
网友评论