Topic: Binary Tree Algorithm

[udaaf]

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

;Result
(1    2    4    5    7    9)
(12    3    11   6   8   10)
;OR
((1 12) (2 3) (4 11) (5 6) (7 (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]

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.

[Kerry]

Perhaps something like this :

[irneb]

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.

[Kerry]

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.

[Kerry]

<..>

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.

[irneb]

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)

[irneb]

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)

[Kerry]

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` ?

[irneb]

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.

[udaaf]

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]

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,

[udaaf]

Kelly,

Please find attached file.

Thanks,

Udaaf

[irneb]

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.

[irneb]

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. |;