全屏閱讀 【版面名稱】：Prolog【版主】：徵求中【討論區】：電腦技術第1頁/共1頁(總計1筆) 


      打包

      發信人:   wave(馳浪)
      題  目:   二叉樹的遍歷與搜索
      發信站: 【蜘蛛網虛擬社區】  (發表於 2001-05-17 14:39:55)
        

      二叉樹（binary tree）是一類特殊的結構，而且非常有用，那么在Prolog里面怎樣表示于操作二叉樹呢？

      Prolog中可以定義復合類型，于是，可以這樣定義樹上的節點
      domains
        value = symbol
        node = node(value,node,node)

      有了這個定義后，一棵樹如：
                            a
                           /  \                   
                          b     c
      可以表示為
      node(a,node(b,null,null),node(c,null,null))

      我們發現需要一個特殊的值表示空節點null
      可以定義一個常量
      constants
        null = node(nil,_,_)

      現在，已經可以表示任意的二叉樹了

      在定義幾個域
      domains
        enumerator = value*
        nodelist = node*

      定義幾個謂詞
        isnull(node) %用來判定一個節點是否為空節點
        splitnode(node,value,node,node) %用來析出某節點的各個域
      如：splitnode(node(a,node(b,null,null),null),VALUE,LEFT,RIGHT)的結果是
      VALUE = a,LEFT = node(b,null,null),RIGHT = null

        append(enumerator,enumerator,enumerator) % 用來連接兩個表
        append([],H,H).
        append(H,[],H).
        append([X|H],T,[X|R]:-
           append(H,T,R).

        
        aqqend(nodelist,nodelist,nodelist) % 用來連接兩個節點表，類似于append
        append([],H,H).
        append(H,[],H).
        append([N|H],T,[N|R]):-
          append(H,T,R).


      二叉樹的遍歷
      1.前序遍歷  a -＞ b -＞ c
        preorder(node,enumerator) %將以前序遍歷以node的為節點的樹，并將結果依次置入表中，于是
        preorder(null,[]):-!.  % 空表的處理
        preorder(node(VALUE,LEFT,RIGHT),E):-
          preorder(LEFT,EL),
          preorder(RIGHT,ER),
          append([E|EL],ER,E).

      現在就可以對樹進行前序遍歷了
       

      2。中序遍歷  b -＞ a -＞ c
        inorder(node,enumerator) % 將以中序遍歷以node的為節點的樹，并將結果依次置入表中，于是
        inorder(null,[]):-!.
        inorder(node(VALUE,LEFT,RIGHT)):-
          inorder(LEFT,EL),
          inorder(RIGHT,ER),
          append(EL,[VALUE|ER],E).


      3.后續遍歷  b -＞ c -＞ a
        postorder(node,enumerator) %將以后序遍歷以node的為節點的樹，并將結果依次置入表中，于是
        postorder(null,[]).
        postorder(node(VALUE,LEFT,RIGHT),E):-
          postorder(LEFT,EL),
          postorder(RIGHT,ER),
          append(EL,ER,EE),
          append(EE,[VALUE],E).


      樹的搜索
      1.深度優先搜索策略
         設謂詞deepsearch(value V,node Tree,node 
      Node)是在以Tree為根的樹種查找值為V的節點，返回值為Node，則：
        deepsearch(V,NODE,NODE):-  % 剛好查找到的情況
          not(isnull(NODE)),
          splitnode(NODE,VALUE,_,_),
          V = VALUE.

        deepsearch(V,NODE,N):-   % 向左子樹查找的情況
          not(isnull(NODE)),
          splitnode(NODE,VALUE,LEFT,_),
          deepsearch(V,LEFT,N).

        deepsearch(V,NODE,N):-   % 向右子樹查找的情況
          not(isnull(NODE)),
          splitnode(NODE,VALUE,_,RIGHT),
          deepsearch(V,RIGHT,N).

      以上規則就可以深度搜索二叉樹了

      2。廣度優先搜索策略
        謂詞widesearch(value V,node Tree,node Node)完成廣度搜索
        搜索的時候用到了一個隊列存放待搜索的節點序列，這是通過謂詞wide完成的。
      　wide(value V,nodelist Nodes,nodelist NewNodes,node Node)
        則：
        widesearch(V,ROOT,N):-
          wide(V,[ROOT],_,N).

        wide(V,[NODE|E],NE,NODE):-  % 剛好找到的情況
          not(isnull(NODE)),
          splitnode(NODE,VALUE,_,_),
          V = VALUE.

        wide(V,[NODE|E],NE,N):-
          not(isnull(NODE)),
          splitnode(NODE,VALUE,LEFT,RIGHT),
          aqqend(E,[LEFT],EL),  % 節點入隊列
          aqqend(EL,[RIGHT],ER),　% 節點入隊列
          delnull(ER,EE),　　% 刪除所有空節點
          wide(V,EE,NE,N).

        其中，delnull(nodelist,nodelist)實現如下：

        delnull([],[]):-!.
        delnull([null|E],R):-
          delnull(E,R).
        delnull([NODE|E],[NODE|R]):-
          delnull(E,R).

      以上完成廣度優先搜索！
        
      -------------- 
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      ~~ ~一切都將歸于滾滾的波濤~~ ~
      ~ ~~一切都將投向海洋的懷抱 ~~~
      ~~~ 就像那川流不止的歲月 ~~ ~~
      ~~ ~翻涌的海洋永遠奔騰咆哮~~~~
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
      ※來源: 【蜘蛛網虛擬社區】.    


      【版面名稱】：Prolog【版主】：徵求中【討論區】：電腦技術第1頁/共1頁(總計1筆) 

  



◎ 蜘蛛網虛擬社區 ◎ club.MagicPower.com  Magic Power Software Studio.©版權所有 
Programming by MagicPower Software Studio.2000
管理員 mudu