广度优先搜索

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 )的方式对元素进行排序。其中的例外是优先级队列，它根据提供的比较器或元素的自然排序对元素进行排序，以及LIFO队列(或堆栈)，它对元素进行后进先出( LIFO )排序。无论使用哪种排序，队列的头部都是可以通过调用remove()或poll()删除的元素。在FIFO队列中，所有新元素都插入到队列的尾部。其他类型的队列可以使用不同的放置规则。每个队列实现都必须指定其排序属性。

带队列的BFS的基本算法规则：

将初始状态放入队列中(队列)，并获取队列的头部(参见remove)

• Do parent -> [child1, child2 ..])

• Append Q

• Q Q (例如，将步骤#3中的任何结果返回到队列的尾部))(参见

1. to step #2，直到Q为空或达到其他结束情况

<Q>G221Q>

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

Answer 2

对于DFS(FILO)，您只需要使用堆栈

对于每个节点，首先将其右子节点压入堆栈，然后再压入左子节点

对于BFS(FIFO)，您应该使用前面提到的@pst队列