二叉树的非递归遍历总结
public class BinaryTree{
public void preOrder(Node root){
if(root == null)
return;
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node cur = stack.pop();
System.out.println(cur.Value);
if(cur.rightChild != null)
stack.push(cur.rightChild);
if(cur.leftChild != null)
stack.push(cur.leftChild);
}
}
public void midOrder(Node root){
if(root == null)
return;
Stack<Node> stack = new Stack<>();
Node myRoot = root;
while(!stack.isEmpty() || myRoot != null){
if(myRoot != null){
stack.push(myRoot);
myRoot = myRoot.leftChild;
}else{
myRoot = stack.pop();
System.out.println(myRoot.value);
myRoot = myRoot.rightChild;
}
}
}
public void posOrder(Node root){
if(root == null)
return;
Stack<Node> stackOne = new Stack<>();
Stack<Node> stackTwo = new Stack<>();
stackOne.push(root);
while(!stackOne.isEmpty()){
Node cur = stackOne.pop();
stackTwo.push(cur);
if(cur.leftChild != null)
stackOne.push(cur.leftChild);
if(cur.rightChild != null)
stackOne.push(cur.rightChild);
}
while(!stackTwo.isEmpty()){
Node cur = stackTwo.pop();
System.out.println(cur.value);
}
}
public void posOrder2(Node root){
if(root == null)
return;
Stack<Node> stack = new Stack<>();
Node curNode = root;
Node lastNode = null;
while(curNode != null){
stack.push(curNode);
curNode = curNode.leftChild;
}
while(!stack.isEmpty()){
curNode = stack.pop();
if(curNode.rightChild != null && curNode.rightChild != lastNode){
stack.push(curNode);
curNode = curNode.rightChild;
while(curNode != null){
stack.push(curNode);
curNode = curNode.leftChild;
}
}else{
System.out.println(curNode.value);
lastNode = curNode;
}
}
}
}
class Node{
public int value;
public Node leftChild;
public Node rightChild;
public Node(int value){
this(value, null, null);
}
public Node(int value, Node leftChild, Node rightChild){
this.value = value;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
}