importjava.util.LinkedList;public classPrintZigzag {private classBinaryNode{intele;
BinaryNode left;
BinaryNode right;public BinaryNode(intele) {this.ele =ele;
left= right = null;
}
@OverridepublicString toString() {return ele + " ";
}
}privateBinaryNode root;//根據數組 arr 中的元素構造一棵二叉排序樹
public void buildTree(int[] arr){for (intnode : arr) {
insert(node);
}
}private void insert(intele){
root=insert(root, ele);
}private BinaryNode insert(BinaryNode root, intele){//遞歸的結束條件.base condition
if(root == null)return newBinaryNode(ele);if(root.ele >ele)
root.left=insert(root.left, ele);else if(root.ele
root.right=insert(root.right, ele);elseroot.left=insert(root.left, ele);return root;//若某結點的左右孩子不空,在後續的遞歸調用中該結點的左右指針是不會變的.
}public voidzigPrintTree(){if(root == null)return;
LinkedList stack = new LinkedList<>();//列印目前行的棧(隻儲存奇數行的結點)
LinkedList nextStack = new LinkedList<>();//列印下一行的棧(隻儲存偶數行的結點)
int lineNumber = 1;//标記行号(根為第一行)
stack.push(root);//根屬于奇數行的結點(第一行)
while(!stack.isEmpty() || !nextStack.isEmpty())
{if(lineNumber % 2 == 1)//奇數行,左孩子先入棧
{while(!stack.isEmpty())
{
BinaryNode current=stack.pop();
System.out.print(current);//列印目前結點
if(current.left != null)
nextStack.push(current.left);//先左孩子入棧
if(current.right != null)
nextStack.push(current.right);//再右孩子入棧
}
System.out.println();//該層結點已經列印完,輸出換行符
}else{//偶數行,右孩子先入棧
while(!nextStack.isEmpty())
{
BinaryNode current=nextStack.pop();
System.out.print(current);if(current.right != null)//先右孩子入棧
stack.push(current.right);if(current.left != null)//再左孩子入棧
stack.push(current.left);
}
System.out.println();
}
lineNumber++;
}
}//hapjin test
public static voidmain(String[] args) {int[] eles = {20,10,30,5,12,25,40};//int[] eles = {20,10,30,12,25};
PrintZigzag pz = newPrintZigzag();
pz.buildTree(eles);
pz.zigPrintTree();
}
}