Author Topic: Binary Tree Algorithm  (Read 11673 times)

0 Members and 1 Guest are viewing this topic.

udaaf

  • Guest
Binary Tree Algorithm
« on: July 25, 2013, 04:56:20 AM »
I wondering how to convert list for example :

Code: [Select]
(setq SeqNum (list "0" "1" "2" "2.1" "2.2" "2.3"))
I wanna result like this one

Quote
;Result
(1    2    4    5    7    9)
(12    3    11   6   8   10)
;OR
((1 12) (2 3) (4 11) (5 6) (7 8) (9 10))

I have create some function but stuck  :-). Hope anyone here can help me.

Here's my code :

Code: [Select]
;Fungsi mencari jumlah karakter tertentu pada kumpulan karakter
(defun JumKar (string cari)
  (setq counter 0)
  (setq i 1)
  (repeat (strlen string)
    ;mencari dan mengambil karakter pada posisi dan jumlah yang akan diambil
    ;membuang karakter spasi pada saat pencarian
    (setq a (substr string i (strlen (setq b (vl-string-trim " " cari)))))
    (if (= a b)
      (setq counter (1+ counter))
      );if
    (setq i (1+ i))
    );repeat
    (setq JumlahKar counter)
  );defun
;Fungsi mencari posisi
(defun CarPos (string cari / i tampung posisi)
  (setq counter 0)
  (setq i 1)
  (setq tampung nil)
  (repeat (strlen string)
    ;mencari dan mengambil karakter pada posisi dan jumlah yang akan diambil
    ;membuang karakter spasi pada saat pencarian
    (setq a (substr string i (strlen (setq b (vl-string-trim " " cari)))))
    (setq posisi i)
    (if (= a b)
      (setq tampung (cons posisi tampung))
      );if
    (setq i (1+ i))
    );repeat
    (setq posisi (reverse tampung))
  );defun
;Cara penggunaan fungsi.
(CARPOS "3.500.67.2" ".")
;-------------------------------------------------
(setq SeqNum (list "0" "1" "2" "2.1" "2.2" "2.3"))
(Setq LenList (length SeqNum))
(setq lft nil
      rgt nil
      );setq
(setq i 1
      j 1
      k 1
      l 1
      m 1
      n 1
      )
;Fungsi jumlah karakter pada urutan list
(defun CharL (n string)
  (strlen (nth n String))
  );defun
 
       
;Tree
(repeat LenList
  (cond
    ((= i 1)
     (progn
       (setq lft (cons i lft))
       (setq i (1+ i))
       );progn
     );cond_1
    ((= (CharL (1- i) SeqNum) (CharL i SeqNum))
     (setq lft (cons (* i 2) lft))
     
     (setq lft (cons (+ i 1) lft))
     );cond_2
    );cond
  );repeat

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #1 on: July 25, 2013, 05:43:37 AM »
For a Binary Tree each node can have only 2 arms, so the branches in your diagram are incorrect.
Perhaps you will need to redraw the tree so the algorithm can be determined.
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #2 on: July 25, 2013, 05:55:50 AM »
Perhaps something like this :

kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #3 on: July 25, 2013, 06:07:36 AM »
I think your terminology might be wrong. As Kerry's pointed out a binary tree can have only 0, 1 or 2 branches from any one node.

Are you perhaps referring to a Tree data structure? In that case any node may have 0 through to N sub-nodes. And in Lisp such a structure is nothing other than a set of nested lists. E.g. your structure would look something like this
Code: [Select]
((1 12)
  ((2 3))
  ((4 11)
    ((5 6))
    ((7 8))
    ((9 10))
  )
)
In this case the 1st item in any node is the data. If the data consists of more than one value, then that 1st item itself is a list.

The rest (if any) are the direct child nodes of the current node. They in turn are defined in exactly the same way as the parent node is. I.e. (as with all trees) the entire structure is a recursive structure: any node along the tree is itself also a tree.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #4 on: July 25, 2013, 06:16:46 AM »

I'd have  assumed than empty links should be `nil` rather than numbered.
I haven't looked at your code yet .. I'd prefer to wait for a complete description of the problem.
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #5 on: July 25, 2013, 06:22:42 AM »
<..>

Are you perhaps referring to a Tree data structure? In that case any node may have 0 through to N sub-nodes. And in Lisp such a structure is nothing other than a set of nested lists.

irneb, if it's a Tree Data Structure the arrangement of the data in the original definition list will need to be structured to represent the design ... so it can't be a single list as indicated by the original post.
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #6 on: July 25, 2013, 06:28:05 AM »
Exactly. E.g.
Code - Auto/Visual Lisp: [Select]
  1. (defun Tree:GetFromIndex (index tree)
  2.   (cond ((not index) tree)
  3.         ((Tree:GetFromIndex (cdr index) (nth (car index) tree)))))
  4.  
  5. (setq Tree:GetValue car)
