1 树
树，顾名思义，长得像一棵树，不过通常我们画成一棵倒过来的树，根在上，叶在下。
1.1 树的一些概念
树还可以表示成下面这种方式：
从上图可以看出：树可以用来描述包含关系，但包含关系不得出现交叉重叠区域，否则就不能用树描述。
2 树的遍历
2.1 广度优先遍历
对于树的广度优先遍历，可以使用队列来完成。
示例：
树节点类：
public class Node { private String name; private List childs; public Node(String name) { super(); this.name = name; } public String getName() { return name; } public List getChilds() { return childs; } public void setChilds(List childs) { this.childs = childs; }} 测试代码：
public class Test { public static void main(String[] args) { // 构造节点 Node a = new Node("A"); Node b = new Node("B"); Node c = new Node("C"); Node d = new Node("D"); Node e = new Node("E"); Node f = new Node("F"); Node g = new Node("G"); Node h = new Node("H"); Node i = new Node("I"); Node j = new Node("J"); Node k = new Node("K"); Node l = new Node("L"); // 构造树 a.setChilds(Arrays.asList(b, c, d)); b.setChilds(Arrays.asList(e, f)); d.setChilds(Arrays.asList(g, h, i)); f.setChilds(Arrays.asList(j, k)); h.setChilds(Arrays.asList(l)); // 创建队列 Queue que = new ArrayDeque (); que.offer(a); // 操作队列 while (!que.isEmpty()) { Node temp = que.poll(); System.out.print(temp.getName()); List childs = temp.getChilds(); if (childs != null) { for (int iter = 0; iter < childs.size(); iter++) { que.offer(childs.get(iter)); } } } }} 输出结果
ABCDEFGHIJKL
队列的状况如下图：
2.2 深度优先遍历
深度有限遍历分为：前序遍历（Preorder Traversal），后序遍历（Postorder Traversal）和中序遍历（Inorder Traversal）。
其中中序遍历只有对二叉树才有意义。
树：
2.2.1 前序遍历：
package com.demo2;import java.util.List;//树节点public class Node { private String name; private List childs; public Node(String name) { super(); this.name = name; } public String getName() { return name; } public List getChilds() { return childs; } public void setChilds(List childs) { this.childs = childs; } @Override public String toString() { return this.name; }} package com.demo2;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;import java.util.List;//测试类public class Test { public static void main(String[] args) { // 构造节点 Node a = new Node("A"); Node b = new Node("B"); Node c = new Node("C"); Node d = new Node("D"); Node e = new Node("E"); Node f = new Node("F"); Node g = new Node("G"); Node h = new Node("H"); Node i = new Node("I"); Node j = new Node("J"); Node k = new Node("K"); Node l = new Node("L"); // 构造树 a.setChilds(Arrays.asList(b, c, d)); b.setChilds(Arrays.asList(e, f)); d.setChilds(Arrays.asList(g, h, i)); f.setChilds(Arrays.asList(j, k)); h.setChilds(Arrays.asList(l)); // 创建栈 Deque que = new ArrayDeque (); que.push(a); // 前序遍历 System.out.println("前序遍历"); while (!que.isEmpty()) { Node nodeTemp = que.pop(); System.out.print(nodeTemp.getName()); List childs = nodeTemp.getChilds(); if (childs != null) { for (int iter = childs.size() - 1; iter >= 0; iter--) { que.push(childs.get(iter)); } } } }} 输出结果：
前序遍历ABEFJKCDGHLI
2.2.2 后序遍历：
后序遍历需要标识“节点是否已经将它的子节点入栈”。因此，在树节点类Node中添加了一个属性boolean mark，mark为true时，表示该节点已经将它的子节点入栈；false表示还没有将该节点的子节点入栈。
package com.demo3;import java.util.List;//树节点类public class Node { private String name; private List childs; private boolean mark; public Node(String name) { super(); this.name = name; this.mark = false; } public String getName() { return name; } public List getChilds() { return childs; } public void setChilds(List childs) { this.childs = childs; } public boolean isMark() { return mark; } public void setMark(boolean mark) { this.mark = mark; } @Override public String toString() { return this.name; }} package com.demo3;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;import java.util.List;//测试public class Test { public static void main(String[] args) { // 构造节点 Node a = new Node("A"); Node b = new Node("B"); Node c = new Node("C"); Node d = new Node("D"); Node e = new Node("E"); Node f = new Node("F"); Node g = new Node("G"); Node h = new Node("H"); Node i = new Node("I"); Node j = new Node("J"); Node k = new Node("K"); Node l = new Node("L"); // 构造树 a.setChilds(Arrays.asList(b, c, d)); b.setChilds(Arrays.asList(e, f)); d.setChilds(Arrays.asList(g, h, i)); f.setChilds(Arrays.asList(j, k)); h.setChilds(Arrays.asList(l)); // 创建栈 Deque que = new ArrayDeque (); que.push(a); // 后序遍历 System.out.println("后序遍历"); while (!que.isEmpty()) { Node nodeTemp = que.peek(); if (nodeTemp.isMark()) { Node node = que.pop(); System.out.print(node.getName()); } else { List childs = nodeTemp.getChilds(); if (childs != null) { for (int iter = childs.size() - 1; iter >= 0; iter--) { que.push(childs.get(iter)); } } nodeTemp.setMark(true); } } }} 输出结果：
后序遍历EJKFBCGLHIDA
2.2.3 二叉树的中序遍历
根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：
对于任一结点P，
1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束
二叉树
//二叉树节点类public class Node { private String name; private Node left; private Node right; public Node(String name) { super(); this.name = name; } public String getName() { return name; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } @Override public String toString() { return this.name; }} import java.util.ArrayDeque;import java.util.Deque;//测试public class Test { public static void main(String[] args) { // 构造节点 Node a = new Node("A"); Node b = new Node("B"); Node c = new Node("C"); Node d = new Node("D"); Node e = new Node("E"); Node f = new Node("F"); Node g = new Node("G"); Node h = new Node("H"); Node i = new Node("I"); Node j = new Node("J"); // 构造树 a.setLeft(b); a.setRight(c); b.setLeft(d); b.setRight(e); c.setLeft(f); c.setRight(g); e.setLeft(h); e.setRight(i); g.setLeft(j); // 创建栈 Deque que = new ArrayDeque (); Node currNode = a; // 中序遍历算法 System.out.println("中序遍历："); while (currNode != null || !que.isEmpty()) { while (currNode != null) { que.push(currNode); currNode = currNode.getLeft(); } currNode = que.pop(); System.out.print(currNode.getName()); currNode = currNode.getRight(); } }} 输出结果：
中序遍历：DBHEIAFCJG