package chap10;

import static org.junit.Assert.*;

import java.util.Stack;

import org.junit.Test;

public class exec10_4_4 {
    /**
     * 将该树打印
     * 
     * @param tree
     */
    static void printTree(TreeWithRoot tree) {
        printNode(tree.root.node);
    }

    /**
     * 遍历一个树的非递归方法，用一个栈实现
     * 
     * @param node
     */
    static void printNode(Node1 node) {
        if (node == null) {
            System.err.println("tree is null");
        }
        Stack<Node1> nodes = new Stack<Node1>();

        do {
            System.out.print(node.key + " ");
            if (node.right_sibling != null) {
                nodes.push(node.right_sibling);
            }
            if (node.left != null) {
                node = node.left;
            } else {
                node = nodes.pop();
            }
        } while (nodes != null);
    }

    /**
     * 创建一个树，弱智方法
     * 
     * @return
     */
    static TreeWithRoot creatTree() {
        TreeWithRoot t = new TreeWithRoot();
        Root1 r = new Root1();
        Node1 n1, n2, n3, n4, n5, n6, n7, n8, n9, n0;
        n1 = new Node1(0);
        n2 = new Node1(1);
        n3 = new Node1(2);
        n4 = new Node1(3);
        n5 = new Node1(4);
        n6 = new Node1(5);
        n7 = new Node1(6);
        n8 = new Node1(7);
        n9 = new Node1(8);
        n0 = new Node1(9);

        t.root = r;
        r.node = n0;
        n0.left = n1;
        n1.right_sibling = n2;
        n2.left = n3;
        n3.right_sibling = n4;
        n3.left = n5;
        n5.left = n6;
        n6.right_sibling = n7;
        n7.right_sibling = n8;
        n7.left = n9;
        return t;
    }

    @Test
    public void testName() throws Exception {
        TreeWithRoot t1 = creatTree();
        printTree(t1);

    }
}