So having the same structure as the OP:
Code: [Select]
_$ (setq tree '((1 12) ((2 3)) ((4 11) ((5 6)) ((7 8)) ((9 10)))))
((1 12) ((2 3)) ((4 11) ((5 6)) ((7 8)) ((9 10))))
_$ (Tree:GetValue (Tree:GetFromIndex nil tree))
(1 12)
_$ (Tree:GetValue (Tree:GetFromIndex '(1) tree))
(2 3)
_$ (Tree:GetValue (Tree:GetFromIndex '(2) tree))
(4 11)
_$ (Tree:GetValue (Tree:GetFromIndex '(2 1) tree))
(5 6)
_$ (Tree:GetValue (Tree:GetFromIndex '(2 2) tree))
(7 8)
_$ (Tree:GetValue (Tree:GetFromIndex '(2 3) tree))
(9 10)
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #7 on: July 25, 2013, 06:47:33 AM »
Actually, to use 0 indexing as the actual value
Code - Auto/Visual Lisp: [Select]
  1. (defun Tree:GetFromIndex (index tree)
  2.   (cond ((or (not index) (= index 0)) tree)
  3.         ((atom index) (nth index tree))
  4.         ((= (length index) 1) (Tree:GetFromIndex (car index) tree))
  5.         ((Tree:GetFromIndex (cdr index) (nth (car index) tree)))))
  6.  
  7. (setq Tree:GetValue car)
Then
Code: [Select]
_$ (Tree:GetValue (Tree:GetFromIndex 2 tree))
(4 11)
_$ (Tree:GetValue (Tree:GetFromIndex 0 tree))
(1 12)
_$ (Tree:GetValue (Tree:GetFromIndex '(1 0) tree))
(2 3)
_$ (Tree:GetValue (Tree:GetFromIndex '(1) tree))
(2 3)
_$ (Tree:GetValue (Tree:GetFromIndex '(2 0) tree))
(4 11)
_$ (Tree:GetValue (Tree:GetFromIndex '(2 1) tree))
(5 6)
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #8 on: July 25, 2013, 06:55:24 AM »
I thought he wanted to build a tree from a simple list ??
Code - Auto/Visual Lisp: [Select]
  1. (setq SeqNum (list "0" "1" "2" "2.1" "2.2" "2.3"))

Wouldn't the `tree` variable you have manually constructed be dependant on the data in  `SeqNum` ?

kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #9 on: July 25, 2013, 08:21:51 AM »
Yes, to build that tree, you'd need to parse each of those "indexes". Sort them into the "deepest" and last index - i.e. reversed. Then cons per level. Each time the level changes the consed list becomes a child of the new list. Don't have the time just now, will write-up some code tonight.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #10 on: July 25, 2013, 11:00:24 AM »
I thought he wanted to build a tree from a simple list ??
Code - Auto/Visual Lisp: [Select]
  1. (setq SeqNum (list "0" "1" "2" "2.1" "2.2" "2.3"))

Wouldn't the `tree` variable you have manually constructed be dependant on the data in  `SeqNum` ?

Yes, I want to build tree and get number of abbreviations for left and right from the 'SeqNum'.
And you right, in the theory one node can have <= 2 arms.
Sorry I'm wrong for called the Trees. In my Tree structure is called 3-ary Tree. And this structure arms like the BOM structure in Inventor. I just want to convert the data from the list into abbreviations number for left and right.
 

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #11 on: July 25, 2013, 11:25:24 AM »
udaaf,

Sorry, I can't relate your CAD drawing with Figure 2 and the with the data list

Can you please provide several examples of data lists ( several different sizes) with the matching tree diagram filled in with all values.

In your figure 2 , do the empty squares have a value or not ?

My difficulty is understanding how you are determining which values are assigned to which nodes.

Regards,
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #12 on: July 25, 2013, 12:04:35 PM »
Kelly,

Please find attached file.

Thanks,

Udaaf

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #13 on: July 25, 2013, 02:45:01 PM »
Hang on a sec.
  • Is this tree always 0 or 3 subnodes? This seems negative, because your root node only has 2 subnodes, even though the rest seem to have 0 or 3.
  • Is it always filled? I.e. you wouldn't skip a number, say have 2.1 and 2.3 but not 2.2.
  • If filled, does it also fill from the left? E.g. you'd never have a situation where 1 has no subnodes, but 2 has some. This also seems negative, since your first sample has 1 with 0 nodes, and 2 with 3 nodes.
  • Is it balanced? I.e. it's always as flat as it can be made, no situations where you might have a 1.1.1 but 2 doesn't have any subnodes.
The reason I'm asking is that if all those questions are answered in the negative, then this tree structure is quite complex to build programatically. Many checks to go through in order to place the correct item in the correct level at the correct branch.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #14 on: July 25, 2013, 03:30:26 PM »
Actually, ignoring any constrictions on the tree makes life easier:
Code - Auto/Visual Lisp: [Select]
  1. (defun Tree:GetFromIndex (index tree)
  2.   (cond ((or (not index) (= index 0)) tree)
  3.         ((atom index) (if (< index (length tree)) (nth index tree)))
  4.         ((= (length index) 1) (Tree:GetFromIndex (car index) tree))
  5.         ((Tree:GetFromIndex (cdr index) (nth (car index) tree)))))
  6.  
  7. (setq Tree:GetValue car)
  8.  
  9. (defun Tree:ParseIndex (index / )
  10.   (read (strcat "(" (vl-string-translate "." " " index) ")")))
  11.  
  12. (defun Tree:SetValueAtIndex (tree index value / doSet)
  13.   (defun doSet (tree index / tmp)
  14.     (cond ((or (not index) (= index 0)) (cons value (cdr tree)))
  15.           ((atom index)
  16.            (repeat index (setq tmp (cons (car tree) tmp) tree (cdr tree)))
  17.            (append (reverse tmp) (list (doSet (car tree) nil)) (cdr tree)))
  18.           ((= (length index) 1) (doSet tree (car index)))
  19.           (t
  20.            (repeat (car index) (setq tmp (cons (car tree) tmp) tree (cdr tree)))
  21.            (append (reverse tmp) (list (doSet (car tree) (cdr index))) (cdr tree)))))
  22.   (doSet tree index))
  23.  
  24. (defun Tree:Make (idxLst dataLst / tree)
  25.   (mapcar (function (lambda (idx data) (setq tree (Tree:SetValueAtIndex tree idx data))))
  26.           idxLst dataLst)
  27.   tree)
  28.  
  29. ;| Testing code
  30. (setq testData '((1 "Albert" 12) (2 "Bert" 3) (4 "Chuck" 11) (5 "Donna" 6) (7 "Eddie" 8) (9 "Fred" 10))
  31.       testIndex '("0" "1" "2" "2.1" "2.2" "2.3"))
  32. (setq testTree (Tree:Make (mapcar 'Tree:ParseIndex testIndex) testData))
  33. (Tree:GetFromIndex (Tree:ParseIndex "2.2") testTree) ;Returns (7 "Eddie" 8)
  34. |;
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #15 on: July 25, 2013, 03:38:31 PM »
Now, I'm just guessing here, but are those numbers the sequence numbers for traversal? Do you actually want to generate those from the tree itself?
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: Binary Tree Algorithm
« Reply #16 on: July 25, 2013, 06:05:41 PM »
From what I understand, trees aren't necessarily sorted like that guys [ 0, 1, 2, 3... ]. ...that would be just be a flat list then. Trees are good for fast searching and whatnot so it could be in any order (actually that's all my experience with them is; create a node when you discover an item you want to store and keep adding to the tree as you keep parsing--add nodes; small on the left, and big on the right-).

About nodes, each node can contain as much information as you want. However the bigger the node the more memory usage. I'm working on a node right now where I'm storing all the integers in a tree and in each node I store the int and two char strings and an enum (another int).

I have been looking at these pictures and from what I can see, this looks like a simple association list kind of thing (I think).
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #17 on: July 25, 2013, 07:45:04 PM »
John,
The tree is simply an ordered Tree using a Universal Address System

This is from the linked pdf.



http://csis.bits-pilani.ac.in/faculty/nirmal/dscs/Intro_Trees.pdf
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #18 on: July 25, 2013, 07:55:19 PM »
udaaf,
The tree is ordered and has a unique naming index for each node.
The nodes can be traversed easily without additional link numbers( the left and right sequence numbers youve used).

Is there a particular reason you want to add the sequence numbers.??

What sort of data do you want to associate with each node ( or edge) ??

It's pointless writing code (other than for just it's acedemic value) without knowing the rules to your problem ... 

Regards, Kerry

p.s. :
Keeping in mind that the tree is just a visualisation of the indexing for your data ;
it seems to me that for a lisp solution a nested cons list with each recursive data level represented by a level in the tree may be a viable solution.
This assumed that you have control of the data structure.
« Last Edit: July 25, 2013, 08:02:50 PM by Kerry »
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #19 on: July 25, 2013, 08:49:13 PM »
Hi Irneb,

Thanks for your reply. Please find the answer in blue color.
Hang on a sec.
  • Is this tree always 0 or 3 subnodes? This seems negative, because your root node only has 2 subnodes, even though the rest seem to have 0 or 3.
For the root yes index always 0 and for subnode can > 2
   
  • Is it always filled? I.e. you wouldn't skip a number, say have 2.1 and 2.3 but not 2.2.
Yes always filled with sequence number 2.1 -> 2.2 not 2.3
   
  • If filled, does it also fill from the left? E.g. you'd never have a situation where 1 has no subnodes, but 2 has some. This also seems negative, since your first sample has 1 with 0 nodes, and 2 with 3 nodes.
Yes I always fill from the left. If not find subnodes or it's called leaf the number will fill the right position
   
  • Is it balanced? I.e. it's always as flat as it can be made, no situations where you might have a 1.1.1 but 2 doesn't have any subnodes.
Sometimes I'll have number 1-1.1-1.1.1-1.1.2-1.2
[/list]The reason I'm asking is that if all those questions are answered in the negative, then this tree structure is quite complex to build programatically. Many checks to go through in order to place the correct item in the correct level at the correct branch.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #20 on: July 25, 2013, 09:05:25 PM »
Hi Kerry,

Thank for your replay and explanation  :-).
Please find the answer in blue color.
udaaf,
The tree is ordered and has a unique naming index for each node.
The nodes can be traversed easily without additional link numbers( the left and right sequence numbers youve used).

Is there a particular reason you want to add the sequence numbers.??
Yes. There is a particular reason for add sequence numbers. Because I wanna to add sequence number into table for query the database
What sort of data do you want to associate with each node ( or edge) ??

It's pointless writing code (other than for just it's acedemic value) without knowing the rules to your problem ... 

Regards, Kerry

p.s. :
Keeping in mind that the tree is just a visualisation of the indexing for your data ;
it seems to me that for a lisp solution a nested cons list with each recursive data level represented by a level in the tree may be a viable solution.
This assumed that you have control of the data structure.


Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #21 on: July 25, 2013, 09:29:47 PM »
The potential problem with the system you propose is that if you add (or remove) sub-assemblies or parts to your tree the left and right links will be forced to change, making maintenance a nightmare.

Refer to the Ordered Tree using a Universal Address System diagram that I posted.

Each vertex with children could be considered a component(sub-assembly) of your assembly( node 0).
Each vertex without children (leaf) would be a part of its parent component.
So your database need only refer to the node index without the additional left and right numbering.

I'll have a look at some code tonight (after 0800 UTC)

Regards, Kerry
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #22 on: July 25, 2013, 09:52:33 PM »
The potential problem with the system you propose is that if you add (or remove) sub-assemblies or parts to your tree the left and right links will be forced to change, making maintenance a nightmare.

Refer to the Ordered Tree using a Universal Address System diagram that I posted.

Each vertex with children could be considered a component(sub-assembly) of your assembly( node 0).
Each vertex without children (leaf) would be a part of its parent component.
So your database need only refer to the node index without the additional left and right numbering.

I'll have a look at some code tonight (after 0800 UTC)

Regards, Kerry

Hi Kerry,

In this case if I add or remove part or assembly, I'll delete the all record first and renumbering and then reload the data. Because I'll save this data in transaction table.

Regards,

Udaaf

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #23 on: July 26, 2013, 01:12:23 AM »
Trees are good for fast searching and whatnot so it could be in any order (actually that's all my experience with them is; create a node when you discover an item you want to store and keep adding to the tree as you keep parsing--add nodes; small on the left, and big on the right-).
You get many different flavours of trees. What you're referring to here is specifically called a Binary Search Tree.

There are even further specializations of that particular type. Look down in that page under the "Optimal binary search trees" heading. One of the flavours of the self-balancing BST is actually one of the algorithms I had to create in one of the exams in my 2nd year CS degree (in 1995): Red Black Tree.

Yes. There is a particular reason for add sequence numbers. Because I wanna to add sequence number into table for query the database
In that case the #1 data #2 needs to be calculated from a traversal of the tree. Will have to look at that. It would be a form of destructive traversal as each node visited would have to modify that node. It would be a form of pre-order traversal.

The potential problem with the system you propose is that if you add (or remove) sub-assemblies or parts to your tree the left and right links will be forced to change, making maintenance a nightmare.
Yep, it means that each time you insert anything into that tree (if it doesn't simply replace an existing node) the entire traversal re-numbering has to be done again. It might be possible to come up with an algorithm to only renumber those nodes which change - potentially halving the average number of changes.
« Last Edit: July 26, 2013, 01:17:19 AM by irneb »
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #24 on: July 26, 2013, 02:03:11 AM »
Here's the code for the pre-order traversal sequencing:
Code - Auto/Visual Lisp: [Select]
  1. (defun Tree:Pre-Order-Traverse (tree visit / )
  2.   (apply visit (list (Tree:GetValue tree)))
  3.   (foreach child (cdr tree) (Tree:Pre-Order-Traverse child visit)))
  4.  
  5. (defun Tree:Pre-Order-Traverse-And-Back (tree visit / val)
  6.   (setq val (apply visit (list (Tree:GetValue tree))))
  7.   (foreach child (cdr tree) (Tree:Pre-Order-Traverse-And-Back child visit))
  8.   (apply visit (list val)))
  9.  
  10. (defun Tree:Pre-Order-Sequence-Index (tree / num result)
  11.   (setq num 0)
  12.   (Tree:Pre-Order-Traverse-And-Back tree
  13.     (function (lambda (val / found)
  14.                 (cond ((and (listp val) (setq found (assoc (car val) result)))
  15.                        (setq result (subst (setq val (append val (list (setq num (1+ num))))) found result)))
  16.                       (t (setq result (cons (setq val (list (setq num (1+ num)) val)) result))))
  17.                 val)))
  18.   (reverse result))
  19.  
  20. ;| Testing code
  21. (setq testData '("Albert" "Bert" "Chuck" "Donna" "Eddie" "Fred")
  22.       testIndex '("0" "1" "2" "2.1" "2.2" "2.3"))
  23. (setq testTree (Tree:Make (mapcar 'Tree:ParseIndex testIndex) testData)) ; Returns ("Albert" ("Bert") ("Chuck" ("Donna") ("Eddie") ("Fred")))
  24. (Tree:GetValue (Tree:GetFromIndex (Tree:ParseIndex "2.2") testTree)) ; Returns "Eddie"
  25. (Tree:Pre-Order-Sequence-Index testTree) ; Returns ((1 "Albert" 12) (2 "Bert" 3) (4 "Chuck" 11) (5 "Donna" 6) (7 "Eddie" 8) (9 "Fred" 10))
  26. |;
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #25 on: July 26, 2013, 02:22:39 AM »
Trees are good for fast searching and whatnot so it could be in any order (actually that's all my experience with them is; create a node when you discover an item you want to store and keep adding to the tree as you keep parsing--add nodes; small on the left, and big on the right-).
You get many different flavours of trees. What you're referring to here is specifically called a Binary Search Tree.

There are even further specializations of that particular type. Look down in that page under the "Optimal binary search trees" heading. One of the flavours of the self-balancing BST is actually one of the algorithms I had to create in one of the exams in my 2nd year CS degree (in 1995): Red Black Tree.

Yes. There is a particular reason for add sequence numbers. Because I wanna to add sequence number into table for query the database
In that case the #1 data #2 needs to be calculated from a traversal of the tree. Will have to look at that. It would be a form of destructive traversal as each node visited would have to modify that node. It would be a form of pre-order traversal.

The potential problem with the system you propose is that if you add (or remove) sub-assemblies or parts to your tree the left and right links will be forced to change, making maintenance a nightmare.
Yep, it means that each time you insert anything into that tree (if it doesn't simply replace an existing node) the entire traversal re-numbering has to be done again. It might be possible to come up with an algorithm to only renumber those nodes which change - potentially halving the average number of changes.

Hi  Irneb,

Thanks for your code. I'll try for learn this code first.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #26 on: July 26, 2013, 02:50:44 AM »
Here's the code for the pre-order traversal sequencing:
Code - Auto/Visual Lisp: [Select]
  1. (defun Tree:Pre-Order-Traverse (tree visit / )
  2.   (apply visit (list (Tree:GetValue tree)))
  3.   (foreach child (cdr tree) (Tree:Pre-Order-Traverse child visit)))
  4.  
  5. (defun Tree:Pre-Order-Traverse-And-Back (tree visit / val)
  6.   (setq val (apply visit (list (Tree:GetValue tree))))
  7.   (foreach child (cdr tree) (Tree:Pre-Order-Traverse-And-Back child visit))
  8.   (apply visit (list val)))
  9.  
  10. (defun Tree:Pre-Order-Sequence-Index (tree / num result)
  11.   (setq num 0)
  12.   (Tree:Pre-Order-Traverse-And-Back tree
  13.     (function (lambda (val / found)
  14.                 (cond ((and (listp val) (setq found (assoc (car val) result)))
  15.                        (setq result (subst (setq val (append val (list (setq num (1+ num))))) found result)))
  16.                       (t (setq result (cons (setq val (list (setq num (1+ num)) val)) result))))
  17.                 val)))
  18.   (reverse result))
  19.  
  20. ;| Testing code
  21. (setq testData '("Albert" "Bert" "Chuck" "Donna" "Eddie" "Fred")
  22.       testIndex '("0" "1" "2" "2.1" "2.2" "2.3"))
  23. (setq testTree (Tree:Make (mapcar 'Tree:ParseIndex testIndex) testData)) ; Returns ("Albert" ("Bert") ("Chuck" ("Donna") ("Eddie") ("Fred")))
  24. (Tree:GetValue (Tree:GetFromIndex (Tree:ParseIndex "2.2") testTree)) ; Returns "Eddie"
  25. (Tree:Pre-Order-Sequence-Index testTree) ; Returns ((1 "Albert" 12) (2 "Bert" 3) (4 "Chuck" 11) (5 "Donna" 6) (7 "Eddie" 8) (9 "Fred" 10))
  26. |;

Hi Irneb,

I had test your code and this is code what I want.
I'll learn your code and link for basic theory.

Code: [Select]
;| Testing code
(setq testData '("M1" "S1" "P1" "S2" "P2" "P5" "P6" "P9" "P0" "P3" "S3" "P4" "P7" "P8")
      testIndex '("0" "1" "1.1" "2" "2.1" "2.1.1" "2.1.2" "2.1.2.1" "2.1.2.2" "2.2" "3" "3.1" "3.1.1" "3.1.2"))
(setq testTree (Tree:Make (mapcar 'Tree:ParseIndex testIndex) testData)) ; Returns ("M1" ("S1" ("P1")) ("S2" ("P2" ("P5") ("P6" ("P9") ("P0"))) ("P3")) ("S3" ("P4" ("P7") ("P8"))))
(Tree:GetValue (Tree:GetFromIndex (Tree:ParseIndex "2.1.2") testTree)) ; Returns "P6"
(Tree:Pre-Order-Sequence-Index testTree) ; Returns ((1 "M1" 28) (2 "S1" 5) (3 "P1" 4) (6 "S2" 19) (7 "P2" 16) (8 "P5" 9) (10 "P6" 15) (11 "P9" 12) (13 "P0" 14) (17 "P3" 18) (20 "S3" 27) (21 "P4" 26) (22 "P7" 23) (24 "P8" 25))
|;

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #27 on: July 26, 2013, 03:57:40 AM »
Glad it worked for you. Just note that the code is meant for a generic multi node tree. There's nothing "special" about it as it doesn't enforce stuff like maximum children or balancing at all. You could use it as the base for other types of trees, or you could re-write to implement something like a binary search tree - the principles are very much the same.

That I leave for someone else  :wink: You tend to learn more by doing than by seeing. Tip: the trick with trees is to use recursion. It makes life a lot simpler.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #28 on: July 26, 2013, 04:51:13 AM »
Glad it worked for you. Just note that the code is meant for a generic multi node tree. There's nothing "special" about it as it doesn't enforce stuff like maximum children or balancing at all. You could use it as the base for other types of trees, or you could re-write to implement something like a binary search tree - the principles are very much the same.

That I leave for someone else  :wink: You tend to learn more by doing than by seeing. Tip: the trick with trees is to use recursion. It makes life a lot simpler.

I thought for the beginning your code is more than enough.
And thank you very much for your tips n trick  :-)

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #29 on: July 26, 2013, 05:08:08 AM »
Thanks irned,
saved me from translating some Python code I wrote a couple of months ago.
I'll go watch the football instead :)

udaaf
Looks like you're well on your way now.
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #30 on: July 26, 2013, 05:16:52 AM »
Thanks irned,
saved me from translating some Python code I wrote a couple of months ago.
I'll go watch the football instead :)

udaaf
Looks like you're well on your way now.

@Kerry,
Yes, Of course  :-D

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: Binary Tree Algorithm
« Reply #31 on: July 26, 2013, 11:39:12 AM »
John,
The tree is simply an ordered Tree using a Universal Address System
...
http://csis.bits-pilani.ac.in/faculty/nirmal/dscs/Intro_Trees.pdf

Whoa?! Damn near a forest of trees. I need to do some reading! Thank you.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: Binary Tree Algorithm
« Reply #32 on: July 26, 2013, 11:43:47 AM »
You get many different flavours of trees. What you're referring to here is specifically called a Binary Search Tree.
...

Thanks for the links! ...Off to read.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

reltro

  • Guest
Re: Binary Tree Algorithm
« Reply #33 on: July 28, 2013, 05:25:55 AM »
Hey...
Im not sure if the following Routines are usefull to build a binary tree, but they build a tree ;)
Just try it out...

They work recursivly, but anonym recursiv...
(without vl-....)

Code: [Select]
(setq setter
     (    (lambda (setter /)
               (eval (list 'lambda '(data key newValue / ) (list setter setter 'data 'key 'newValue)))
          )
          (lambda (setter data key newValue / )
               (cond
                    ((and (listp data) (not (and (atom (cdr data)) (not (null (cdr data))))) (apply 'and (mapcar 'listp data)))
                         (     (lambda (subdata otherdata / )
                                   (cond
                                        ((and (null (cdr key)) newValue)
                                             (cons (list (car key) newValue) otherdata)
                                        )
                                        ((and (null (cdr key)) (null newValue)) otherdata)
                                        ('T
                                             (     (lambda (rec / )
                                                       (if rec
                                                            (cons (list (car key) rec) otherdata)
                                                            otherdata
                                                       )
                                                  )
                                                  (setter setter subdata (cdr key) newValue)
                                             )
                                        )
                                   )
                              )
                              (cadr (assoc (car key) data))
                              (     (lambda (nose tail / )
                                        (repeat (length tail) (setq nose (cdr nose)))
                                        (append (cdr tail) (reverse nose))
                                   )
                                   (reverse data)
                                   (member (assoc (car key) data) data)
                              )
                         )
                    )
                    ('T (if newValue
                              (list
                                   (list
                                        (car key)
                                        (     (lambda (k / )
                                                  (while k
                                                       (setq newValue (list (cons (car k) (list newValue))))
                                                       (setq k (cdr k))
                                                  )
                                                  newValue
                                             )
                                             (reverse (cdr key))
                                        )
                                   )
                              )
                         )
                    )
               )
          )
     )
)
;-------------------------------------------------
(setq getter
     (    (lambda (getter / )
               (eval (list 'lambda '(data key / ) (list getter getter 'data 'key)))
          )
          (lambda (getter data key / )
               (cond
                    ((and (listp data) (not (and (atom (cdr data)) (not (null (cdr data))))) (apply 'and (mapcar 'listp data)))
                         (     (lambda (subdata / )
                                   (if (null (cdr key)) subdata
                                        (getter getter subdata (cdr key))
                                   )
                              )
                              (cadr (assoc (car key) data))
                         )
                    )
                    ('T  data)
               )
          )
     )
)


Usage:

(setq DataBase (setter nil '(1 2 3 4) "DataItem"))
;-> ((1 ((2 ((3 ((4 "DataItem"))))))))

(setq DataBase (setter DataBase '(1 2 3 5) "DataItem2"))
;-> ((1 ((2 ((3 ((5 "DataItem2") (4 "DataItem"))))))))

(setq DataBase (setter DataBase '(1 2 2) "DataItem3"))
;-> ((1 ((2 ((2 "DataItem3") (3 ((5 "DataItem2") (4 "DataItem"))))))))

;;toRemove a DataItem
(setq DataBase (setter DataBase '(1 2 3 4) nil))
;-> ((1 ((2 ((3 ((5 "DataItem2"))) (2 "DataItem3"))))))

;; and the 'getter' Function
(getter DataBase '(1 2 2))
;-> "DataItem3"

greets reltro

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #34 on: July 28, 2013, 06:17:02 AM »
reltro,
Just for interest, which language did you work with before using AutoLisp ??

...
and why do use double parenthesis for the result ?
added: I see what you did now.
« Last Edit: July 28, 2013, 07:35:17 AM by Kerry »
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

reltro

  • Guest
Re: Binary Tree Algorithm
« Reply #35 on: July 28, 2013, 06:44:11 AM »
Hey Kerry...
Autolisp was the firts language I learned...

I don't work as a programmer, so I don't know/understand the benefits of a binarytree... Im studing architecture...

I use double parenthesis because someone told me that for Example '(1 2 . 2) is not a valid Data in AutoLisp...
This one came up if u want to Store a dotteddPair, u know: (cons 1 '(2 . 2))



For this task:
Code: [Select]
(setq MakeTree
     (lambda (indexLst Datalst / DataBase)
          (foreach i      (mapcar
                              '(lambda (index DataItem / )
                                   (list
                                        (read (strcat "(" (vl-string-translate "." " " index) ")"))
                                        DataItem
                                   )
                              )
                              indexLst
                              Datalst
                         )
               (setq DataBase (apply 'setter (cons DataBase i)))
          )
     )
)
(setq GetFromIndex (lambda (DataBase Index / ) (getter DataBase (read (strcat "(" (vl-string-translate "." " " index) ")")))))


Code: [Select]
(setq Tree
(MakeTree
'("0" "1" "1.1" "2" "2.1" "2.1.1" "2.1.2" "2.1.2.1" "2.1.2.2" "2.2" "3" "3.1" "3.1.1" "3.1.2")
'("M1" "S1" "P1" "S2" "P2" "P5" "P6" "P9" "P0" "P3" "S3" "P4" "P7" "P8")
)
)

;-> ((3 ((1 ((2 "P8") (1 "P7"))))) (2 ((2 "P3") (1 ((2 ((2 "P0") (1 "P9"))) (1 "P5"))))) (1 ((1 "P1"))) (0 "M1"))

(getFromIndex Tree "2.1.2.1")

irneb:
;(read (strcat "(" (vl-string-translate "." " " index) ")"))
this is so nice :)

greets
« Last Edit: July 28, 2013, 07:01:11 AM by reltro »

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #36 on: July 28, 2013, 07:16:00 AM »
You will need to have another look at your routine ... all values are not in the tree.
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

reltro

  • Guest
Re: Binary Tree Algorithm
« Reply #37 on: July 28, 2013, 07:24:47 AM »
Oh, ur right... Thanks Kerry

I don't wrote the routines for this thread...
I don't tought about this, because I use it in an other way...

to refer to a binaryTree I can store Data only in a leaf...

Will build an other Version soon...

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #38 on: July 28, 2013, 09:11:03 AM »
irneb:
;(read (strcat "(" (vl-string-translate "." " " index) ")"))
this is so nice :)
:lol: I can't take the credit entirely, I saw this principle from some other threads a long time ago. Just can't remember which. It was probably one of the parsing strings (like in reading a CSV file).

I try to make my code as simple as possible. Though I'm still not as good at it as some others here. E.g. that nested mapcar thread is a place where Lee beat me at simplicity as well as performance :wink: That is actually very close to the traversing functions in this thread, at least related.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

reltro

  • Guest
Re: Binary Tree Algorithm
« Reply #39 on: July 28, 2013, 10:10:18 AM »
Kerry,
the 'new' Version:

WithOut vl-...
Code: [Select]
(apply
   '(lambda (ParseIndex setter getter / )
      (list
         (eval
            (list 'defun 'Tree:make '(IndexLst DataLst / )
               (list
                  (lambda (ParseIndex setter / Tree)
                     (mapcar '(lambda (i d / ) (setq Tree (setter Tree (ParseIndex i) d))) IndexLst DataLst)
                     Tree
                  )
                  ParseIndex
                  setter
               )
            )
         )
         (eval (list 'defun 'Tree:get '(Tree Index / ) (list getter 'Tree (list ParseIndex 'Index))))
         (eval (list 'defun 'Tree:set '(Tree Index Value / ) (list setter 'Tree (list ParseIndex 'Index) 'Value)))
      )
   )
   (list
      (lambda (Index / )
         (mapcar 'read
            (   (lambda (str sep / tmp Out)
                  (if (= sep "")
                     (   (lambda (str / res i)
                           (setq i 0)
                           (reverse (repeat (strlen str) (setq res (cons (substr str (setq i (1+ i)) 1) res))))
                        )
                        str
                     )
                     (progn
                        (setq tmp "")
                        (while (not (= str ""))
                           (if (eq (substr str 1 (strlen sep)) sep)
                              (setq    Out      (cons tmp Out)
                                    str      (substr str (strlen sep))
                                    tmp      ""
                              )
                              (setq tmp (strcat tmp (substr str 1 1)))
                           )
                           (setq str (substr str 2))
                        )
                        (reverse (cons tmp Out))
                     )
                  )
               )
               Index
               "."
            )
         )
      )
      ;-------------------------------------------------
      (   (lambda (setter / ) (eval (list 'lambda '(Tree Index Value / ) (list setter setter 'Tree 'Index 'Value))))
         (lambda (setter Tree Index Value / subdata i res remove)
            (if   (and Tree (setq subdata (assoc (car Index) Tree)))
               (progn
                  (setq remove (lambda (toRemove from / res) (reverse (foreach i from (if (not (equal toRemove i))(setq res (cons i res)))))))
                  (if (cdr Index)
                     (remove
                        nil
                        (mapcar
                           '(lambda (a / ) (if (and (null (cadr a)) (null (caddr a))) nil a))
                           (subst
                              (list
                                 (car subdata)
                                 (cadr subdata)
                                 (setter setter (caddr subdata) (cdr Index) Value)
                              )
                              subdata
                              Tree
                           )
                        )
                     )
                     (if (or Value (caddr subdata))
                        (subst
                           (cons (car subdata) (cons Value (cddr subdata)))
                           subdata
                           Tree
                        )
                        (remove subdata Tree)
                     )
                  )
               )
               (if Value
                  (cons
                     (repeat (length (setq Index (reverse Index)))
                        (setq res
                           (list
                              (nth (if i i (setq i 0)) Index)
                              (if (= (setq i (1+ i)) 1) Value)
                              (if res (list res) nil)
                           )
                        )
                     )
                     Tree
                  )
                  Tree
               )
            )
         )
      )
      ;-------------------------------------------------
      (lambda (Tree Index / )
         (while Index
            (setq Tree
               (   (lambda (res / )
                     (if (setq Index (cdr Index))
                        (caddr res)
                        (cadr res)
                     )
                  )
                  (assoc (car Index) Tree)
               )
            )
         )
      )
   )
)

With vl-remove , vl-remove-if-not , vl-string-translate
Code: [Select]
(apply
   '(lambda (ParseIndex setter getter / )
      (list
         (eval
            (list 'defun 'Tree:make '(IndexLst DataLst / )
               (list
                  (lambda (ParseIndex setter / Tree)
                     (mapcar '(lambda (i d / ) (setq Tree (setter Tree (ParseIndex i) d))) IndexLst DataLst)
                     Tree
                  )
                  ParseIndex
                  setter
               )
            )
         )
         (eval (list 'defun 'Tree:get '(Tree Index / ) (list getter 'Tree (list ParseIndex 'Index))))
         (eval (list 'defun 'Tree:set '(Tree Index Value / ) (list setter 'Tree (list ParseIndex 'Index) 'Value)))
      )
   )
   (list
      (lambda (Index / ) (read (strcat "(" (vl-string-translate "." " " index) ")")))
      ;-------------------------------------------------
      (   (lambda (setter / )
            (eval (list 'lambda '(Tree Index Value / ) (list setter setter 'Tree 'Index 'Value)))
         )
         (lambda (setter Tree Index Value / subdata i res)
            (if   (and Tree (setq subdata (assoc (car Index) Tree)))
               (if (cdr Index)
                  (vl-remove-if-not
                     '(lambda (a / ) (or (cadr a) (caddr a)))
                     (subst
                        (list
                           (car subdata)
                           (cadr subdata)
                           (setter setter (caddr subdata) (cdr Index) Value)
                        )
                        subdata
                        Tree
                     )
                  )
                  (if (or Value (caddr subdata))
                     (subst
                        (cons (car subdata) (cons Value (cddr subdata)))
                        subdata
                        Tree
                     )
                     (vl-remove subdata Tree)
                  )
               )
               (if Value
                  (cons
                     (repeat (length (setq Index (reverse Index)))
                        (setq res
                           (list
                              (nth (if i i (setq i 0)) Index)
                              (if (= (setq i (1+ i)) 1) Value)
                              (if res (list res) nil)
                           )
                        )
                     )
                     Tree
                  )
                  Tree
               )
            )
         )
      )
      ;-------------------------------------------------
      (lambda (Tree Index / )
         (while Index
            (setq Tree
               (   (lambda (res / )
                     (if (setq Index (cdr Index))
                        (caddr res)
                        (cadr res)
                     )
                  )
                  (assoc (car Index) Tree)
               )
            )
         )
      )
   )
)

(setq Tree
  (Tree:Make
    '("0" "1" "1.1" "2" "2.1" "2.1.1" "2.1.2" "2.1.2.1" "2.1.2.2" "2.2" "3" "3.1" "3.1.1" "3.1.2")
    '("M1" "S1" "P1" "S2" "P2" "P5" "P6" "P9" "P0" "P3" "S3" "P4" "P7" "P8")
  )
)

;; -> ((3 "S3" ((1 "P4" ((2 "P8" nil) (1 "P7" nil))))) (2 "S2" ((2 "P3" nil) (1 "P2" ((2 "P6" ((2 "P0" nil) (1 "P9" nil))) (1 "P5" nil))))) (1 "S1" ((1 "P1" nil))) (0 "M1" nil))


(Tree:Get Tree "2.1.1") ;;-> "P5"

(setq tree (Tree:Set Tree "2.1.1" "hello"))

(Tree:Get Tree "2.1.1") ;;-> "hello"

greets reltro
« Last Edit: July 28, 2013, 03:15:32 PM by reltro »

reltro

  • Guest
Re: Binary Tree Algorithm
« Reply #40 on: July 29, 2013, 05:49:20 PM »
Here is an other Version:

I found out that the double parenthesis don't make any sense in this case, so I built one without them...

Code: [Select]
(   (lambda (setter getter / ParseIndex tmp)
      (setq ParseIndex (lambda (Index / ) (read (strcat "(" (vl-string-translate "." " " (vl-princ-to-string Index)) ")"))))
     
      (list
         ;---------------
         (eval
            (list 'defun 'Tree:Get '(Tree Index / )
               (list
                  (lambda (getter ParseIndex / )
                     (setq Index (ParseIndex Index))
                     (cond
                        ((= (type Tree) 'SYM) (getter (eval Tree) Index))
                        ((getter Tree Index))
                     )
                  )
                  getter
                  ParseIndex
               )
            )
         )
         ;---------------
         (setq tmp
            (eval
               (list 'defun 'Tree:Set '(Tree Index Value / )
                  (list
                     (lambda (setter ParseIndex / )
                        (setq Index (ParseIndex Index))
                        (cond
                           ((= (type Tree) 'SYM) (set Tree (setter setter (eval Tree) Index Value)))
                           ((setter setter Tree Index Value))
                        )
                     )
                     setter
                     ParseIndex
                  )
               )
            )
         )
         ;---------------
         (eval
            (list 'defun 'Tree:Make '(IndexLst DataLst / )
               (list
                  (lambda (setter / Tree)
                     (mapcar
                        '(lambda (i d / ) (setq Tree (setter Tree i d)))
                        IndexLst
                        DataLst
                     )
                     Tree
                  )
                  tmp
               )
            )
         )
      )
   )
   ;---------------
   (lambda (setter Tree Index Value / subdata res i)
      (if   (and Tree (setq subdata (assoc (car Index) Tree)))
         (if (cdr Index)
            (vl-remove-if-not
               '(lambda (a / ) (or (cadr a) (cddr a)))
               (subst
                  (vl-list* (car subdata) (cadr subdata) (setter setter (cddr subdata) (cdr Index) Value))
                  subdata
                  Tree
               )
            )
            (if (or Value (cddr subdata))
               (subst
                  (vl-list* (car subdata) Value (cddr subdata))
                  subdata
                  Tree
               )
               (vl-remove subdata Tree)
            )
         )
         (if Value
            (cons
               (repeat (length (setq Index (reverse Index)))
                  (setq res
                     (cond
                        (i (setq i (1+ i)) (list (nth i Index) nil res))
                        ((setq i 0) (list (nth i Index) Value))
                     )
                  )
               )
               Tree
            )
            Tree
         )
      )
   )
   ;---------------
   (lambda (Tree Index / )
      (while Index
         (setq Tree
            (   (lambda (res / )
                  (if (setq Index (cdr Index))
                     (cddr res)
                     (cadr res)
                  )
               )
               (assoc (car Index) Tree)
            )
         )
      )
   )
)

I also added some other 'feature' in the "Tree:set"-Method:
If the Tree is given as a Symbol, the Routine will set the new Data for Tree directly.

(Tree:set 'MyTree "1.2.3" "hello")
OR
(setq MyTree (Tree:set MyTree "1.2.3" "helloWorld")

Greets

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #41 on: July 30, 2013, 03:09:29 AM »
Just as an extra over, here's the traverse-breadth-first:
Code - Auto/Visual Lisp: [Select]
  1. (defun enqueue (source item)
  2.   (set source (cons item (eval source)))
  3.   item)
  4.  
  5. (defun dequeue (source / item)
  6.   (setq item (car (set source (reverse (eval source)))))
  7.   (set source (reverse (cdr (eval source))))
  8.   item)
  9.  
  10. (defun Tree:Breadth-First-Traverse (tree visit / queue node)
  11.   (enqueue 'queue tree)
  12.   (while queue
  13.     (apply visit (list (Tree:GetValue (setq node (dequeue 'queue)))))
  14.     (foreach item (cdr node) (enqueue 'queue item))))
I'm using the algorithm from here: http://en.wikipedia.org/wiki/Tree_traversal#Breadth-first_2

Thus the queue data structure as a helper.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #42 on: July 31, 2013, 04:16:12 AM »
@Irneb,

I'm back again after trying for learn your code. Actually your code is very hard for understood  :-D.

I have try for parse the text index become
Code: [Select]
((0) (1) (2) (3) (3 1) (3 2) (3 3))With this one :

Code: [Select]
(setq testData '("M-001" "P-001" "P-002" "SU-001" "P-001" "P-002" "P-003")
      testIndex '("0" "1" "2" "3" "3.1" "3.2" "3.3"))
(setq i 0)
(setq index nil)
(repeat (length testIndex)
  (setq TempIndex (read (strcat "("(vl-string-translate "." " " (nth i testIndex))")")))
  (setq index (cons TempIndex index))
  (setq i (1+ i))
  )
(setq ParseIndex (reverse index))

and then I'm try for breakdown this function :

Code: [Select]
(defun Tree:SetValueAtIndex (tree index value / doSet)
  (defun doSet (tree index / tmp)
    (cond ((or (not index) (= index 0)) (cons value (cdr tree)))
          ((atom index)
           (repeat index (setq tmp (cons (car tree) tmp) tree (cdr tree)))
           (append (reverse tmp) (list (doSet (car tree) nil)) (cdr tree)))
          ((= (length index) 1) (doSet tree (car index)))
          (t
           (repeat (car index) (setq tmp (cons (car tree) tmp) tree (cdr tree)))
           (append (reverse tmp) (list (doSet (car tree) (cdr index))) (cdr tree)))))
  (doSet tree index))

I can't understand how to fill variable tree & index the code above.
Can you explain me please  :-)
 

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Binary Tree Algorithm
« Reply #43 on: July 31, 2013, 05:18:48 AM »
@udaaf,
Start with a shorter list and step through the code in the debugger in the VLIDE.
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #44 on: July 31, 2013, 06:33:26 AM »
@Kerry,

Thanks for your suggestion.
I had try with shorter list and debugging in VLIDE. But still can't understand Irneb code. Especially for function Tree:SetValueAtIndex and doSet. Where this function get variable for tree + index + value.
So that's why I try create new code for understand the logic. 

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Binary Tree Algorithm
« Reply #45 on: July 31, 2013, 08:11:01 AM »
That SetValueAtIndex basically rebuilds the entire tree recursively, checking if the current index is as specified by the index argument. See if you understand it better if I over-comment it:
Code - Auto/Visual Lisp: [Select]
  1. (defun Tree:SetValueAtIndex (tree index value / doSet)
  2.   (defun doSet (tree index / tmp) ;Define the helper function as a nested function so it doesn't interfere with name clashes
  3.     (cond ((or (not index) (= index 0)) (cons value (cdr tree))) ;If the index arg is nil or 0 this is the position where the value needs to go, so return it into the tree
  4.           ((atom index) ;If the index arg is an atom, then we're at the correct level and branch
  5.            (repeat index (setq tmp (cons (car tree) tmp) tree (cdr tree))) ;Fill the return with the tree's nodes preceding the index
  6.            (append (reverse tmp) (list (doSet (car tree) nil)) (cdr tree))) ;Join the preceding, new value and following nodes of the tree, and return it
  7.           ((= (length index) 1) (doSet tree (car index))) ;If the index is only 1 number, call this function with only the number, not the list
  8.           (t ;Else (index consists of 2 or more levels)
  9.            (repeat (car index) (setq tmp (cons (car tree) tmp) tree (cdr tree))) ;Fill the return with the tree's nodes preceding the index
  10.            (append (reverse tmp) (list (doSet (car tree) (cdr index))) (cdr tree))))) ;Join the preceding, new value and following nodes of the tree, and return it
  11.                                                                                       ;The new value for the node is generated recursively, by removing the highest level of the index
  12.                                                                                       ;then calling this same function with the node of the tree as if it's a tree on its own
  13.   (doSet tree index)) ;Call the helper function and return whatever it returns.
The doSet is calling itself for each level it runs through the index. Most of the work is done in the Else portion of the cond structure.
  • It copies the nodes before the current level's index argument to the returned variable
  • It then calculates the new node by calling itself with only the node at that index and the rest of the index's levels
  • Then it appends the values obtained from the previous 2 and the rest of the current portion of the tree.
I could've done it all without a nested helper function, but since the value argument never changes - it's not necessary to send for each recursion. Thus it's an attempt to make it a bit more optimal: AutoLisp copies each argument to the instance of the new function every time it's called.

The 1st option in the cond structure could actually be omitted. Since the repeat would not run, and the append would not include a nil into the result. It's only there for some optimization.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

udaaf

  • Guest
Re: Binary Tree Algorithm
« Reply #46 on: July 31, 2013, 08:50:33 PM »
@Irneb,

Once again many thanks for your explanation  :-).
I'll learn.