增加了對(duì)原帖缺失方法的補(bǔ)充和錯(cuò)誤修改，原帖地址：
http://www.cnblogs.com/toSeeMyDream/p/5816682.html
http://dyygusi.iteye.com/blog/2162617
在編程生活中，我們總會(huì)遇見樹性結(jié)構(gòu)，這幾天剛好需要對(duì)樹形結(jié)構(gòu)操作，就記錄下自己的操作方式以及過程?，F(xiàn)在假設(shè)有一顆這樣樹，（是不是二叉樹都沒關(guān)系，原理都是一樣的）
1、深度優(yōu)先
英文縮寫為DFS即Depth First Search.其過程簡(jiǎn)要來說是對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問一次。對(duì)于上面的例子來說深度優(yōu)先遍歷的結(jié)果就是：A,B,D,E,I,C,F,G,H.(假設(shè)先走子節(jié)點(diǎn)的的左側(cè))。
深度優(yōu)先遍歷各個(gè)節(jié)點(diǎn)，需要使用到堆（Stack）這種數(shù)據(jù)結(jié)構(gòu)。stack的特點(diǎn)是是先進(jìn)后出。整個(gè)遍歷過程如下：
首先將A節(jié)點(diǎn)壓入堆中，stack（A）;
將A節(jié)點(diǎn)彈出，同時(shí)將A的子節(jié)點(diǎn)C，B壓入堆中，此時(shí)B在堆的頂部，stack(B,C)；
將B節(jié)點(diǎn)彈出，同時(shí)將B的子節(jié)點(diǎn)E，D壓入堆中，此時(shí)D在堆的頂部，stack（D,E,C）；
將D節(jié)點(diǎn)彈出，沒有子節(jié)點(diǎn)壓入,此時(shí)E在堆的頂部，stack（E，C）；
將E節(jié)點(diǎn)彈出，同時(shí)將E的子節(jié)點(diǎn)I壓入，stack（I,C）；
...依次往下，最終遍歷完成，Java代碼大概如下：
public void depthFirst() {
Stack<Map<String, Object>> nodeStack = new Stack<Map<String, Object>>();
Map<String, Object> node = new HashMap<String, Object>();
nodeStack.add(node);
while (!nodeStack.isEmpty()) {
node = nodeStack.pop();
System.out.println(node);
//獲得節(jié)點(diǎn)的子節(jié)點(diǎn)，對(duì)于二叉樹就是獲得節(jié)點(diǎn)的左子結(jié)點(diǎn)和右子節(jié)點(diǎn)
List<Map<String, Object>> children = getChildren(node);
if (children != null && !children.isEmpty()) {
for (Map child : children) {
nodeStack.push(child);
}
}
}
}
?//節(jié)點(diǎn)使用Map存放
2、廣度優(yōu)先
英文縮寫為BFS即Breadth FirstSearch。其過程檢驗(yàn)來說是對(duì)每一層節(jié)點(diǎn)依次訪問，訪問完一層進(jìn)入下一層，而且每個(gè)節(jié)點(diǎn)只能訪問一次。對(duì)于上面的例子來說，廣度優(yōu)先遍歷的 結(jié)果是：A,B,C,D,E,F,G,H,I(假設(shè)每層節(jié)點(diǎn)從左到右訪問)。
廣度優(yōu)先遍歷各個(gè)節(jié)點(diǎn)，需要使用到隊(duì)列（Queue）這種數(shù)據(jù)結(jié)構(gòu)，queue的特點(diǎn)是先進(jìn)先出，其實(shí)也可以使用雙端隊(duì)列，區(qū)別就是雙端隊(duì)列首位都可以插入和彈出節(jié)點(diǎn)。整個(gè)遍歷過程如下：
首先將A節(jié)點(diǎn)插入隊(duì)列中，queue（A）;
將A節(jié)點(diǎn)彈出，同時(shí)將A的子節(jié)點(diǎn)B，C插入隊(duì)列中，此時(shí)B在隊(duì)列首，C在隊(duì)列尾部，queue（B，C）；
將B節(jié)點(diǎn)彈出，同時(shí)將B的子節(jié)點(diǎn)D，E插入隊(duì)列中，此時(shí)C在隊(duì)列首，E在隊(duì)列尾部，queue（C，D，E）;
將C節(jié)點(diǎn)彈出，同時(shí)將C的子節(jié)點(diǎn)F，G，H插入隊(duì)列中，此時(shí)D在隊(duì)列首，H在隊(duì)列尾部，queue（D，E，F(xiàn)，G，H）；
將D節(jié)點(diǎn)彈出，D沒有子節(jié)點(diǎn)，此時(shí)E在隊(duì)列首，H在隊(duì)列尾部，queue（E，F(xiàn)，G，H）；
...依次往下，最終遍歷完成，Java代碼大概如下：
public void breadthFirst() {
Deque<Map<String, Object>> nodeDeque = new ArrayDeque<Map<String, Object>>();
Map<String, Object> node = new HashMap<String, Object>();
nodeDeque.add(node);
while (!nodeDeque.isEmpty()) {
node = nodeDeque.peekFirst();
System.out.println(node);
//獲得節(jié)點(diǎn)的子節(jié)點(diǎn)，對(duì)于二叉樹就是獲得節(jié)點(diǎn)的左子結(jié)點(diǎn)和右子節(jié)點(diǎn)
List<Map<String, Object>> children = getChildren(node);
if (children != null && !children.isEmpty()) {
for (Map child : children) {
nodeDeque.add(child);
}
}
}
}
//這里使用的是雙端隊(duì)列，和使用queue是一樣的
1、深度優(yōu)先
英文縮寫為DFS即Depth First Search.其過程簡(jiǎn)要來說是對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止，
而且
每個(gè) 節(jié)點(diǎn)
只能
訪問一次。對(duì)于上面的例子來說深度優(yōu)先遍歷的結(jié)果就是：A,B,D,E,I,C,F,G,H.(假設(shè)先走子節(jié)點(diǎn)的的左側(cè))。
深度優(yōu)先遍歷各個(gè)節(jié)點(diǎn)，需要使用到堆（Stack）這種數(shù)據(jù)結(jié)構(gòu)。stack的特點(diǎn)是是先進(jìn)后出。整個(gè)遍歷過程如下：
首先將A節(jié)點(diǎn)壓入堆中，stack（A）;
將A節(jié)點(diǎn)彈出，同時(shí)將A的子節(jié)點(diǎn)C，B壓入堆中，此時(shí)B在堆的頂部，
stack(B,C)；
將B節(jié)點(diǎn)彈出，同時(shí)將B的子節(jié)點(diǎn)E，D壓入堆中，此時(shí)D在堆的頂部
，stack（D,E,C）；
將D節(jié)點(diǎn)彈出，沒有子節(jié)點(diǎn)壓入,此時(shí)E在堆的頂部
，stack（E，C）；
將E節(jié)點(diǎn)彈出，同時(shí)將E的子節(jié)點(diǎn)I壓入，stack（I,C）；
...依次往下，最終遍歷完成，Java代碼大概如下：
|
public void depthFirst() {
Stack<Map<String, Object>> nodeStack = new Stack<Map<String, Object>>();
Map<String, Object> node = new HashMap<String, Object>();
nodeStack.add(node);
while (!nodeStack.isEmpty()) {
node = nodeStack.pop();
System.out.println(node);
//獲得節(jié)點(diǎn)的子節(jié)點(diǎn)，對(duì)于二叉樹就是獲得節(jié)點(diǎn)的左子結(jié)點(diǎn)和右子節(jié)點(diǎn)
List<Map<String, Object>> children = getChildren(node);
if (children != null && !children.isEmpty()) {
for (Map child : children) {
nodeStack.push(child);
}
}
}
}
?//節(jié)點(diǎn)使用Map存放
|
2、廣度優(yōu)先
英文縮寫為BFS即Breadth FirstSearch。其過程檢驗(yàn)來說是對(duì)每一層節(jié)點(diǎn)依次訪問，訪問完一層進(jìn)入下一層，而且每個(gè)節(jié)點(diǎn)只能訪問一次。對(duì)于上面的例子來說，廣度優(yōu)先遍歷的 結(jié)果是：A,B,C,D,E,F,G,H,I(假設(shè)每層節(jié)點(diǎn)從左到右訪問)。
廣度優(yōu)先遍歷各個(gè)節(jié)點(diǎn)，需要使用到隊(duì)列（Queue）這種數(shù)據(jù)結(jié)構(gòu)，queue的特點(diǎn)是先進(jìn)先出，其實(shí)也可以使用雙端隊(duì)列，區(qū)別就是雙端隊(duì)列首位都可以插入和彈出節(jié)點(diǎn)。整個(gè)遍歷過程如下：
首先將A節(jié)點(diǎn)插入隊(duì)列中，queue（A）;
將A節(jié)點(diǎn)彈出，同時(shí)將A的子節(jié)點(diǎn)B，C插入隊(duì)列中，此時(shí)B在隊(duì)列首，C在隊(duì)列尾部，queue（B，C）；
將B節(jié)點(diǎn)彈出，同時(shí)將B的子節(jié)點(diǎn)D，E插入隊(duì)列中，此時(shí)C在隊(duì)列首，E在隊(duì)列尾部，queue（C，D，E）;
將C節(jié)點(diǎn)彈出，同時(shí)將C的子節(jié)點(diǎn)F，G，H插入隊(duì)列中，此時(shí)D在隊(duì)列首，H在隊(duì)列尾部，queue（D，E，F(xiàn)，G，H）；
將D節(jié)點(diǎn)彈出，D沒有子節(jié)點(diǎn)，此時(shí)E在隊(duì)列首，H在隊(duì)列尾部，queue（E，F(xiàn)，G，H）；
...依次往下，最終遍歷完成，Java代碼大概如下：
|
public void breadthFirst() {
Deque<Map<String, Object>> nodeDeque = new ArrayDeque<Map<String, Object>>();
Map<String, Object> node = new HashMap<String, Object>();
nodeDeque.add(node);
while (!nodeDeque.isEmpty()) {
node = nodeDeque.pollFirst();
System.out.println(node);
//獲得節(jié)點(diǎn)的子節(jié)點(diǎn)，對(duì)于二叉樹就是獲得節(jié)點(diǎn)的左子結(jié)點(diǎn)和右子節(jié)點(diǎn)
List<Map<String, Object>> children = getChildren(node);
if (children != null && !children.isEmpty()) {
for (Map child : children) {
nodeDeque.add(child);
}
}
}
}
//這里使用的是雙端隊(duì)列，和使用queue是一樣的
public static List<Map<String, Object>> getChildren(Map<String, Object> map){
List<Map<String, Object>> list = new ArrayList<>();
Object obj = map.get("son");
if(obj!=null) {
Map<String, Object> value = (HashMap) obj;
list.add(value);
}
Object obj2 = map.get("son2");
if(obj2!=null) {
Map<String, Object> value = (HashMap) obj2;
list.add(value);
}
return list;
};
public static Map<String, Object> getMap(){
Map<String, Object> node = new HashMap<String, Object>();
node.put("mess","我是爸爸");
Map<String, Object> f11 = new HashMap<String, Object>();
f11.put("mess","我是大兒子");
Map<String, Object> f12 = new HashMap<String, Object>();
f12.put("mess","我是二兒子");
Map<String, Object> f21 = new HashMap<String, Object>();
f21.put("mess","我是大孫子");
Map<String, Object> f22 = new HashMap<String, Object>();
f22.put("mess","我是二孫子");
Map<String, Object> f31 = new HashMap<String, Object>();
f31.put("mess","我是大曾孫子");
f21.put("son",f31);
f11.put("son",f21);
f12.put("son",f22);
node.put("son",f11);
node.put("son2",f12);
return node;
}