二叉树查找函数

Highflybird

1. ;;;=============================================================
   
2. ;;;用AutoLISP从二叉树中查找一个元素(Search a key in binary tree)
   
3. ;;;每次查找总是从中间开始，如果不是，大于中间的就查找右边，小于
   
4. ;;;中间则查找左边，直到原子或者点对表。                        
   
5. ;;;因为树的最大深度不超过log(n)，故单次查找的时间为O(n)<=log(n)
   
6. ;;;-------------------------------------------------------------
   
7. ;;;输入: 要查找的Key，已经构建好的二叉查找树，n查询的最大节点数
   
8. ;;;输出: 如果找到，返回找到的Key的位置。否则返回nil            
   
9. ;;;Author:Highflybird              in Shenzhen,China,2012-06-15
   
10. ;;;=============================================================
    
11. (defun XD::DataSTRU:BTreeFind (key Tree n / L R i)
    
12.   (if (atom Tree)                                               ;if it's an atom,
    
13.     (if (= key Tree) 0)                                         ;set the index as 0
    
14.     (if (= (setq L (car Tree)) key)                             ;if left node = key
    
15.       (/ n 2)                                                   ;the index is the middle number.
    
16.       (if (atom (setq R (cdr Tree)))                            ;if the right node is an atom
    
17.         (if (= R key) 0)                                        ;and right node = key, set the index as 0
    
18.         (if (> L key)                                           ;if left node > key
    
19.           (XD::DataSTRU:BTreeFind key (car R) (/ n 2))                           ;recurse Left
    
20.           (if (setq i (XD::DataSTRU:BTreeFind key (cdr R) (/ (1- n) 2)))         ;otherwise recurse right
    
21.             (1+ (+ (/ n 2) i))                                  ;must add the index
    
22.           )
    
23.         )
    
24.       )
    
25.     )
    
26.   )
    
27. )
    
28. 
    

;;;=============================================================<br /> ;;;用AutoLISP从二叉树中查找一个元素(Search a key in binary tree)<br /> ;;;每次查找总是从中间开始，如果不是，大于中间的就查找右边，小于 <br /> ;;;中间则查找左边，直到原子或者点对表。                         <br /> ;;;因为树的最大深度不超过log(n)，故单次查找的时间为O(n)<=log(n) <br /> ;;;-------------------------------------------------------------<br /> ;;;输入: 要查找的Key，已经构建好的二叉查找树，n查询的最大节点数 <br /> ;;;输出: 如果找到，返回找到的Key的位置。否则返回nil             <br /> ;;;Author:Highflybird              in Shenzhen,China,2012-06-15 <br /> ;;;=============================================================<br /> (defun XD::DataSTRU:BTreeFind (key Tree n / L R i)<br />   (if (atom Tree)                                               ;if it's an atom,<br />     (if (= key Tree) 0)                                         ;set the index as 0<br />     (if (= (setq L (car Tree)) key)                             ;if left node = key<br />       (/ n 2)                                                   ;the index is the middle number.<br />       (if (atom (setq R (cdr Tree)))                            ;if the right node is an atom<br />         (if (= R key) 0)                                        ;and right node = key, set the index as 0<br />         (if (> L key)                                           ;if left node > key<br />           (XD::DataSTRU:BTreeFind key (car R) (/ n 2))                           ;recurse Left<br />           (if (setq i (XD::DataSTRU:BTreeFind key (cdr R) (/ (1- n) 2)))         ;otherwise recurse right<br />             (1+ (+ (/ n 2) i))                                  ;must add the index<br />           )<br />         )<br />       )<br />     )<br />   )<br /> )<br /> <br />

Free-Lancer

函数很好也能学到知识，楼主能给个具体应用例子吗，来自: Android客户端

sicky111

此函数是为了缩短查找时间吗？

pengfei2010

能说一下 能这个的用途吗？是不是缩短程序运行时间呀

Highflybird

sicky111 发表于 2013-6-10 23:06
此函数是为了缩短查找时间吗？

二叉树算法，对于排序查找是个很重要的算法，极大提高排序查找速度。

构建二叉树的函数见另外的帖子发布的 XD::DataStru:BTree 函数。

GTJ116600

Highflybird 发表于 2013-6-11 12:17
二叉树算法，对于排序查找是个很重要的算法，极大提高排序查找速度。

构建二叉树的函数见另外的帖子发 ...

G版，能给个 XD::DataStru:BTree 函数的链接么

GTJ116600

GTJ116600 发表于 2013-6-11 15:04
G版，能给个 XD:ataStru:BTree 函数的链接么

呵呵，我自罚，在Highflybird版主原创前错呼G版。笔误，笔误。谢谢兄弟们指正。也请Highflybird版主
见谅。sicky111兄弟，你说话可真够犀利的，够狠{:soso_e113:}

q3_2006

二叉树?第一次听说呀！