C         A. Colin Day, "Balancing a Binary Tree", COMPUTER JOURNAL
C         Vol. 19 (1976), pp. 360-61.
C
      SUBROUTINE BALNCE(ILPT,IRPT,N,IROOT)
C
C         BALANCES A TREE OF N ITEMS.
C            ILPT(N) - LEFT POINTERS
C            IRPT(N) - RIGHT POINTERS
C            IROOT - ROOT OF TREE (CHANGED BY SUBROUTINE)
C
      DIMENSION ILPT(N), IRPT(N)
C
C         STRIP ITEMS FROM TREE AS LIST
C         tjr:  in-order traversal of a threaded binary tree
C
      IF ( N .LE. 1) RETURN
      ISTRT = 0
      J = IROOT
      GO TO 20
C FOLLOW LEFT POINTERS
   10 J = ILPT(J)
   20 IF (ILPT(J) .GT. 0) GO TO 10
C THIS ITEM IS TO BE STRIPPED
      IF (ISTRT .GT. 0) GO TO 30
C FIRST ITEM - KEEP TRACK OF START
      ISTRT = J
      GO TO 40
C NOT FIRST - CHAIN TOGETHER
   30 IRPT(LAST) = J
   40 ILPT(J) = 0
      LAST = J
C TEST FOR BACKTRACK, END OR RIGHT BRANCH
      J = IRPT(J)
      IF (J) 50, 60, 20
C BACKTRACK   tjr note:  threaded binary tree representation
   50 J = -J
      GO TO 30
C
C         FORM BALANCED TREE
C
C SET LENGTH OF BACKBONE
   60 NBACK = N - 1
C FIND NO. OF TRANSFORMATION
   70 M = NBACK / 2
      IF ( M .LE. 0 ) RETURN
C INITIALISE FOR LOOP
      J = IROOT
      L = J
C MOVE ON ROOT IN ANTICIPATION
      IROOT = IRPT(IROOT)
C PERFORM TRANSFORMATIONS
      DO 80 I = 1, N
      K = IRPT(J)
      IRPT(L) = K
      IRPT(J) = ILPT(K)
      ILPT(K) = J
      L = K
   80 J = IRPT(K)
C AMEND LENGTH OF BACKBONE
      NBACK = NBACK - M - 1
      GO TO 70
      END