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;
}
}