建立如图所示的树
Tree类的定义public class Tree {
private Object val;
private Tree father;
private Tree left;
private Tree right;
}
将树的节点作为测试类的元素，用代码块进行初始化
public class TreeTest {
linkedList
基于栈的中序遍历
@Test
public void inOderTraverse(){
//初始化栈
Stack treeStack = new Stack();
//将根节点作为第一个入栈的元素
Tree h=a;
while(h!=null||!treeStack.isEmpty()){
if(h!=null){
//如果当前访问的节点存在，则将其入栈，并访问他的左子树
treeStack.push(h);
h=h.getLeft();
}else{
//如果访问的节点不存在，就对栈进行出栈，访问出栈节点，然后访问出栈节点的右子树
Tree pop = treeStack.pop();
trees.add(pop.getVal());
h=pop.getRight();
}
System.out.println(trees);
}
System.out.println(trees);
}
基于队列的层序遍历
@Test
public void traverse(){
//初始化队列
Queue treeQueue =new linkedList();
Tree p=a;
treeQueue.add(p);
//根节点入队
while(!treeQueue.isEmpty()){
//出队，出队元素如果有子节点，就将子节点从左到右入栈，依次重复，直至队列为空
Tree poll = treeQueue.poll();
trees.add(poll.getVal());
if(poll.getLeft()!=null){
treeQueue.add(poll.getLeft());
}
if(poll.getRight()!=null){
treeQueue.add(poll.getRight());
}
}
System.out.println(trees);
}
