社区 › AutoLISP/Visual LISP 编程技术 › 二叉树的autolisp实现，算法

freedom_ice 发表于 2022-10-28 10:33:20

二叉树的autolisp实现，算法

本帖最后由 freedom_ice 于 2022-10-28 10:39 编辑

学习数据结构，找不到autolisp版本的，摸索到common lisp，结合C语言的数据结构，实现了满二叉树及遍历。
但是目前没想到有什么应用场景。
抛砖引玉，供大家交流讨论。
知乎用户 SSSS 岩土设计


( defun c:xx()
( setq aaa '( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ) )         ;;满二叉树
( setq bbb '( 2 13 55 46 37 8 19 10 15 12 113 14 22 23 25 ) );;满二叉树
( setq bbb '( 2 13 55 46 37 8 19 10 15 12 113 14) )          ;;不是满二叉树
;( setq aaa '( 0 1 2 3 4 5 6 ) )
( setq abc ( BinaryTree 0 aaa ) )
( princ abc )
;( istree abc )
;( setq abc ( BinaryTree 0 bbb ) )
;( PreOrder abc )   ;先序遍历
;( Inorder abc )    ;中序遍历
( Postorder abc );后序遍历
)

;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名: BinaryTree ********************************************************
;;;说明: 仅适用于顺序存储转满二叉树的形式***********************************
;;;功能: 顺序存储转二叉树***************************************************
;;;参数: i 二叉树深度*******************************************************
;;;参数: datalist 顺序存储表************************************************
;;;返回值: 二叉树格式*********************************************************
;;;例子: ( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 )顺序表***********************
;;;输出: (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14))) 输出二叉树格式****
( defun BinaryTree ( i datalist / left mid n right )
( setq mid nil )
( setq left nil )
( setq right nil )
( setq n ( length datalist ) )
(cond ( ( <= i ( - ( / ( - n 1 ) 2 ) 1 ) )
         ( progn         
            ( setq mid ( nth i datalist )   
                            left ( BinaryTree ( + ( * 2 i ) 1 ) datalist )
                           right ( BinaryTree ( + ( * 2 i ) 2 ) datalist )
                     )
             ( list mid left right )
         )         
                   )
         ( ( and ( > i ( - ( / ( - n 1 ) 2 ) 1 ) )
               ( < i n ) )
         ( setq mid ( nth i datalist ) )            
         )
         ( t nil )
)
)
;;;*****************************************************************************
;;;*****************************************************************************


;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名: istree ************************************************************
;;;说明: 判断表数据是否符合满二叉树的格式***********************************
;;;参数: i 二叉树深度*******************************************************
;;;参数: datalist 顺序存储表************************************************
;;;返回值: 二叉树格式*********************************************************
;;;例子: (istree (a (b nil nil) nil)) 二叉树格式****************************
;;;输出: T 输出真值*********************************************************
;;;例子: (istree (a (b nil nil))) 非二叉树格式******************************
;;;输出: NIL 输出假值*******************************************************
( defun istree ( treelist / left right root )
    ( if ( or ( eq nil treelist ) ( null treelist ) );empty is a tree
         t
         ( if ( = ( length treelist ) 3 )               
            ( progn
                ( setqroot( atom ( car treelist ) ) )
                ( setqleft( istree ( cadr treelist ) ) )
                ( setqright ( istree ( caddr treelist ) ) )
                ( and   root left right )               
            )
            nil
         )   
    )      
)
;;;*****************************************************************************
;;;*****************************************************************************



;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名: PreOrder **********************************************************
;;;说明: 满二叉树的先序遍历*************************************************
;;;参数: treedata 二叉树格式************************************************
;;;例子: (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
;;;输出: 0 1 3 7 8 4 9 10 2 5 11 12 6 13 14 先序遍历输出********************
( defun PreOrder ( treedata )
( if ( not ( atom treedata ) )
    ( progn
      ( princ "\n" )
      ( if ( atom ( car treedata ) )
             ( princ ( car treedata ) )
      )
      ( princ "\n" )
      ( if ( atom ( cadr treedata ) )
             ( princ ( cadr treedata ) )
      )
      ( princ "\n" )
      ( if ( atom ( caddr treedata ) )
             ( princ ( caddr treedata ) )
      )
      ( princ "\n" )
      ( PreOrder ( cadr treedata ) )
      ( PreOrder ( caddr treedata ) )
    )
)
)
;;;*****************************************************************************
;;;*****************************************************************************



;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名: Inorder ***********************************************************
;;;说明: 满二叉树的中序遍历*************************************************
;;;参数: treedata 二叉树格式************************************************
;;;例子: (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
;;;输出: 7 3 8 1 9 4 10 0 11 5 12 2 13 6 14 中序遍历输出********************
( defun Inorder ( treedata )
( if ( not ( atom treedata ) )
    ( progn
      ( Inorder ( cadr treedata ) )
      ( princ "\n" )
      ( if ( atom ( cadr treedata ) )
             ( princ ( cadr treedata ) )
      )
      ( princ "\n" )
      ( if ( atom ( car treedata ) )
             ( princ ( car treedata ) )
      )
      ( princ "\n" )
      ( if ( atom ( caddr treedata ) )
             ( princ ( caddr treedata ) )
      )
      ( princ "\n" )
      ( Inorder ( caddr treedata ) )
    )
)
)
;;;*****************************************************************************
;;;*****************************************************************************



;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名: Postorder *********************************************************
;;;说明: 满二叉树的后序遍历*************************************************
;;;参数: treedata 二叉树格式************************************************
;;;例子: (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
;;;输出: 7 8 3 9 10 4 1 11 12 5 13 14 6 2 0 后序遍历输出********************
( defun Postorder ( treedata )
( if ( not ( atom treedata ) )
    ( progn
      ( Postorder ( cadr treedata ) )
      ( Postorder ( caddr treedata ) )
      
      ( princ "\n" )
      ( if ( atom ( cadr treedata ) )
             ( princ ( cadr treedata ) )
      )
      ( princ "\n" )
      ( if ( atom ( caddr treedata ) )
             ( princ ( caddr treedata ) )
      )
      ( princ "\n" )
      ( if ( atom ( car treedata ) )
             ( princ ( car treedata ) )
      )
      ( princ "\n" )
    )
)
)
;;;*****************************************************************************
;;;*****************************************************************************



;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名: PreOrder2 *********************************************************
;;;说明: 满二叉树的先序遍历*************************************************
;;;参数: treedata 二叉树格式************************************************
;;;例子: (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
;;;输出: 0 1 3 7 8 4 9 10 2 5 11 12 6 13 14 先序遍历输出********************
( defun PreOrder2 ( treedata )
( if ( not ( atom treedata ) )
    ( progn
      ( princ "\n" )
      ( if ( atom ( car treedata ) )
             ( princ ( car treedata ) )
      )
      ( princ "\n" )
      ( if ( atom ( cadr treedata ) )
             ( princ ( cadr treedata ) )
      )
      ( princ "\n" )
      ( if ( atom ( caddr treedata ) )
             ( princ ( caddr treedata ) )
      )
      ( princ "\n" )
      ( PreOrder2 ( cadr treedata ) )
      ( PreOrder2 ( caddr treedata ) )
    )
)
)
;;;*****************************************************************************
;;;*****************************************************************************

自贡黄明儒 发表于 2022-10-28 10:41:49

cad是近视眼，用ssget等函数有些选择失误，这时候遍历整个图形。如果采用此法，是不是比全图选择快些？

陨落 发表于 2022-10-28 10:43:46

自贡黄明儒 发表于 2022-10-28 10:41
cad是近视眼，用ssget等函数有些选择失误，这时候遍历整个图形。如果采用此法，是不是比全图选择快些？

遍历图形要用四叉树或者八叉树

freedom_ice 发表于 2022-10-28 10:50:31

自贡黄明儒 发表于 2022-10-28 10:41
cad是近视眼，用ssget等函数有些选择失误，这时候遍历整个图形。如果采用此法，是不是比全图选择快些？

是的在不涉及交互的时候
尽量不用选择集
用过滤或者遍历
也有人说，过滤也可以不用 这个就不知道为什么了

mahuan1279 发表于 2022-10-28 18:56:36

能根据前序遍历和中序遍历得出后续遍历吗？

nijiea123 发表于 2022-10-31 17:56:57

期待大神开发出这种算法的用处就好

dcl1214 发表于 2022-11-2 00:13:09

本帖最后由 dcl1214 于 2022-11-3 09:38 编辑

我用【迪杰斯特拉】【弗洛伊德】【图论】算法实现过，地图200个分叉点，80万条路径计算很快的

查看完整版本: 二叉树的autolisp实现，算法