import java.util.Stack;
/**
* Created by ***** on 2017/8/21.
*/
public class BinaryTreeSeek {
public static void main(String[] agrs){
BinarySortTree b = new BinarySortTree();
b.val = 5;
b.left_child = new BinarySortTree();
b.right_child = new BinarySortTree();
b.left_child.val = 3;
b.right_child.val = 7;
b.left_child.left_child = new BinarySortTree();
b.left_child.right_child = new BinarySortTree();
b.left_child.left_child.val = 2;
b.left_child.right_child.val = 4;
b.right_child.left_child = new BinarySortTree();
b.right_child.right_child = new BinarySortTree();
b.right_child.left_child.val = 6;
b.right_child.right_child.val = 8;
// PreOrder(b);
// System.out.println();
// PreOrder2(b);
// System.out.println();
// InOrder(b);
// System.out.println();
// InOrder2(b);
// System.out.println();
// PostOrder(b);
// System.out.println();
PostOrder2(b);
}
/**
* 二叉树递归前序遍历
* @param tree
*/
public static void PreOrder(BinarySortTree tree){
if (tree != null){
System.out.print(tree.val+" ");
PreOrder(tree.left_child);
PreOrder(tree.right_child);
}else {
return;
}
}
/**
* 二叉树前序遍历
* @param tree
*/
public static void PreOrder2(BinarySortTree tree){
Stack<BinarySortTree> stack = new Stack<>();
while(tree != null || !stack.empty()){
if (tree != null){
stack.push(tree);
System.out.print(tree.val+" ");
tree = tree.left_child;
}else {
tree = stack.pop();
tree = tree.right_child;
}
}
}
/**
* 二叉树递归中序遍历
* @param tree
*/
public static void InOrder(BinarySortTree tree){
if (tree != null){
InOrder(tree.left_child);
System.out.print(tree.val+" ");
InOrder(tree.right_child);
}else {
return;
}
}
/**
* 二叉树中序遍历
* @param tree
*/
public static void InOrder2(BinarySortTree tree){
Stack<BinarySortTree> stack = new Stack<>();
while(tree != null || !stack.empty()){
if (tree != null){
stack.push(tree);
tree = tree.left_child;
}else {
tree = stack.pop();
System.out.print(tree.val+" ");
tree = tree.right_child;
}
}
}
/**
* 二叉树递归后序遍历
* @param tree
*/
public static void PostOrder(BinarySortTree tree){
if (tree != null){
PostOrder(tree.left_child);
PostOrder(tree.right_child);
System.out.print(tree.val+" ");
}else {
return;
}
}
/**
* 二叉树后序遍历 需要记录上一次弹出的节点
* @param tree
*/
public static void PostOrder2(BinarySortTree tree){
Stack<BinarySortTree> stack = new Stack<>();
BinarySortTree lastview = null;
while(tree != null || !stack.empty()){
if (tree != null){
stack.push(tree);
tree = tree.left_child;
}else {
tree = stack.pop();
if (tree.right_child == null || tree.right_child == lastview){
//如果无右节点或者该节点的右节点已经访问过
System.out.print(tree.val+" ");
lastview = tree;
tree = null;
}else {
stack.push(tree);//重新入栈有右孩子的改节点
tree = tree.right_child;
}
}
}
}
}
