1. 递归实现
先序
代码语言：javascript
复制public void preOrder(){
preOrder(root);
}
private void preOrder(Node node){
if(node != null){
System.out.println(node.value);
preOrder(node.left);
preOrder(node.right);
}
}
中序
代码语言：javascript
复制public void midOrder(){
midOrder(root);
}
private void midOrder(Node node){
if(node != null){
midOrder(node.left);
System.out.println(node.value);
midOrder(node.right);
}
}
后序
代码语言：javascript
复制public void postOrder(){
postOrder(root);
}
private void postOrder(Node node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
System.out.println(node.value);
}
}
2. 非递归
前序
代码语言：javascript
复制public void preOrderNew(){
preOrderNew(root);
}
private void preOrderNew(Node node){
if(node != null){
LinkedList<Node> list = new LinkedList();
list.addFirst(node);
while(!list.isEmpty()){
Node temp = (Node) list.removeFirst();
if(temp.right != null){
list.addFirst(temp.right);
}
if(temp.left != null){
list.addFirst(temp.left);
}
System.out.println(temp.value);
}
}
}
中序
代码语言：javascript
复制public void midOrderNew(){
midOrderNew(root);
}
private void midOrderNew(Node node){
LinkedList<Node> list = new LinkedList();
while(!list.isEmpty() || node != null){
if(node != null){
list.addFirst(node);
node = node.left;
}else{
node = list.removeFirst();
System.out.println(node.value);
node = node.right;
}
}
}
后序
代码语言：javascript
复制public void postOrderNew(){
postOrderNew(root);
}
private void postOrderNew(Node node){
if(node != null){
LinkedList<Node> list1 = new LinkedList();
LinkedList<Node> list2 = new LinkedList();
list1.addFirst(node);
while(!list1.isEmpty()){
Node temp = list1.removeFirst();
list2.addFirst(temp);
if(temp.left != null){
list1.addFirst(temp.left);
}
if(temp.right != null){
list1.addFirst(temp.right);
}
}
while(!list2.isEmpty()){
Node temp = list2.removeFirst();
System.out.println(temp.value);
}
}
}
