1

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

所以我使用以下代码制作了一个 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 也会发生同样的事情。如果我之前不清楚，我的主要问题是删除一个数组元素，然后用它的子元素替换它。

4

2 回答 2

2

队列(FIFO)通常适用于 BFS。它不一定是优先级队列，但通常是因为赋予权重很常见：

队列通常但不一定以 FIFO（先进先出）方式对元素进行排序。例外情况包括优先级队列，它根据提供的比较器或元素的自然顺序对元素进行排序，以及对元素进行排序的 LIFO 队列（或堆栈） LIFO（后进先出）。无论使用何种排序，队列的头部都是将通过调用 remove() 或 poll() 删除的元素。在 FIFO 队列中，所有新元素都插入到队列的尾部。其他类型的队列可能使用不同的放置规则。每个 Queue 实现都必须指定其排序属性。

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

  1. 将初始状态放入Q（队列）
  2. 带头Q（见remove）
  3. 用所取的值做一些事情（例如parent -> [child1, child2 ..]）
  4. 将第 3 步的任何结果附加到Q（参见add）的尾部
  5. 返回步骤 #2 直到Q为空或达到其他最终情况

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

于 2012-12-25T01:59:19.350 回答
0

对于 DFS(FILO)，你只需要使用一个堆栈

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

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

于 2013-01-06T06:36:12.680 回答