;;; This is a hard problem. One way to think about it: you need an
;;; auxiliary functions for constructing cbt with arbitrary start
;;; label at root. Then you need to know the number of nodes in left
;;; and right subtrees.
;;; A table for that comes handy:
;;; N / left size / p
;;; 1 / 0 /
;;; 2 / 1 / 1
;;; 3 / 1 / 1
;;; 4 / 2 / 2
;;; 5 / 3 / 2
;;; 6 / 3 / 2
;;; 7 / 3 / 2
;;; 8 / 4 / 4
;;; 9 / 5 / 4
;;; 10 / 6 / 4
;;; 11 / 7 / 4
;;; 12 / 7 / 4
;;; 13 / 7 / 4
;;; 14 / 7 / 4
;;; 15 / 7 / 4
;;; 16 / 8 / 8
;;;
;;; Ok, except for the base N = 1, one can see that the left size
;;; depends essentially on the 2 higher-order bits (HOB) of N: if
;;; these two higer-order bits are "10", then left size keeps growing
;;; form a power of 2 by 1 unit; if the HOB are "11", then left size
;;; is constant, equal t the last value from the "10" series.
;;;
;;; These two HOB are just N div p, where p is the value in the third
;;; colimn; and what needs to be added to form the left size in the
;;; "10" case is p + lower order bits, which is p + N mod p. In the
;;; "11" case, this just gets to be p + (p-1).
;;;
;;; The starting label for subtrees is just 2k and 2k+1, if k is the
;;; starting label for the tree.
(defun complete-binary-tree (n)
(cbt-label n 1)
)
;;; cbt-label: complete binary tree with given label k at root;
;;; notice we also need an extra base case for n = 0.
(defun cbt-label (n k)
(cond
((= n 0) nil)
((= n 1) (list k nil nil))
(t (let* ((p (floor (highest-2-power n) 2))
(left (if (= 2 (floor n p))
(+ p (mod n p))
(+ p (1- p)))))
(list k
(cbt-label left (* 2 k))
(cbt-label (- n 1 left) (+ 1 (* 2 k)))
)))
)
)
;;; highest-2-poer: that is less that or equal to n
(defun highest-2-power (n)
(if (<= n 1)
1
(* 2 (highest-2-power (floor n 2)))
)
)