JAVAは二叉木をフォント順に印刷

2111 ワード

ツリーの奇数行と偶数行をそれぞれ2つのスタックで格納し,奇数行は左から右へ子供を押し込み,偶数行は右から左へ子供を押し込む.
import java.util.LinkedList;
import java.util.Stack;

/**
 * Created by Administrator on 2018/3/7.
 */
public class zhiPrint {
    public void print(TreeNode root){
        if(root==null)
            return;
        Stack s1 = new Stack<>();//     
        Stack s2 = new Stack<>();//     
        s1.push(root);
        while(!s1.isEmpty() || !s2.isEmpty()){
            while (!s1.isEmpty()) {//         
                TreeNode node = s1.pop();
                System.out.print(node.element+" ");
                if (s1.isEmpty())//        
                    System.out.println();
                if (node.left != null)
                    s2.push(node.left);//  child  child       
                if (node.right != null)
                    s2.push(node.right);
            }
            while (!s2.isEmpty()) {//         
                TreeNode node = s2.pop();
                System.out.print(node.element+" ");
                if (s2.isEmpty())
                    System.out.println();
                if (node.right != null)
                    s1.push(node.right);//  child  child       
                if (node.left != null)
                    s1.push(node.left);
            }
        }
    }
    public static void main(String... args){
        LinkedList q = new LinkedList<>();//            ,   1 15
        int i = 1;
        TreeNode root = new TreeNode(i++);
        q.add(root);
        while (!q.isEmpty()&&i<=15){
            TreeNode lchild = new TreeNode(i++);
            TreeNode rchild = new TreeNode(i++);
            TreeNode node = q.poll();
            node.left = lchild;
            node.right = rchild;
            q.add(node.left);
            q.add(node.right);
        }
        //    
        new zhiPrint().print(root);
    }
}
class TreeNode {
    Object element;
    TreeNode left;
    TreeNode right;
    public TreeNode(int id){
        element = (Object)id;
    }
}