久久久久久久视色,久久电影免费精品,中文亚洲欧美乱码在线观看,在线免费播放AV片

<center id="vfaef"><input id="vfaef"><table id="vfaef"></table></input></center>

    <p id="vfaef"><kbd id="vfaef"></kbd></p>

    
    
    <pre id="vfaef"><u id="vfaef"></u></pre>

      <thead id="vfaef"><input id="vfaef"></input></thead>

    1. 站長資訊網(wǎng)
      最全最豐富的資訊網(wǎng)站

      廣度優(yōu)先遍歷類似于二叉樹的什么遍歷?

      廣度優(yōu)先遍歷類似于二叉樹的層次遍歷。廣度優(yōu)先搜索是從根結(jié)點開始沿著樹的寬度搜索遍歷,也就是按層次的去遍歷;從上往下對每一層依次訪問,在每一層中,從左往右(也可以從右往左)訪問結(jié)點,訪問完一層就進入下一層,直到?jīng)]有結(jié)點可以訪問為止。

      廣度優(yōu)先遍歷類似于二叉樹的什么遍歷?

      廣度優(yōu)先搜索(Breadth First Search)(其實是二叉樹的層次遍歷),又叫寬度優(yōu)先搜索或橫向優(yōu)先搜索,是從根結(jié)點開始沿著樹的寬度搜索遍歷。

      從上往下對每一層依次訪問,在每一層中,從左往右(也可以從右往左)訪問結(jié)點,訪問完一層就進入下一層,直到?jīng)]有結(jié)點可以訪問為止。

      廣度優(yōu)先遍歷類似于二叉樹的什么遍歷?

      上面二叉樹的遍歷順序為:ABCDEFG. 可以利用隊列實現(xiàn)廣度優(yōu)先搜索。

      廣度優(yōu)先搜索算法:

      保留全部結(jié)點,占用空間大; 無回溯操作(即無入棧、出棧操作),運行速度快。

      廣度優(yōu)先搜索算法,一般需存儲產(chǎn)生的所有結(jié)點,占用的存儲空間要比深度優(yōu)先搜索大得多,因此,程序設(shè)計中,必須考慮溢出和節(jié)省內(nèi)存空間的問題。但廣度優(yōu)先搜索法一般無回溯操作,即入棧和出棧的操作,所以運行速度比深度優(yōu)先搜索要快些。

      示例:

      廣度優(yōu)先遍歷類似于二叉樹的什么遍歷?

      其過程檢驗來說是對每一層節(jié)點依次訪問,訪問完一層進入下一層,而且每個節(jié)點只能訪問一次。對于上面的例子來說,廣度優(yōu)先遍歷的 結(jié)果是:A,B,C,D,E,F,G,H,I(假設(shè)每層節(jié)點從左到右訪問)。

      廣度優(yōu)先遍歷各個節(jié)點,需要使用到隊列(Queue)這種數(shù)據(jù)結(jié)構(gòu),queue的特點是先進先出,其實也可以使用雙端隊列,區(qū)別就是雙端隊列首位都可以插入和彈出節(jié)點。整個遍歷過程如下:

      首先將A節(jié)點插入隊列中,queue(A);

      將A節(jié)點彈出,同時將A的子節(jié)點B,C插入隊列中,此時B在隊列首,C在隊列尾部,queue(B,C);

      將B節(jié)點彈出,同時將B的子節(jié)點D,E插入隊列中,此時C在隊列首,E在隊列尾部,queue(C,D,E);

      將C節(jié)點彈出,同時將C的子節(jié)點F,G,H插入隊列中,此時D在隊列首,H在隊列尾部,queue(D,E,F(xiàn),G,H);

      將D節(jié)點彈出,D沒有子節(jié)點,此時E在隊列首,H在隊列尾部,queue(E,F(xiàn),G,H);

      …依次往下,最終遍歷完成

      Java代碼大概如下:

      public class TreeNode {     int val = 0;     TreeNode left = null;     TreeNode right = null;      public TreeNode(int val) {         this.val = val;     } } public class Solution {     public ArrayList<Integer> wide(TreeNode root) {         ArrayList<Integer> lists=new ArrayList<Integer>();         if(root==null)             return lists;         Queue<TreeNode> queue=new LinkedList<TreeNode>();         queue.offer(root);         while(!queue.isEmpty()){             TreeNode node = queue.poll();             if(node.left!=null){                 queue.offer(node.left);             }             if(node.right!=null){                 queue.offer(node.right);             }             lists.add(node.val); 		}         return lists;     } }

      贊(0)
      分享到: 更多 (0)
      網(wǎng)站地圖   滬ICP備18035694號-2    滬公網(wǎng)安備31011702889846號