由于沒有系統(tǒng)的學習過，所以最近在看算法方面的基礎知識點，正好看見數(shù)據(jù)結(jié)構(gòu)中的樹，以前也沒有用過，正好寫一下。
首先構(gòu)建一棵樹，只創(chuàng)建了子節(jié)點屬性
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();
? ? }
}
? ? 說道遍歷，就不得不提深度和廣度的問題，廣度遍歷就是先把同一深度的所有節(jié)點遍歷完成，如果這些節(jié)點中存在子節(jié)點，那么再同一遍歷下一層深度的所有節(jié)點，知道完成為止，而深度遍歷呢就是把一條分支一直遍歷到終點，再也找不到子級為止，再找上一級有沒有同級節(jié)點，繼續(xù)向下遍歷
? ? 因為不知道樹到底有多深，所以首先想到的就是遞歸，那么遞歸，先想到了深度遞歸，這個比較簡單：
//深度遞歸
public void depthRecursion(){
//輸入List
? ? List trees =new ArrayList();
? ? if(trees !=null && trees.size()>0){
for(TreeNode child : trees){
//TODD
? ? ? ? ? ? recursionDepth(child);
? ? ? ? }
}
//輸入樹節(jié)點
? ? 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);
? ? ? ? }
}
}
? ? 那優(yōu)先遍歷廣度呢？廣度的話，就想到了用循環(huán)，for循環(huán)？不行，用for的話循環(huán)次數(shù)是已知的，但是從第二次循環(huán)開始我們就不知道需要循環(huán)多少次了，所以使用while循環(huán)，可以無限循環(huán)，而且也能很方便結(jié)束循環(huán)
//廣度遍歷樹
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;
? ? }
}
? ? 當然，上面這個遍歷也能使用遞歸實現(xiàn)，只是使用遞歸替換了while的功能
? ?//廣度遞歸
public void widthRecursion(){
//輸入List
? ? List trees =new ArrayList();
? ? recursionWidth(trees);
? ? //輸入樹節(jié)點
? ? 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);
? ? }
}
? ? 樹好像有且只有一個根節(jié)點。囧。。。反正是為了遍歷。就當是多棵樹好了。哈哈！
