SO에 대한 최근의 질문에서 영감을 얻은 …
다음 형식으로 이진 트리를 인쇄하는 함수를 작성하십시오.
3
/ \
1 5
\ / \
2 4 6
- (A)의 뒤에 노드 라인의 라인 구성되어야 출력,
/과\등의 노드 라인을 다음의 관계를 나타내는 문자, - 모든 노드가 단일 문자로 표현 가능하다고 가정 할 수 있습니다.
- 가장 낮은 레벨의 인접 노드는 최소한 하나의 공간으로 분리해야하며, 추가 노드는 적절하게 분리해야합니다.
- 두 자녀가있는 노드는 직계 자녀의 중간에 정확하게 배치해야합니다.
- 관계 슬래시는 부모와 해당 자식 사이의 중간에 있어야합니다 (원하는 방식).
입력:
입력은 함수에 대한 인수로 제공됩니다. 트리의 정확한 구조를 지정하지는 않지만 실제 이진 트리로 사용할 수 있어야합니다. “트리는 프로그램에서 우연히 예상 된 출력처럼 보이는 문자열로 프로그램에 표시됩니다”.
출력 스트림으로 인쇄하거나 원하는 출력을 포함하는 문자열을 반환 할 수 있습니다.
가장 짧은 코드에 대한 요점이지만 90 % 작동하는 짧은 것보다 완전히 작동하는 긴 솔루션을 선호합니다.
현상금 업데이트 :
현상금을 위해, 나는 (최적화 자) 약간의 변경을하고 있습니다 :
- STDIN, ARGV 또는 함수 인수에서 입력 할 수 있습니다.
- 출력은 STDOUT에 있어야합니다 (또는
console.logJS의 경우). - 예를 들어 입력이 배열 형식이라고 가정 할 수 있습니다.
[1,2,3]또는[1 2 3]
업데이트 2- 이진 트리는 실제로 이진 검색 트리 여야합니다. 처음에는 이것을 언급하지 않았으므로 사용자는 일반 배열을 이진 검색 트리 배열로 변환하는 것을 별도의 프로그램으로 취급하고 최종 바이트 수는 프로그램이 배열을 인수로 가져 와서 인쇄하는 것입니다. 이진 트리처럼.
답변
포트란 77-1085 자
subroutine q(u,t)
implicit integer(i-z)
character*33 f,g
dimension t(u)
m=ceiling(log(real(u))/log(2.))
v=2**(m+1)-1
do l=1,m
n=2**(l-1)
k=2**(m-l+2)-3
w=(3+k)*2**(l-1)-k
p=1+(v-w)/2
if(l.ne.1)then
write(f,'(A,I3,A)')'(A',p,',$)'
print f,' '
write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
do j=2**(l-1),2**l-1
if(t(j/2).lt.0.or.t(j).lt.0)then
print f,' ',' '
elseif(mod(j,2).eq.0)then
print f,' /',' '
else
print f,' \ ',' '
endif
enddo
print*
endif
write(f,'(A,I3,A)')'(A',p,',$)'
print f,' '
write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
write(g,'(A2,I3,A3)')'(A',k+3,',$)'
do j=2**(l-1),2**l-1
if(t(j).ge.0)then
print f,t(j),' '
else
print g,' '
endif
enddo
print*
enddo
end
트리는 t일반적인 방식으로 입력 배열 에 루트 1에서 루트-> 2에서 왼쪽, 루트-> 3에서 루트-> 왼쪽-> 4에서 왼쪽으로 표시됩니다.
출력은 최대 5 단계 깊이의 일반 터미널에 맞아야합니다.
각 노드 쌍 사이에 정확히 하나의 슬래시를 사용합니다. 4 개 이상의 레벨이 있으면 상단 근처에서 꽤 어리석게 보입니다. 최대 3 자리 노드를 허용했습니다.
의견과 발사 발판이있는 전체 프로그램 :
program tree
parameter (l=8) ! How many nodes to support
dimension i(l)
c Initialize the array to all empty nodes
do j=1,l
i(j)=-1
end do
c Fill in some values
i(1)=3
i(2)=1
i(3)=5
i(5)=2
i(6)=4
i(7)=7
c i(14)=6
c i(15)=8
c Call the printing routine
call q(l,i)
stop
end
c Print an ASCII representation of the tree
c
c u the length of the array containing the tree
c t an integer array representing the tree.
c
c The array contains only non-negative values, and empty nodes are
c represented in the array with -1.
c
c The printed representation uses three characters for every node,
c and places the (back) slash equally between the two node-centers.
subroutine q(u,t)
implicit integer(i-z)
character*33 f,g
dimension t(u)
m=ceiling(log(real(u))/log(2.)) ! maximum depth of the tree
v=2**(m+1)-1 ! width needed for printing the whole tree
! Optimized from 3*2**m + 1*((2**m)-1) at
! the bottom level
do l=1,m
n=2**(l-1) ! number of nodes on this level
k=2**(m-l+2)-3 ! internode spacing
w=(3+k)*2**(l-1)-k ! width needed for printing this row
! Optimized from 3*2**l + k*((2**l)-1) at
! the bottom level
p=1+(v-w)/2 ! padding for this row
c Print the connecting lines associated with the previous level
if(l.ne.1)then ! Write the connecting lines
write(f,'(A,I3,A)')'(A',p,',$)'
print f,' '
write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
do j=2**(l-1),2**l-1
if(t(j/2).lt.0.or.t(j).lt.0)then
print f,' ',' '
elseif(mod(j,2).eq.0)then
print f,' /',' '
else
print f,' \ ',' '
endif
enddo
print*
endif
c Print the nodes on this level
write(f,'(A,I3,A)')'(A',p,',$)'
print f,' '
write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
write(g,'(A2,I3,A3)')'(A',k+3,',$)'
do j=2**(l-1),2**l-1
if(t(j).ge.0)then
print f,t(j),' '
else
print g,' '
endif
enddo
print*
enddo
end
예제와 동등한 입력을 가진 출력 :
$ ./a.out
3
/ \
1 5
\ / \
2 4 7
답변
CJam, 100 99 바이트
q~_,2b,)2\#:Q1@{_2$<Q(S*:T*TQ2/:Q@ts[N+_0@{@1$' >{2$St2$_Q3*&2/^_4$>"\/"=t}*@)}/;U*o]o1:U$>\2*\}h];
입력은 ASCII 제어 문자가없는 문자 목록이어야합니다. 빈 노드는 공백으로 표시됩니다. 또한 정확히 2 n -1 노드를 가진 완벽한 이진 트리 여야합니다 .
예:
['6 '3 '7 '1 '4 ' '9 '0 '2 ' '5 ' ' '8 ' ]
또는 단순히 문자열을 사용하십시오.
"63714 902 5 8 "
산출:
6
/ \
3 7
/ \ \
1 4 9
/ \ \ /
0 2 5 8
설명
q~ " Read input. ";
_,2b, " Get tree height. ";
)2\#:Q " Get (displayed) tree width and save it in Q. ";
1@ " Push X=1 and rotate the input to top. ";
{ " Do: ";
_2$< " Get first X characters from the input. ";
Q(S*:T " T = (Q-1) spaces. ";
* " Separate the X characters by T. ";
TQ2/:Q@t " Put the string in the middle of T, and divide Q by 2. ";
s " Concatenate everything into a string.
This is the line of node labels. ";
[
N+ " Append a newline. ";
_ " Duplicate. ";
0@ " Push a 0 and rotate the original string to top. ";
{ " For each character: ";
@ " Rotate the duplicate to top. ";
1$' > " Test if the current character is greater than a space. ";
{ " If true: ";
2$St " Set the current character in the duplicate to space. ";
2$ " Copy the current position I (the number initialized with 0). ";
_Q3*&2/^ " Calculate I ^ ((I & (3*Q))>>1),
the position of the relationship character. ";
_4$> " Test if it is greater than the current position. ";
"\/"= " Select the relationship character. ";
t " Change the character in the duplicate. ";
}*
@) " Increment the current position. ";
}/
" The last two items are the line of relationship characters
and the tree width. ";
; " Discard the tree width. ";
U* " If it is the first line, empty the line of
relationship characters. ";
o " Output. ";
]o " Output the line of node labels. ";
1:U " Mark it not the first line. ";
$> " Remove the first X characters from the input. ";
\2*\ " Multiply X by 2. ";
}h " ...while the input is not empty. ";
]; " Discard everything in the stack. ";
변환 스크립트
[[0LL]W]
[q~{_a_:i={'0+}*}%La2*f+
_,,]z$
1$a+
{
{
1$1=1$1=>:T
{
~@0=2 3$1=t
@1@ta\+
}*
T
}g
}*
0=1=a
{
{
(M\+:M;
La[' LL]aer~
}%
_[' LL]a-
}g
];
M0+`-3<']+
문자 또는 한 자리 숫자를 허용합니다.
예 (모두 동일) :
['6 '7 '9 '3 '1 '2 '8 '4 '0 '5]
[6 7 9 3 1 2 8 4 0 5]
"6793128405"
산출:
['6 '3 '7 '1 '4 ' '9 '0 '2 ' '5 ' ' '8 ' ]
직진적인 직교 트리 구조입니다.
답변
파이썬 2, 411 바이트
import math
def g(a,o,d,l,b):
if l<0:
return
c=2*b+1
k=2*l+1
o[k]=' '*b
n=d-l
p=1 if n==0 else 3*2**n-1
o[k-1]=p/2*' '
i=0
for v in a[2**l-1:2**l*2-1]:
v=' ' if v==None else v
o[k]+=v+' '*c
m=' ' if v==' ' else '/' if i%2==0 else '\\'
o[k-1]+=m+max(1,b)*' ' if i%2==0 else m+p*' '
i+=1
g(a,o,d,l-1,c)
def f(a):
d=int(math.log(len(a),2))
o=['']*(d*2+2)
g(a,o,d,d,0)
print '\n'.join(o[1:])
참고 : 첫 번째 들여 쓰기 수준은 1 칸, 두 번째는 하나의 탭입니다.
예를 들어, 한 f문자열 또는의 목록으로 호출하십시오 None. f(['1',None,'3']). 목록은 비워 둘 수 없습니다.
이것은 현상금 규칙을 준수해야합니다.
변환기 스크립트 :
이진 트리 프린터에서 사용하는 형식으로 변환하고 배열합니다. 예:
$ python conv.py [3,5,4,6,1,2]
['3', '1', '5', None, '2', '4', '6']
–
import sys
def insert(bt, i):
if i < bt[0]:
j = 0
else:
j = 1
n = bt[1][j]
if n == [None]:
bt[1][j] = [i, [[None], [None]]]
else:
insert(bt[1][j], i)
def insert_empty(bt, i):
if i == 0:
return
if bt == [None]:
bt += [[[None], [None]]]
insert_empty(bt[1][0], i - 1)
insert_empty(bt[1][1], i - 1)
def get(l, level):
if level == 0:
if type(l) == list:
return ([], l)
else:
return ([l], [])
elif type(l) != list:
return ([], [])
res = []
left = []
for r, l in [get(i, level - 1) for i in l]:
res += r
left += l
return (res, left)
if __name__ == '__main__':
l = eval(sys.argv[1])
bt = [l[0], [[None], [None]]]
map(lambda x: insert(bt, x), l[1:])
depth = lambda l: 0 if type(l) != list else max(map(depth, l)) + 1
d = (depth(bt) + 1) / 2
insert_empty(bt, d - 1)
flat = []
left = bt
i = 0
while len(left) > 0:
f, left = get(left, 1)
flat += f
i += 1
for i in range(len(flat) - 1, -1, -1):
if flat[i] == None:
flat.pop()
else:
break
flat = map(lambda x: None if x == None else str(x), flat)
print flat
예 :
이를 실행하려면 기본 파일 이름 bt.py과 변환기 파일 이름 이 있어야합니다 conv.py.
$ python conv.py [3,5,4,6,1,2] | python -c 'import bt; bt.f(input())'
3
/ \
1 5
\ / \
2 4 6
$ python conv.py [5,4,3,7,9] | python -c 'import bt; bt.f(input())'
5
/ \
4 7
/ \
3 9
$ python conv.py [1,2,3,4,5,6] | python -c 'import bt; bt.f(input())'
1
\
2
\
3
\
4
\
5
\
6
$ python conv.py [6,5,4,3,2,1] | python -c 'import bt; bt.f(input())'
6
/
5
/
4
/
3
/
2
/
1
답변
APL, 125 자
{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)ׯ1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}
예:
{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)ׯ1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}('1' ('2' ('3' ('4' ()()) ('5' ()())) ('6' ()('7' ()())))('8' ()('9' ('0' ()())())))
답변
루비, 265 바이트
def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=2**(h-d)-1;c=2**d;if d>0;m=' '*(s+s/2)+'I'+' '*(s-s/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end
@proudhaskeller 버전, 269 바이트
def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=(z=2**(h-d))-1;c=2**d;if d>0;m=' '*(s+z/2)+'I'+' '*(s-z/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end
설명
자세한 버전 :
def p(t)
depth = Math.log(t.length, 2).floor
i = -1
j = []
(0..depth).each do |d|
s = 2 ** (depth-d)-1
c = 2 ** d
if d > 0
m = ' '*(s+s/2) + '|' + ' '*(s-s/2)
w = i
1.upto(d) { m += ' ' + m.reverse }
puts m.gsub(/\|/) { |o| t[w+=1] ? (w%2==0 ? '\\' : '/') : ' ' }
end
puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' '
end
end
예
n = nil
p([
1, 2, 3, 4, 5,
n, 7, 8, 9, 0,
1, n, n, 4, 5,
6, 7, 8, 9, 0,
1, 2, 3, n, n,
n, n, 8, 9, n,
n
])
제공합니다 :
1
/ \
2 3
/ \ \
4 5 7
/ \ / \ / \
8 9 0 1 4 5
/ \ / \ / \ / \ / \
6 7 8 9 0 1 2 3 8 9
(아직 변환 스크립트를 작성하지 않았습니다.)