10.10树的遍历

 

 

 

import java.util.LinkedList;
import java.util.Stack;
public class trees<T> {
private T data;
public trees<T> left;
public trees<T> right;

public trees(T data) {
this.data = data;
this.left = null;
this.right = null;
}

public trees(T data, trees<T> left, trees<T> right) {
this.data = data;
this.left = left;
this.right = right;
}

public void preOrder(trees<T> t) {//递归前序
if (t != null) {
System.out.print(t.data+" ");
preOrder(t.left);
preOrder(t.right);
}
}

public void preOrderandmidOrder(trees<T> t) {//非递归前序和后序
trees<T> current = t;
LinkedList<T> pre = new LinkedList<>();
LinkedList<T> mid = new LinkedList<>();
Stack<trees> S = new Stack<>();
while (current != null || !S.isEmpty()) {
if (current != null) {
S.push(current);
pre.add(current.data);
current = current.left;
} else {
trees<T> pop=S.pop();
mid.add(pop.data);
current = pop.right;

}
}
System.out.println();
System.out.println("前序");
for(T pre1:pre)
{
System.out.print(pre1+" ");
}
System.out.println();
System.out.println("中序");
mid.forEach(data-> System.out.printf(data+" "));
}

public void midOrder(trees<T> t) {//递归中序
if (t != null) {
midOrder(t.left);
System.out.print(t.data+" ");
midOrder(t.right);
}
}

public void lastOrder(trees<T> t) {//递归后序
if (t != null) {
lastOrder(t.left);
lastOrder(t.right);
System.out.print(t.data+" ");
}
}
}