범위 우선 깊이 우선 접근 트 리
public class Tst {
static TreeNode treeFactory() {
TreeNode a = new TreeNode("a");
TreeNode b = new TreeNode("b");
TreeNode c = new TreeNode("c");
TreeNode d = new TreeNode("d");
TreeNode e = new TreeNode("e");
TreeNode f = new TreeNode("f");
TreeNode g = new TreeNode("g");
TreeNode h = new TreeNode("h");
a.children.add(b); a.children.add(c);
b.children.add(d); b.children.add(e);
c.children.add(f); c.children.add(g);
e.children.add(h);
return a;
}
static void printTreeDepthFirst(TreeNode root) {
System.out.print(root);
if(! root.children.isEmpty()) {
for(TreeNode child : root.children)
printTreeDepthFirst(child);
}
}
static ArrayList<ArrayList<TreeNode>> row;
static void printTreeWidthFirst(TreeNode root) {
transferTree(root, 0);
for(ArrayList<TreeNode> list : row) {
for(TreeNode node : list)
System.out.print(node);
}
}
private static void transferTree(TreeNode root, int i) {
putNode2row(root, i);
if(! root.children.isEmpty()) {
i++;
for(TreeNode child : root.children)
transferTree(child, i);
}
}
private static void putNode2row(TreeNode node, int i) {
if(row.size() <= i) {
row.add(new ArrayList<TreeNode>());
}
row.get(i).add(node);
}
public static void main(String[] args) {
printTreeDepthFirst(treeFactory());
System.out.println();
row = new ArrayList<ArrayList<TreeNode>>();
printTreeWidthFirst(treeFactory());
}
}
class TreeNode {
List<TreeNode> children = new ArrayList<TreeNode>();
String name;
public TreeNode(String name) {
this.name = name;
}
public String toString() {
return name;
}
}
출력
abdehcfg
abcdefgh
위의 코드 의 넓이 가 우선 적 인 것 은 먼저 재 귀적 으로 옮 겨 다 니 며 재 귀적 인 데 이 터 를 List 의 List 에 넣 고 층 의 구조 로 바 꾸 는 것 입 니 다.공간 과 시간 을 비교적 많이 사용한다.'데이터 구조 P170' 을 보고 그림 의 넓이 를 우선적으로 옮 겨 다 녔 다.Queue 를 사용 하여 현재 층 의 노드 를 저장 하고 이 방법 을 최적화 할 수 있 습 니 다.
static void printTreeWidthFirst(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
queue.add(root);
System.out.print(root);
while(!queue.isEmpty()) {
root = queue.poll();
for(TreeNode child : root.children) {
System.out.print(child);
queue.add(child);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
예제 1.15 UVALive-3902 트리의 검색컨베이어 도어 제목 대의: n대의 기계는 하나의 트리 네트워크로 연결되어 잎 노드는 클라이언트이고 다른 노드는 서버이다. 처음에는 한 대의 서버만 하나의 서비스를 제공했지만 k의 거리 내의 클라이언트만 덮어쓸 수 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.