二叉树的autolisp实现，算法

freedom_ice

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

1. ( defun c:xx()
   
2.   ( setq aaa '( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ) )           ;;满二叉树
   
3.   ( setq bbb '( 2 13 55 46 37 8 19 10 15 12 113 14 22 23 25 ) )  ;;满二叉树
   
4.   ( setq bbb '( 2 13 55 46 37 8 19 10 15 12 113 14  ) )          ;;不是满二叉树
   
5.   ;( setq aaa '( 0 1 2 3 4 5 6 ) )
   
6.   ( setq abc ( BinaryTree 0 aaa ) )
   
7.   ( princ abc )
   
8.   ;( istree abc )
   
9.   ;( setq abc ( BinaryTree 0 bbb ) )
   
10.   ;( PreOrder abc )   ;先序遍历
    
11.   ;( Inorder abc )    ;中序遍历
    
12.   ( Postorder abc )  ;后序遍历
    
13. )
    
14. 
    
15. ;;;*****************************************************************************
    
16. ;;;*****************************************************************************
    
17. ;;;函数名  : BinaryTree ********************************************************
    
18. ;;;说  明  : 仅适用于顺序存储转满二叉树的形式***********************************
    
19. ;;;功  能  : 顺序存储转二叉树***************************************************
    
20. ;;;参  数  : i 二叉树深度*******************************************************
    
21. ;;;参  数  : datalist 顺序存储表************************************************
    
22. ;;;返回值  : 二叉树格式*********************************************************
    
23. ;;;例  子  : ( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 )顺序表***********************
    
24. ;;;输  出  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14))) 输出二叉树格式****
    
25. ( defun BinaryTree ( i datalist / left mid n right )
    
26.   ( setq mid nil )
    
27.   ( setq left nil )
    
28.   ( setq right nil )
    
29.   ( setq n ( length datalist ) )
    
30.   (  cond ( ( <= i ( - ( / ( - n 1 ) 2 ) 1 ) )
    
31.            ( progn           
    
32.             ( setq mid ( nth i datalist )   
    
33.                             left ( BinaryTree ( + ( * 2 i ) 1 ) datalist )
    
34.                              right ( BinaryTree ( + ( * 2 i ) 2 ) datalist )
    
35.                      )
    
36.              ( list mid left right )
    
37.            )           
    
38.                    )
    
39.          ( ( and ( > i ( - ( / ( - n 1 ) 2 ) 1 ) )
    
40.                  ( < i n ) )
    
41.            ( setq mid ( nth i datalist ) )            
    
42.          )
    
43.          ( t nil )
    
44.   )
    
45. )
    
46. ;;;*****************************************************************************
    
47. ;;;*****************************************************************************
    
48. 
    
49. 
    
50. ;;;*****************************************************************************
    
51. ;;;*****************************************************************************
    
52. ;;;函数名  : istree ************************************************************
    
53. ;;;说  明  : 判断表数据是否符合满二叉树的格式***********************************
    
54. ;;;参  数  : i 二叉树深度*******************************************************
    
55. ;;;参  数  : datalist 顺序存储表************************************************
    
56. ;;;返回值  : 二叉树格式*********************************************************
    
57. ;;;例  子  : (istree (a (b nil nil) nil)) 二叉树格式****************************
    
58. ;;;输  出  : T 输出真值*********************************************************
    
59. ;;;例  子  : (istree (a (b nil nil))) 非二叉树格式******************************
    
60. ;;;输  出  : NIL 输出假值*******************************************************
    
61. ( defun istree ( treelist / left right root )
    
62.     ( if ( or ( eq nil treelist ) ( null treelist ) )  ;empty is a tree
    
63.          t
    
64.          ( if ( = ( length treelist ) 3 )               
    
65.               ( progn
    
66.                 ( setq  root  ( atom ( car treelist ) ) )
    
67.                 ( setq  left  ( istree ( cadr treelist ) ) )
    
68.                 ( setq  right ( istree ( caddr treelist ) ) )
    
69.                 ( and   root left right )                 
    
70.               )
    
71.               nil
    
72.          )   
    
73.     )      
    
74. )
    
75. ;;;*****************************************************************************
    
76. ;;;*****************************************************************************
    
77. 
    
78. 
    
79. 
    
80. ;;;*****************************************************************************
    
81. ;;;*****************************************************************************
    
82. ;;;函数名  : PreOrder **********************************************************
    
83. ;;;说  明  : 满二叉树的先序遍历*************************************************
    
84. ;;;参  数  : treedata 二叉树格式************************************************
    
85. ;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
    
86. ;;;输  出  : 0 1 3 7 8 4 9 10 2 5 11 12 6 13 14 先序遍历输出********************
    
87. ( defun PreOrder ( treedata )
    
88.   ( if ( not ( atom treedata ) )
    
89.     ( progn
    
90.         ( princ "\n" )
    
91.         ( if ( atom ( car treedata ) )
    
92.              ( princ ( car treedata ) )
    
93.         )
    
94.         ( princ "\n" )
    
95.         ( if ( atom ( cadr treedata ) )
    
96.              ( princ ( cadr treedata ) )
    
97.         )
    
98.         ( princ "\n" )
    
99.         ( if ( atom ( caddr treedata ) )
    
100.              ( princ ( caddr treedata ) )
     
101.         )
     
102.         ( princ "\n" )
     
103.         ( PreOrder ( cadr treedata ) )
     
104.         ( PreOrder ( caddr treedata ) )
     
105.     )
     
106.   )
     
107. )
     
108. ;;;*****************************************************************************
     
109. ;;;*****************************************************************************
     
110. 
     
111. 
     
112. 
     
113. ;;;*****************************************************************************
     
114. ;;;*****************************************************************************
     
115. ;;;函数名  : Inorder ***********************************************************
     
116. ;;;说  明  : 满二叉树的中序遍历*************************************************
     
117. ;;;参  数  : treedata 二叉树格式************************************************
     
118. ;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
     
119. ;;;输  出  : 7 3 8 1 9 4 10 0 11 5 12 2 13 6 14 中序遍历输出********************
     
120. ( defun Inorder ( treedata )
     
121.   ( if ( not ( atom treedata ) )
     
122.     ( progn
     
123.         ( Inorder ( cadr treedata ) )
     
124.         ( princ "\n" )
     
125.         ( if ( atom ( cadr treedata ) )
     
126.              ( princ ( cadr treedata ) )
     
127.         )
     
128.         ( princ "\n" )
     
129.         ( if ( atom ( car treedata ) )
     
130.              ( princ ( car treedata ) )
     
131.         )
     
132.         ( princ "\n" )
     
133.         ( if ( atom ( caddr treedata ) )
     
134.              ( princ ( caddr treedata ) )
     
135.         )
     
136.         ( princ "\n" )
     
137.         ( Inorder ( caddr treedata ) )
     
138.     )
     
139.   )
     
140. )
     
141. ;;;*****************************************************************************
     
142. ;;;*****************************************************************************
     
143. 
     
144. 
     
145. 
     
146. ;;;*****************************************************************************
     
147. ;;;*****************************************************************************
     
148. ;;;函数名  : Postorder *********************************************************
     
149. ;;;说  明  : 满二叉树的后序遍历*************************************************
     
150. ;;;参  数  : treedata 二叉树格式************************************************
     
151. ;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
     
152. ;;;输  出  : 7 8 3 9 10 4 1 11 12 5 13 14 6 2 0 后序遍历输出********************
     
153. ( defun Postorder ( treedata )
     
154.   ( if ( not ( atom treedata ) )
     
155.     ( progn
     
156.         ( Postorder ( cadr treedata ) )
     
157.         ( Postorder ( caddr treedata ) )
     
158.       
     
159.         ( princ "\n" )
     
160.         ( if ( atom ( cadr treedata ) )
     
161.              ( princ ( cadr treedata ) )
     
162.         )
     
163.         ( princ "\n" )
     
164.         ( if ( atom ( caddr treedata ) )
     
165.              ( princ ( caddr treedata ) )
     
166.         )
     
167.         ( princ "\n" )
     
168.         ( if ( atom ( car treedata ) )
     
169.              ( princ ( car treedata ) )
     
170.         )
     
171.         ( princ "\n" )
     
172.     )
     
173.   )
     
174. )
     
175. ;;;*****************************************************************************
     
176. ;;;*****************************************************************************
     
177. 
     
178. 
     
179. 
     
180. ;;;*****************************************************************************
     
181. ;;;*****************************************************************************
     
182. ;;;函数名  : PreOrder2 *********************************************************
     
183. ;;;说  明  : 满二叉树的先序遍历*************************************************
     
184. ;;;参  数  : treedata 二叉树格式************************************************
     
185. ;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
     
186. ;;;输  出  : 0 1 3 7 8 4 9 10 2 5 11 12 6 13 14 先序遍历输出********************
     
187. ( defun PreOrder2 ( treedata )
     
188.   ( if ( not ( atom treedata ) )
     
189.     ( progn
     
190.         ( princ "\n" )
     
191.         ( if ( atom ( car treedata ) )
     
192.              ( princ ( car treedata ) )
     
193.         )
     
194.         ( princ "\n" )
     
195.         ( if ( atom ( cadr treedata ) )
     
196.              ( princ ( cadr treedata ) )
     
197.         )
     
198.         ( princ "\n" )
     
199.         ( if ( atom ( caddr treedata ) )
     
200.              ( princ ( caddr treedata ) )
     
201.         )
     
202.         ( princ "\n" )
     
203.         ( PreOrder2 ( cadr treedata ) )
     
204.         ( PreOrder2 ( caddr treedata ) )
     
205.     )
     
206.   )
     
207. )
     
208. ;;;*****************************************************************************
     
209. ;;;*****************************************************************************

( defun c:xx() <br />   ( setq aaa '( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ) )           ;;满二叉树<br />   ( setq bbb '( 2 13 55 46 37 8 19 10 15 12 113 14 22 23 25 ) )  ;;满二叉树<br />   ( setq bbb '( 2 13 55 46 37 8 19 10 15 12 113 14  ) )          ;;不是满二叉树<br />   ;( setq aaa '( 0 1 2 3 4 5 6 ) )<br />   ( setq abc ( BinaryTree 0 aaa ) )<br />   ( princ abc )<br />   ;( istree abc )<br />   ;( setq abc ( BinaryTree 0 bbb ) )<br />   ;( PreOrder abc )   ;先序遍历<br />   ;( Inorder abc )    ;中序遍历<br />   ( Postorder abc )  ;后序遍历<br /> )<br /> <br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************<br /> ;;;函数名  : BinaryTree ********************************************************<br /> ;;;说  明  : 仅适用于顺序存储转满二叉树的形式***********************************<br /> ;;;功  能  : 顺序存储转二叉树***************************************************<br /> ;;;参  数  : i 二叉树深度*******************************************************<br /> ;;;参  数  : datalist 顺序存储表************************************************<br /> ;;;返回值  : 二叉树格式*********************************************************<br /> ;;;例  子  : ( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 )顺序表***********************<br /> ;;;输  出  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14))) 输出二叉树格式****<br /> ( defun BinaryTree ( i datalist / left mid n right )<br />   ( setq mid nil )<br />   ( setq left nil )<br />   ( setq right nil )<br />   ( setq n ( length datalist ) )<br />   (  cond ( ( <= i ( - ( / ( - n 1 ) 2 ) 1 ) ) <br />            ( progn           <br />             ( setq mid ( nth i datalist )    <br />                             left ( BinaryTree ( + ( * 2 i ) 1 ) datalist ) <br />                              right ( BinaryTree ( + ( * 2 i ) 2 ) datalist )<br />                      )<br />              ( list mid left right )<br />            )           <br />                    )<br />          ( ( and ( > i ( - ( / ( - n 1 ) 2 ) 1 ) ) <br />                  ( < i n ) )<br />            ( setq mid ( nth i datalist ) )            <br />          )<br />          ( t nil )<br />   )<br /> )<br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************<br /> <br /> <br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************<br /> ;;;函数名  : istree ************************************************************<br /> ;;;说  明  : 判断表数据是否符合满二叉树的格式***********************************<br /> ;;;参  数  : i 二叉树深度*******************************************************<br /> ;;;参  数  : datalist 顺序存储表************************************************<br /> ;;;返回值  : 二叉树格式*********************************************************<br /> ;;;例  子  : (istree (a (b nil nil) nil)) 二叉树格式****************************<br /> ;;;输  出  : T 输出真值*********************************************************<br /> ;;;例  子  : (istree (a (b nil nil))) 非二叉树格式******************************<br /> ;;;输  出  : NIL 输出假值*******************************************************<br /> ( defun istree ( treelist / left right root )<br />     ( if ( or ( eq nil treelist ) ( null treelist ) )  ;empty is a tree<br />          t<br />          ( if ( = ( length treelist ) 3 )               <br />               ( progn<br />                 ( setq  root  ( atom ( car treelist ) ) )<br />                 ( setq  left  ( istree ( cadr treelist ) ) )<br />                 ( setq  right ( istree ( caddr treelist ) ) )<br />                 ( and   root left right )                 <br />               ) <br />               nil<br />          )    <br />     )      <br /> )<br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************<br /> <br /> <br /> <br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************<br /> ;;;函数名  : PreOrder **********************************************************<br /> ;;;说  明  : 满二叉树的先序遍历*************************************************<br /> ;;;参  数  : treedata 二叉树格式************************************************<br /> ;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************<br /> ;;;输  出  : 0 1 3 7 8 4 9 10 2 5 11 12 6 13 14 先序遍历输出********************<br /> ( defun PreOrder ( treedata )<br />   ( if ( not ( atom treedata ) )<br />     ( progn <br />         ( princ "\n" )<br />         ( if ( atom ( car treedata ) )<br />              ( princ ( car treedata ) ) <br />         )<br />         ( princ "\n" )<br />         ( if ( atom ( cadr treedata ) )<br />              ( princ ( cadr treedata ) ) <br />         )<br />         ( princ "\n" )<br />         ( if ( atom ( caddr treedata ) )<br />              ( princ ( caddr treedata ) ) <br />         )<br />         ( princ "\n" )<br />         ( PreOrder ( cadr treedata ) )<br />         ( PreOrder ( caddr treedata ) )<br />     )<br />   )<br /> )<br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************<br /> <br /> <br /> <br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************<br /> ;;;函数名  : Inorder ***********************************************************<br /> ;;;说  明  : 满二叉树的中序遍历*************************************************<br /> ;;;参  数  : treedata 二叉树格式************************************************<br /> ;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************<br /> ;;;输  出  : 7 3 8 1 9 4 10 0 11 5 12 2 13 6 14 中序遍历输出********************<br /> ( defun Inorder ( treedata )<br />   ( if ( not ( atom treedata ) )<br />     ( progn <br />         ( Inorder ( cadr treedata ) )<br />         ( princ "\n" )<br />         ( if ( atom ( cadr treedata ) )<br />              ( princ ( cadr treedata ) ) <br />         )<br />         ( princ "\n" )<br />         ( if ( atom ( car treedata ) )<br />              ( princ ( car treedata ) ) <br />         )<br />         ( princ "\n" )<br />         ( if ( atom ( caddr treedata ) )<br />              ( princ ( caddr treedata ) ) <br />         )<br />         ( princ "\n" )<br />         ( Inorder ( caddr treedata ) )<br />     )<br />   )<br /> )<br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************<br /> <br /> <br /> <br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************<br /> ;;;函数名  : Postorder *********************************************************<br /> ;;;说  明  : 满二叉树的后序遍历*************************************************<br /> ;;;参  数  : treedata 二叉树格式************************************************<br /> ;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************<br /> ;;;输  出  : 7 8 3 9 10 4 1 11 12 5 13 14 6 2 0 后序遍历输出********************<br /> ( defun Postorder ( treedata )<br />   ( if ( not ( atom treedata ) )<br />     ( progn <br />         ( Postorder ( cadr treedata ) )<br />         ( Postorder ( caddr treedata ) )<br />       <br />         ( princ "\n" )<br />         ( if ( atom ( cadr treedata ) )<br />              ( princ ( cadr treedata ) ) <br />         )<br />         ( princ "\n" )<br />         ( if ( atom ( caddr treedata ) )<br />              ( princ ( caddr treedata ) ) <br />         )<br />         ( princ "\n" )<br />         ( if ( atom ( car treedata ) )<br />              ( princ ( car treedata ) ) <br />         )<br />         ( princ "\n" )<br />     )<br />   )<br /> )<br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************<br /> <br /> <br /> <br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************<br /> ;;;函数名  : PreOrder2 *********************************************************<br /> ;;;说  明  : 满二叉树的先序遍历*************************************************<br /> ;;;参  数  : treedata 二叉树格式************************************************<br /> ;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************<br /> ;;;输  出  : 0 1 3 7 8 4 9 10 2 5 11 12 6 13 14 先序遍历输出********************<br /> ( defun PreOrder2 ( treedata )<br />   ( if ( not ( atom treedata ) )<br />     ( progn <br />         ( princ "\n" )<br />         ( if ( atom ( car treedata ) )<br />              ( princ ( car treedata ) ) <br />         )<br />         ( princ "\n" )<br />         ( if ( atom ( cadr treedata ) )<br />              ( princ ( cadr treedata ) ) <br />         )<br />         ( princ "\n" )<br />         ( if ( atom ( caddr treedata ) )<br />              ( princ ( caddr treedata ) ) <br />         )<br />         ( princ "\n" )<br />         ( PreOrder2 ( cadr treedata ) )<br />         ( PreOrder2 ( caddr treedata ) )<br />     )<br />   )<br /> )<br /> ;;;*****************************************************************************<br /> ;;;*****************************************************************************

自贡黄明儒

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

陨落

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

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

freedom_ice

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

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

mahuan1279

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

nijiea123

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

dcl1214

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