而叉数.txt

Prolog开发的简单的几个人工智能方面的程序.含问题分析报告.

全屏阅读 【版面名称】：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