一映九、二叉樹的層次遍歷原理
如圖所示為二叉樹的層次遍歷，即按照箭頭所指方向瞎颗，按照1件甥、2、3哼拔、4的層次順序引有，對二叉樹中各個結(jié)點進行訪問(此圖反映的是自左至右的層次遍歷，自右至左的方式類似)倦逐。
二叉樹層次遍歷
要進行層次遍歷譬正，需要建立一個循環(huán)隊列。先將二叉樹頭結(jié)點入隊列，然后出隊列曾我，訪問該結(jié)點粉怕，如果它有左子樹，則將左子樹的根結(jié)點入隊:如果它有右子樹抒巢，則將右子樹的根結(jié)點入隊贫贝。然后出隊列，對出隊結(jié)點訪問蛉谜，如此反復稚晚，直到隊列為空為止。
整體上結(jié)合具體數(shù)據(jù)還是比較好理解的
這里需要注意的是對出隊列的結(jié)點進行訪問
二型诚、實現(xiàn)代碼
創(chuàng)建二叉樹的方法前面文章已經(jīng)寫到了客燕，這里直接調(diào)用，下面來看實現(xiàn)的方法
（注：隊列方面我們使用java提供的ArrayDeque工具類）
public static void level(BTNode node) {
ArrayDeque<BTNode> queue = new ArrayDeque<>(20);
//首先將根節(jié)點加入棧中
queue.add(node);
//遍歷二叉樹
while (!queue.isEmpty()) {
BTNode tempNode = queue.poll();
System.out.print(tempNode.data + " ");
if(tempNode.leftChild != null){
queue.add(tempNode.leftChild);
}
if(tempNode.rightChild != null){
queue.add(tempNode.rightChild);
}
}
}
三俺驶、測試代碼
/**
* 構(gòu)建二叉樹
* 3
* 2 4
* 5 2 2 4
* 5
* @param args
*/
public static void main(String[] args) {
int[] a = {3,2,4,5,2,2,4,5};
BTNode root = BTNodeUtil.createBTNodebyArray(a);
System.out.print("層次遍歷為：");
level(root);
}
輸出結(jié)果為：
層次遍歷為：3 2 4 5 2 2 4 5
