四、程序

package 剑指offer;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

class BinaryTreeNodeZhi{
int value;
BinaryTreeNodeZhi left;
BinaryTreeNodeZhi right;

BinaryTreeNodeZhi(int value){
this.value = value;
}

public String toString(){
return value+"  ";
}
}

public class Test61 {

// 进行之字输出的第一种方式
public static void printByLineZhi1(BinaryTreeNodeZhi head){
if(head == null){
System.out.println("Error");
}

// 首先建立两个链表，链表的结点是二叉树的结点
List<BinaryTreeNodeZhi> current = new LinkedList<BinaryTreeNodeZhi>();
List<BinaryTreeNodeZhi> reverse = new LinkedList<BinaryTreeNodeZhi>();

current.add(head);
BinaryTreeNodeZhi node;
int flag = 0;

while(current.size() > 0){
// 从后往前打印
node = current.remove(current.size() - 1);
System.out.print(node);

if(flag == 0)
{
// 从左往右添加元素到reverse中
if(node.left != null){
reverse.add(node.left);
}

if(node.right != null){
reverse.add(node.right);
}
}else if(flag == 1){
// 从右往左添加元素到reverse中
if(node.right != null){
reverse.add(node.right);
}

if(node.left != null){
reverse.add(node.left);
}
}

// 转变flag也就是转变添加元素的顺序，将reverse中的元素变到current中进行打印了
            if (current.size() == 0) {
                flag = 1 - flag;
                List<BinaryTreeNodeZhi> tmp = current;
                current = reverse;
                reverse = tmp;
                System.out.println();
            }
}
}

// 第二中方式进行"之"字形式的，二叉树的打印
public static void printByLineZhi2(BinaryTreeNodeZhi head){
if(head == null){
System.out.println("Error");
}

int current = 1;
int next = 0;
// 使用队列的方式，先入先出
Queue<BinaryTreeNodeZhi> queue = new LinkedList<BinaryTreeNodeZhi>();
BinaryTreeNodeZhi node;
queue.offer(head);

Stack<BinaryTreeNodeZhi> stack = new Stack<BinaryTreeNodeZhi>();

int flag = 0;

while(queue.size() > 0){
//这用当弹出current个数的时候才会输出下一轮
node = queue.poll();
current--;
// 当flag为零的时候，表明这一行是正向的顺序，所以可以直接进行打印
if(flag == 0)
System.out.print(node);
// 当flag为1的时候，表明这一行是反向的顺序，将其存入栈中，在下面进行打印
if(flag == 1){
stack.push(node);
}


// 分别将当前结点的左右孩子入队列，并标明这是下一行要打印的结点
if(node.left != null){
queue.offer(node.left);
next++;
}

if(node.right != null){
queue.offer(node.right);
next++;
}
// 标明此时这行的结点打印完了，要换到下一行了
            if (current ==0) {
                
                current = next;
                next = 0;
                //将存入栈的的元素进行打印
                while(!stack.isEmpty()){
                System.out.print(stack.pop());
                }               
                System.out.println();
                // 转变标志位
                flag = 1 - flag;
            }
}
}


    private static void assembleZhi(BinaryTreeNodeZhi n1,
    BinaryTreeNodeZhi n2,
    BinaryTreeNodeZhi n3) {
    n1.left = n2;
    n1.right = n3;
    }

public static void main(String args[]){
BinaryTreeNodeZhi n1 = new BinaryTreeNodeZhi(1);
BinaryTreeNodeZhi n2 = new BinaryTreeNodeZhi(2);
BinaryTreeNodeZhi n3 = new BinaryTreeNodeZhi(3);
BinaryTreeNodeZhi n4 = new BinaryTreeNodeZhi(4);
BinaryTreeNodeZhi n5 = new BinaryTreeNodeZhi(5);
BinaryTreeNodeZhi n6 = new BinaryTreeNodeZhi(6);
BinaryTreeNodeZhi n7 = new BinaryTreeNodeZhi(7);

assembleZhi(n1, n2, n3);
assembleZhi(n2, n4, n5);
assembleZhi(n3, n6, n7);

printByLineZhi1(n1);
System.out.println("===================");
printByLineZhi2(n1);
}

}

1  
3  2  
4  5  6  7  
===================
1  
3  2  
4  5  6  7