2

二分木をレベル順または幅優先順でトラバースしながらレベルを追跡するにはどうすればよいですか?

バイナリ ツリーのノードには、左右の参照のみがあります。

ノードの各行を区別できるようにしたい。

レベル順トラバーサルの方法は次のとおりです。

private static Queue<Node> traverseLevelOrder(final Node node)
{
    final Queue<Node> temporaryQueue = new LinkedList<Node>(); // Temporary queue is used for traversal.
    final Queue<Node> permanentQueue = new LinkedList<Node>(); // Permanent queue is used for node storage.

    // Add the root node, as current, to the queue.
    Node current = node;
    temporaryQueue.add(current);
    permanentQueue.add(current);

    while (!temporaryQueue.isEmpty())
    {
        current = temporaryQueue.remove();
        System.out.println(String.valueOf(current));

        // Check current's children.
        if (current != null)
        {
            final Node left = current.getLeft();
            final Node right = current.getRight();

            current = left;
            if (current != null)
            {
                temporaryQueue.add(current);
                permanentQueue.add(current);
            }

            current = right;
            if (current != null)
            {
                temporaryQueue.add(current);
                permanentQueue.add(current);
            }
        }
    }

    return permanentQueue;
}
4

4 に答える 4

3 
public void bfs(Node root) {
    Queue<Node> q = new LinkedList<Node>();
    Node dummy = new Node(null);

    q.add(root);
    q.add(dummy);

    while(!q.isEmpty()) {
        Node curr = q.poll();

        if(curr != null) {
            System.out.print(curr.data + " ");

            if(curr.left != null)
                q.insert(curr.left);
            if(curr.right !== null)
                q.insert(curr.right);
        } else {
            System.out.println();
            if(!q.isEmpty())
                q.insert(dummy);
        }
    }
}

nullこのコードは中間ノードを示していません。

于 2011-12-05T14:51:18.903 に答える