廣度優先搜索

我只是有一個簡單的實現查詢。廣度優先搜索

所以我做一個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發生同樣的事情。如果我以前不清楚，我的主要問題是刪除一個數組元素，然後將其替換爲它的子元素。

來源

2012-12-25 gran_profaci

'if（n == null）{n.data = d; }'你是否試圖得到'NullPointerException'或是這是一個錯字？ – ApproachingDarknessFish

@ValekHalfHeart - 不用擔心，在賦值'Node n = this之前有一對行，所以n永遠不能爲null。 –

是的，我剛剛得到了！謝謝！ –

A Queue（先進先出）通常適用於BFS。它不一定是一個優先級隊列，但它往往是因爲給予的權重是很常見的：

隊列一般，但不一定，在FIFO（先入先出）的方式順序的元素。其中的例外是優先級隊列，它根據提供的比較器對元素進行排序，或者元素的自然順序，以及對元素LIFO（後進先出）進行排序的LIFO隊列（或堆棧）。無論使用何種排序，隊列的頭部都是通過調用remove（）或poll（）來移除的元素。在FIFO隊列中，所有新元素都插入隊列尾部。其他種類的隊列可能會使用不同的放置規則。每個隊列實現都必須指定其排序屬性。

基本「算法」的BFS與隊列規則：

將初始狀態（S）在Q（隊列）
就拿Q的頭部（見remove）
用值取值（例如parent -> [child1, child2 ..]）
將步驟＃3的任何結果附加到Q的尾部（請參閱add ）
回到步驟＃2，直到Q是空的或其他終端的情況下，實現

陣列只是PITA對付過去的初始化和迭代。在Java中，「切片」和「調整大小」往往特別痛苦。

來源

2012-12-25 01:59:19

的DFS（FILO），U只需要使用堆棧

每個節點，推他的右子堆棧第一，然後按下左子

的BFS（FIFO），U應該使用隊列作爲@pst提到

來源

2013-01-06 06:36:12 songlj

廣度優先搜索

回答

相關問題