Converting a List into a Binary tree

[stanovb]

I am reading a book about common lisp and its talking about binary tree data structures. They give a list of (A B (C D) E) and they also give a graphical representation of it. I believe each box is either the CAR or the CDR of the cons cell. The terminal nodes of the tree are the atoms A, B, C, D, E, and NIL. The nonterminal nodes are the cons cells. 

They say  "To view this diagram as a binary tree instead of a list, turn the page 45 degrees clockwise". I am having a little trouble visualizing what that would look like and I could use some help as to what the binary tree would look like. Its a very good book in my opinion. but just saying to turn it 45 degrees clockwise is not helping me visualize this.

[paullimapa]

since autolisp does not support binary trees there's no builtin function to do this.

but there's a way using a different programming language:

python - How to convert a flat list to a binary tree - Stack Overflow

[_gile]

Hi,

The only AutoLISP data structure is a 'linked list' which can be seen as a binary tree where each 'cons cell' is a 'tree node', left 'leaves' are atoms and right 'leaves' are nil.

[stanovb]

Thanks. That might actually be it. The book told me to turn it at an angle, but that wasnt helping me

[_gile]

'(A B (C D) E)

is a shortcut for:

(cons 'A (cons 'B (cons (cons 'C (cons 'D ())) (cons 'E ())))) 

which can be written using 'dotted pair notation':

'(A . (B . ((C . (D . ())) . (E . ()))))

 which can be seen as a binary tree:

[stanovb]

 I did find a video on what I guess is common lisp

https://www.youtube.com/watch?v=D4UA5pcGx58

The guy said in the video that if for instance if you have a list of numbers, the lesser number goes to the left and the greater number goes to the right

[_gile]

The example in the video is a "binary search tree".

We can emulate this kind of tree by using nested lists.

For example, a tree can be a list which first item is a number (tree node), second item is the left child tree (a sublist) and the the third item is the right child tree (another sublist).

(defun list2tree (lst / insert tree)
  (defun insert	(ele tree)
    (cond
      ((null tree) (list ele nil nil))
      ((< ele (car tree))
       (list (car tree) (insert ele (cadr tree)) (caddr tree))
      )
      (T
       (list (car tree) (cadr tree) (insert ele (caddr tree)))
      )
    )
  )
  (foreach x lst (setq tree (insert x tree)))
)

Example:

_$ (list2tree '(6 1 8 5 3 4 9 2 7))
(6 (1 nil (5 (3 (2 nil nil) (4 nil nil)) nil)) (8 (7 nil nil) (9 nil nil)))

We can define a 'traversal' function to get the tree leaves from the lower to the greater item.

(defun traversal (tree)
  (append
    (if	(cadr tree)
      (traversal (cadr tree))
    )
    (list (car tree))
    (if	(caddr tree)
      (traversal (caddr tree))
    )
  )
)

This could be used to sort a list:

_$ (traversal (list2tree '(6 1 8 5 3 4 9 2 7)))
(1 2 3 4 5 6 7 8 9)

[stanovb]

I guess that's sort of what they meant about turning it an an angle