c-----------------------------------------------------------
c Chapter 28: Labeled Trees(p267)
c-----------------------------------------------------------
c   Name of subroutine: LBLTRE
c
c   Algorithm:Produce the edge list of a tree from its
c             Prufer codeword.
c
c   input:    
c   complier: f77 lbltre_2.f
c-----------------------------------------------------------

        parameter(n=4)
        integer TREE(n),A(n)
        write(*,10)
10      format('Input the Prufer codeword A(1),A(2):')
        read(5,*) A(1),A(2)

        call lbltre(N,A,TREE)
        write(*,20)
20      format('The output tree array is: ')
        write(*,30),A(1),A(2), (TREE(i),i=1,3)
30      format(1x,i2,i2,3x,3(i2))
        stop
        end

c-----Subroutine begins here--------------------------------

	SUBROUTINE LBLTRE(N, A, TREE)
	INTEGER A(N), TREE(N), R
10	DO 11 I=1,N
11 	TREE(I)=0
	NM2=N-2
	DO 12 I=1, NM2
	L=A(N-1-I)
	IF (TREE(L).EQ.0) A(N-1-I)=-L
12	TREE(L)=-1
	K=1
	A(N-1)=N
	J=0
20	IF(TREE(K).EQ.0) GO TO 25
	K=K+1
	GO TO 20
25	KP=K
30	J=J+1
	R=IABS(A(J))
	TREE(KP)=R
	IF (J.EQ.N-1) GO TO 40
32	IF (A(J).GT.0) GO TO 20
	IF (R.GT.K) GO TO 35
	KP=R
	GO TO 30
35	TREE(R)=0
	GO TO 20
40	DO 41 I=1,NM2
41	A(I)=IABS(A(I))
	RETURN
	END