本人需要閱讀代碼，如果覺得閱讀困難可以一步到CSDN
代碼中涉及到的通過先序遍歷和中序遍歷生成一條二叉樹的算法，在本人的另一篇博客通過樹的中序和先序遍歷生成二叉樹中進行了詳細講解。
廣度優(yōu)先搜索算法（Breadth First Search）,又叫寬度優(yōu)先搜索，或橫向優(yōu)先搜索。
? ? ?搜索是從根節(jié)點開始，沿著樹的寬度遍歷樹的節(jié)點。如果所有節(jié)點均被訪問，則算法中止。如右圖所示的二叉樹，A 是第一個訪問的，然后順序是 B、C，然后再是 D、E、F、G。
那么，怎樣才能來保證這個訪問的順序呢？
借助隊列數據結構，由于隊列是先進先出的順序，因此可以先將左子樹入隊，然后再將右子樹入隊。
這樣一來，左子樹結點就存在隊頭，可以先被訪問到。
程序代碼如下
import java.util.LinkedList;
/**
* 二叉樹的廣度優(yōu)先搜索:我們在二叉樹T中搜索節(jié)點N是否存在?
* @author
* 針對這樣一個問題，我們要考慮一下如何解決以下幾個問題:
* 1.使用什么樣的數據結構表示 樹
*? 我們可創(chuàng)建一個類TreeNode,該類包含的屬性應該有:節(jié)點名,左孩子,右孩子, 父節(jié)點? 使用二叉鏈表
*
* 2.如何規(guī)范輸入格式,能夠方便我們進行樹的初始化？
*? 通過樹的中序遍歷和先序遍歷來進行對數的初始化
*
*/
public class Tree {
private TreeNode rootNode;
/**
*
* @param bef 先序遍歷字符串
* @param mid 中序遍歷字符串
* @return 樹的根節(jié)點
*/
public TreeNode creatTree(String bef,String mid) {
String root=bef.substring(0, 1);
int rootindex=mid.indexOf(root);
// System.out.println(rootindex);
String leftBef=bef.substring(1, rootindex+1);
String leftMid=mid.substring(0, rootindex);
// System.out.println("left child:"+leftBef+"? ? "+leftMid);
TreeNode lchild=initTree(leftBef,leftMid);
int len=mid.length();
String rightBef=bef.substring(rootindex+1,len);
String rightMid=mid.substring(rootindex+1,len);
// System.out.println("right child:"+rightBef+"? ? "+rightMid);
TreeNode rchild=initTree(rightBef,rightMid);
rootNode=new TreeNode(root, lchild, rchild);
return rootNode;
}
/**
* 遞歸
* @param bef
* @param mid
* @return
*/
public TreeNode initTree(String bef,String mid) {
if(bef.length()==1&&mid.length()==1) {
return new TreeNode(bef, null, null);
}
// if(bef.length()==2&&mid.length()==2) {? //左子樹為空或者右子樹為空時
// if(bef.charAt(0)==mid.charAt(0)) {
// return new TreeNode(bef.substring(0,1), null, new TreeNode(bef.substring(1,2), null, null));
// }else {
// return new TreeNode(bef.substring(0,1), new TreeNode(mid.substring(0,1), null, null), null);
// }
// }
String root=bef.substring(0, 1);
int rootindex=mid.indexOf(root);
String leftBef=bef.substring(1, rootindex+1);
String leftMid=mid.substring(0, rootindex);
TreeNode lchild=null;
if(leftBef.length()==leftMid.length()&&leftBef.length()!=0) {? //不為空時
lchild=initTree(leftBef,leftMid);
}
int len=mid.length();
String rightBef=bef.substring(rootindex+1,len);
String rightMid=mid.substring(rootindex+1,len);
TreeNode rchild=null;
if(rightMid.length()==rightBef.length()&&rightBef.length()!=0) {
rchild=initTree(rightBef,rightMid);
}
TreeNode rootNode=new TreeNode(root, lchild, rchild);
return rootNode;
}
public static void main(String[] args) {
Tree tree=new Tree();
// System.out.println(tree.rootIndex("ASDFG", "S2"));
// System.out.println("ASF".substring(0, 1));
TreeNode tree2 = tree.creatTree("ABDECFGHI", "DBEAGFHIC");
tree.treeBFS("L");
}
//通過BFS搜索 節(jié)點N是否存在
public void treeBFS(String N) {
LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
queue.add(rootNode); //將根節(jié)點加入隊列中
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
if(node.lchild!=null) {
queue.add(node.lchild);
}
if(node.rchild!=null) {
queue.add(node.rchild);
}
System.out.print(node.nodeName+" ");
if(node.nodeName.equals(N)) {
System.out.println("節(jié)點存在二叉樹中");
return;
}
}
System.out.println("\n節(jié)點不存在");
}
}
/**
* 內部節(jié)點類
* @author 曾鵬
*
*/
class TreeNode{
public String nodeName;
public TreeNode lchild;
public TreeNode rchild;
// public TreeNode parent;
public TreeNode(String nodeName,TreeNode lchild,TreeNode rchild) {
this.nodeName=nodeName;
this.lchild=lchild;
this.rchild=rchild;
// this.parent=parent;
}
}
