本人需要閱讀代碼遂铡，如果覺得閱讀困難可以一步到CSDN
代碼中涉及到的通過先序遍歷和中序遍歷生成一條二叉樹的算法匣掸，在本人的另一篇博客通過樹的中序和先序遍歷生成二叉樹中進(jìn)行了詳細(xì)講解挂谍。
廣度優(yōu)先搜索算法（Breadth First Search）,又叫寬度優(yōu)先搜索厂庇，或橫向優(yōu)先搜索投剥。
? ? ?搜索是從根節(jié)點(diǎn)開始焕梅，沿著樹的寬度遍歷樹的節(jié)點(diǎn)迹鹅。如果所有節(jié)點(diǎn)均被訪問，則算法中止贞言。如右圖所示的二叉樹斜棚，A 是第一個(gè)訪問的，然后順序是 B该窗、C弟蚀，然后再是 D、E酗失、F义钉、G。
那么规肴，怎樣才能來保證這個(gè)訪問的順序呢捶闸？
借助隊(duì)列數(shù)據(jù)結(jié)構(gòu)夜畴，由于隊(duì)列是先進(jìn)先出的順序，因此可以先將左子樹入隊(duì)删壮，然后再將右子樹入隊(duì)贪绘。
這樣一來，左子樹結(jié)點(diǎn)就存在隊(duì)頭央碟，可以先被訪問到税灌。
程序代碼如下
import java.util.LinkedList;
/**
* 二叉樹的廣度優(yōu)先搜索:我們在二叉樹T中搜索節(jié)點(diǎn)N是否存在?
* @author
* 針對這樣一個(gè)問題，我們要考慮一下如何解決以下幾個(gè)問題:
* 1.使用什么樣的數(shù)據(jù)結(jié)構(gòu)表示 樹
*? 我們可創(chuàng)建一個(gè)類TreeNode,該類包含的屬性應(yīng)該有:節(jié)點(diǎn)名,左孩子,右孩子, 父節(jié)點(diǎn)? 使用二叉鏈表
*
* 2.如何規(guī)范輸入格式,能夠方便我們進(jìn)行樹的初始化硬耍？
*? 通過樹的中序遍歷和先序遍歷來進(jìn)行對數(shù)的初始化
*
*/
public class Tree {
private TreeNode rootNode;
/**
*
* @param bef 先序遍歷字符串
* @param mid 中序遍歷字符串
* @return 樹的根節(jié)點(diǎn)
*/
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) {? //左子樹為空或者右子樹為空時(shí)
// 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) {? //不為空時(shí)
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é)點(diǎn)N是否存在
public void treeBFS(String N) {
LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
queue.add(rootNode); //將根節(jié)點(diǎn)加入隊(duì)列中
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é)點(diǎn)存在二叉樹中");
return;
}
}
System.out.println("\n節(jié)點(diǎn)不存在");
}
}
/**
* 內(nèi)部節(jié)點(diǎn)類
* @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;
}
}
