java遍历树
如现有以下一颗树：A B B1 B11 B2 B22 C C1 C11 C12 C2 D D1 D11

第一种方式深度优先遍历（最终返回的一棵压扁的树，依次从上往下）使用Stack，由于stack是先进后出，故实现方式为：
首先push一个初始节点到stack中，假定为A，
循环这个stack，只要不为空则循环不结束，从stack中pop出第一个元素，把次元素放到一个list中，作为树的返回结果显示，获取次元素的下一级子元素，如果有则把他们都push到stack中。
首先第一次进入循环的stack中只有A，把A元素从stack中pop出来后，第一个被放到list里，然后获取到A的一级子元素（BCD），把他们push到stack中，此时stack中有三个元素（BCD），进入第二次循环。
这次循环从stack中pop出第一个元素B（注：这里的BCD获取的先后顺序符合先进后出原则）把B元素从stack中pop出来后，第一个被放到list里，然后获取到A的一级子元素（B1B2），把他们push到stack中，此时stack中有元素（B1B2CD），进入第三次循环。
这次循环从stack中pop出的应该是B1或者B2中的一个，后面和上诉的循环一致。
获取的结果为A B B1 B11 B2 B22 C C1 C11 C12 C2 D D1 D11
第二种方式广度优先遍历使用list，由于list是集合，集合是先进先出，故实现方式为：
首先add一个初始节点到list中，假定为A，循环这个list，只要不为空，则循环不结束，从这个list中取出第一个元素即A放到result（假定也是一个list）中，并且remove这个元素。然后获取到A的一级子元素（BCD），把他们放到list中，此时list中有三个元素（BCD），进入第二次循环。
这次循环从list中取出第一个元素即B然后放到result中，并且remove这个元素。把B的一级子元素（B1B2）放入result中，此时list中元素为（CDB1B2）,进入第三次循环。
这次循环和上两次一样，取出的第一个元素是C。
获取的结果为A B C D B1 B2 C1 C2 D1 B11 B22 C11 C12 D11

package com.order;

import java.util.ArrayList;

import java.util.Collection;

import java.util.List;

import java.util.Stack;

public class MytreeOrder {

 private static List<String> allElement = new ArrayList<String>();

 public static void setElement() {

  allElement.add("A");

  allElement.add("A1");

  allElement.add("A2");

  allElement.add("A3");

  allElement.add("A4");

  allElement.add("A11");

  allElement.add("A21");

  allElement.add("A22");

  allElement.add("A41");

  allElement.add("A42");

  allElement.add("A111");

  allElement.add("A421");

 }

 public static void main(String[] args) {

  setElement();

  deepOrder("A");

  broadOrder("A");

 }

 // 深度遍历

 public static void deepOrder(String oneElement) {

  if (allElement.contains(oneElement)) {

   Stack<String> s = new Stack<String>();

   s.push(oneElement);

   while (!s.isEmpty()) {

    String now = s.pop();

    StringBuffer t = getSpace(now);

    System.out.println(t.toString() + now);

    s.addAll(getChild("deep", now));

   }

  }

 }

 // 根据传入的string元素来返回需要的空格

 private static StringBuffer getSpace(String now) {

  StringBuffer t = new StringBuffer("");

  for (int i = 0; i < now.length(); i++) {

   t.append(" ");

  }

  return t;

 }

 // 获取子元素

 private static Collection<String> getChild(String mode, String oneElement) {

  List<String> childs = new ArrayList<String>();

  for (int i = 0; i < allElement.size(); i++) {

   if (allElement.get(i).toString().length() == oneElement.length() + 1

     && (allElement.get(i).toString().substring(0,

       oneElement.length()).equals(oneElement))) {

    if (mode.equals("deep")) {

     // 此处保证集合中最后一个元素是需要显示在当前层级中第一个展示的子节点（因为堆栈中是最后一个元素先出）

     if (childs != null

       && childs.size() != 0

       && Integer.valueOf(allElement.get(i).toString()

         .substring(1)) > Integer.valueOf(childs

         .get(0).toString().substring(1))) {

      childs.add(0, allElement.get(i));

     } else {

      childs.add(allElement.get(i));

     }

    } else {

     if (childs != null

       && childs.size() != 0

       && Integer.valueOf(allElement.get(i).toString()

         .substring(1)) < Integer.valueOf(childs

         .get(0).toString().substring(1))) {

      childs.add(0, allElement.get(i));

     } else {

      childs.add(allElement.get(i));

     }

    }

   }

  }

  return childs;

 }

 // 广度遍历

 private static void broadOrder(String oneElement) {

  if (allElement.contains(oneElement)) {

   List<String> l = new ArrayList<String>();

   l.add(oneElement);

   while (!l.isEmpty()) {

    String now = l.get(0);

    l.remove(0);

    StringBuffer t = getSpace(now);

    System.out.println(t.toString() + now);

    l.addAll(getChild("broad", now));

   }

  }

 }

}

巴特西

java遍历树（深度遍历和广度遍历

最新文章

热门文章