树的后序遍历

Posted on Edited on In

definition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static class BinaryNode<AnyType>
{
    BinaryNode(AnyType theElement)
    {
        this(theElement, null, null);
    }

    BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt)
    {
        element = theElement;
        left = lt;
        right = rt;
    }

    AnyType element;
    BinaryNode<AnyType> left;
    BinaryNode<AnyType> right;
}

private BinaryNode<AnyType> root;

posOrder

1
2
3
4
5
6
7
8
9
public void posOrder(BinaryNode<AnyType> Node)
    {
        if (Node != null)
        {
            posOrder(Node.left);
            posOrder(Node.right);
            System.out.print(Node.element + " ");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public void posOrder(BinaryNode<AnyType> Node)
{
    Stack<BinaryNode> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    int i = 1;
    while(Node != null || !stack1.empty())
    {
        while (Node != null)
        {
            stack1.push(Node);
            stack2.push(0);
            Node = Node.left;
        }

        while(!stack1.empty() && stack2.peek() == i)
        {
            stack2.pop();
            System.out.print(stack1.pop().element + "   ");
        }

        if(!stack1.empty())
        {
            stack2.pop();
            stack2.push(1);
            Node = stack1.peek();
            Node = Node.right;
        }
    }
}