二叉树的autolisp实现，算法

admin1

( defun c:xx()
  ( setq aaa '( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ) )           ;;满二叉树
  ( setq bbb '( 2 13 55 46 37 8 19 10 15 12 113 14 22 23 25 ) )  ;;满二叉树
  ( setq bbb '( 2 13 55 46 37 8 19 10 15 12 113 14  ) )          ;;不是满二叉树
  ;( setq aaa '( 0 1 2 3 4 5 6 ) )
  ( setq abc ( BinaryTree 0 aaa ) )
  ( princ abc )
  ;( istree abc )
  ;( setq abc ( BinaryTree 0 bbb ) )
  ;( PreOrder abc )   ;先序遍历
  ;( Inorder abc )    ;中序遍历
  ( Postorder abc )  ;后序遍历
)

;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名  : BinaryTree ********************************************************
;;;说  明  : 仅适用于顺序存储转满二叉树的形式***********************************
;;;功  能  : 顺序存储转二叉树***************************************************
;;;参  数  : i 二叉树深度*******************************************************
;;;参  数  : datalist 顺序存储表************************************************
;;;返回值  : 二叉树格式*********************************************************
;;;例  子  : ( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 )顺序表***********************
;;;输  出  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14))) 输出二叉树格式****
( defun BinaryTree ( i datalist / left mid n right )
  ( setq mid nil )
  ( setq left nil )
  ( setq right nil )
  ( setq n ( length datalist ) )
  (  cond ( ( <= i ( - ( / ( - n 1 ) 2 ) 1 ) )
           ( progn           
            ( setq mid ( nth i datalist )   
                            left ( BinaryTree ( + ( * 2 i ) 1 ) datalist )
                             right ( BinaryTree ( + ( * 2 i ) 2 ) datalist )
                     )
             ( list mid left right )
           )           
                   )
         ( ( and ( > i ( - ( / ( - n 1 ) 2 ) 1 ) )
                 ( < i n ) )
           ( setq mid ( nth i datalist ) )            
         )
         ( t nil )
  )
)
;;;*****************************************************************************
;;;*****************************************************************************


;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名  : istree ************************************************************
;;;说  明  : 判断表数据是否符合满二叉树的格式***********************************
;;;参  数  : i 二叉树深度*******************************************************
;;;参  数  : datalist 顺序存储表************************************************
;;;返回值  : 二叉树格式*********************************************************
;;;例  子  : (istree (a (b nil nil) nil)) 二叉树格式****************************
;;;输  出  : T 输出真值*********************************************************
;;;例  子  : (istree (a (b nil nil))) 非二叉树格式******************************
;;;输  出  : NIL 输出假值*******************************************************
( defun istree ( treelist / left right root )
    ( if ( or ( eq nil treelist ) ( null treelist ) )  ;empty is a tree
         t
         ( if ( = ( length treelist ) 3 )               
              ( progn
                ( setq  root  ( atom ( car treelist ) ) )
                ( setq  left  ( istree ( cadr treelist ) ) )
                ( setq  right ( istree ( caddr treelist ) ) )
                ( and   root left right )                 
              )
              nil
         )   
    )      
)
;;;*****************************************************************************
;;;*****************************************************************************



;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名  : PreOrder **********************************************************
;;;说  明  : 满二叉树的先序遍历*************************************************
;;;参  数  : treedata 二叉树格式************************************************
;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
;;;输  出  : 0 1 3 7 8 4 9 10 2 5 11 12 6 13 14 先序遍历输出********************
( defun PreOrder ( treedata )
  ( if ( not ( atom treedata ) )
    ( progn
        ( princ "\n" )
        ( if ( atom ( car treedata ) )
             ( princ ( car treedata ) )
        )
        ( princ "\n" )
        ( if ( atom ( cadr treedata ) )
             ( princ ( cadr treedata ) )
        )
        ( princ "\n" )
        ( if ( atom ( caddr treedata ) )
             ( princ ( caddr treedata ) )
        )
        ( princ "\n" )
        ( PreOrder ( cadr treedata ) )
        ( PreOrder ( caddr treedata ) )
    )
  )
)
;;;*****************************************************************************
;;;*****************************************************************************



;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名  : Inorder ***********************************************************
;;;说  明  : 满二叉树的中序遍历*************************************************
;;;参  数  : treedata 二叉树格式************************************************
;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
;;;输  出  : 7 3 8 1 9 4 10 0 11 5 12 2 13 6 14 中序遍历输出********************
( defun Inorder ( treedata )
  ( if ( not ( atom treedata ) )
    ( progn
        ( Inorder ( cadr treedata ) )
        ( princ "\n" )
        ( if ( atom ( cadr treedata ) )
             ( princ ( cadr treedata ) )
        )
        ( princ "\n" )
        ( if ( atom ( car treedata ) )
             ( princ ( car treedata ) )
        )
        ( princ "\n" )
        ( if ( atom ( caddr treedata ) )
             ( princ ( caddr treedata ) )
        )
        ( princ "\n" )
        ( Inorder ( caddr treedata ) )
    )
  )
)
;;;*****************************************************************************
;;;*****************************************************************************



;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名  : Postorder *********************************************************
;;;说  明  : 满二叉树的后序遍历*************************************************
;;;参  数  : treedata 二叉树格式************************************************
;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
;;;输  出  : 7 8 3 9 10 4 1 11 12 5 13 14 6 2 0 后序遍历输出********************
( defun Postorder ( treedata )
  ( if ( not ( atom treedata ) )
    ( progn
        ( Postorder ( cadr treedata ) )
        ( Postorder ( caddr treedata ) )
      
        ( princ "\n" )
        ( if ( atom ( cadr treedata ) )
             ( princ ( cadr treedata ) )
        )
        ( princ "\n" )
        ( if ( atom ( caddr treedata ) )
             ( princ ( caddr treedata ) )
        )
        ( princ "\n" )
        ( if ( atom ( car treedata ) )
             ( princ ( car treedata ) )
        )
        ( princ "\n" )
    )
  )
)
;;;*****************************************************************************
;;;*****************************************************************************



;;;*****************************************************************************
;;;*****************************************************************************
;;;函数名  : PreOrder2 *********************************************************
;;;说  明  : 满二叉树的先序遍历*************************************************
;;;参  数  : treedata 二叉树格式************************************************
;;;例  子  : (0 (1 (3 7 8) (4 9 10)) (2 (5 11 12) (6 13 14)))*******************
;;;输  出  : 0 1 3 7 8 4 9 10 2 5 11 12 6 13 14 先序遍历输出********************
( defun PreOrder2 ( treedata )
  ( if ( not ( atom treedata ) )
    ( progn
        ( princ "\n" )
        ( if ( atom ( car treedata ) )
             ( princ ( car treedata ) )
        )
        ( princ "\n" )
        ( if ( atom ( cadr treedata ) )
             ( princ ( cadr treedata ) )
        )
        ( princ "\n" )
        ( if ( atom ( caddr treedata ) )
             ( princ ( caddr treedata ) )
        )
        ( princ "\n" )
        ( PreOrder2 ( cadr treedata ) )
        ( PreOrder2 ( caddr treedata ) )
    )
  )
)
;;;*****************************************************************************
;;;*****************************************************************************