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