節(jié)點(diǎn)類
class Node {
public int value;
public Node left;
public Node right;
public Node(int data){
this.value=data;
}
}
測試實(shí)例
import java.util.Stack;
//樹的遍歷
public class Tree {
//遞歸先序遍歷
public static void preOrderRecur(Node head){
if(head==null){
return;
}
System.out.print(head.value+" ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
//遞歸中序遍歷
public static void inOrderRecur(Node head){
if(head==null){
return;
}
inOrderRecur(head.left);
System.out.print(head.value+" ");
inOrderRecur(head.right);
}
//非遞歸實(shí)現(xiàn)后序遍歷（兩個(gè)棧）
public static void posOrderUnrecur(Node head){
if(head!=null){
Stack<Node> s1=new Stack<Node>();
Stack<Node> s2=new Stack<Node>();
s1.push(head);
while(!s1.isEmpty()){
head=s1.pop();
s2.push(head);
if(head.left!=null){
s1.push(head.left);
}
if(head.right!=null){
s1.push(head.right);
}
}
while(!s2.isEmpty()){
System.out.print(s2.pop().value+" ");
}
}
System.out.println();
}
public static void main(String[] args) {
Tree tree = new Tree();
Node node1=new Node(1);
Node node2=new Node(2);
Node node3=new Node(3);
Node node4=new Node(4);
Node node5=new Node(5);
Node node6=new Node(6);
Node node7=new Node(7);
node1.left=node2;
node1.right=node3;
node2.left=node4;
node2.right=node5;
node3.left=node6;
node3.right=node7;
preOrderRecur(node1);
System.out.println();
inOrderRecur(node1);
System.out.println();
posOrderUnrecur(node1);
}
}
