java - 广度优先搜索

Question

我只是有一个简单的实现查询。

所以我使用以下代码制作了 BST:

class Node{

    int data;
    Node left=null;
    Node right=null;
    Node link=null;

    public Node(int d)
    {
        data=d;
    }

    public void append(int d)
    {
        Node n=this;
        Node nval=new Node(d);
        if(n==null)
        {
            n.data=d;
        }
        else
        {   boolean done=false;
            while(!done)
            {
                 if(n.data<=d)
                 {
                     if(n.left==null)
                     {
                         n.left=nval;
                         done=true;
                     System.out.println("Data Entered "+nval.data);
                     }
                     else
                     {
                         n=n.left;
                     }
                 }
                 else
                 if(n.data>d)
                 {
                     if(n.right==null)
                     {
                         n.right=nval;
                         done=true;
                     System.out.println("Data Entered "+nval.data);
                     }
                     else
                     {
                         n=n.right;
                     }
                 }
            }
        }
    }
}

现在，我开始对其应用广度优先和深度优先搜索。我在做这件事时遇到了真正的问题。

对于DFS，我必须添加放置在堆栈上的当前节点的左右值，对吗？我该如何编程呢？我在使用链接列表执行此操作时遇到问题？有人可以告诉我数据结构或指针应该是什么样的吗？

BFS 也会发生同样的情况。如果我之前不清楚，我的主要问题是删除一个数组元素，然后用它的子元素替换它。

Answer 1

一个Queue (FIFO) 通常对于 BFS 来说效果很好。它不一定是优先级队列，但通常是因为赋予权重很常见:

Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering, and LIFO queues (or stacks) which order the elements LIFO (last-in-first-out). Whatever the ordering used, the head of the queue is that element which would be removed by a call to remove() or poll(). In a FIFO queue, all new elements are inserted at the tail of the queue. Other kinds of queues may use different placement rules. Every Queue implementation must specify its ordering properties.

带有队列的 BFS 的基本“算法”规则:

1. 将初始状态放入Q(队列)
2. 取出Q的头部(参见删除)
3. 使用获取的值执行某些操作(例如 parent -> [child1, child2 ..])
4. 将步骤 #3 中的任何结果附加到 Q 的尾部(请参阅add)
5. 返回步骤 #2，直到 Q 为空或实现其他最终情况

数组只是一个处理过去初始化和迭代的 PITA。在 Java 中，“切片”和“调整大小”往往特别痛苦。