in cây nhị phân ở cạnh của nó

Question

Làm thế nào bạn có thể in một cây nhị phân ở bên cạnh để kết quả trông như thế này?

__/a 
__/ \b 
    \ _/c 
    \_/ \d 
    \e 

_{(đẹp ascii-nghệ thuật chào đón)}

Dưới đây là một số mã mà không thực hiện khá công việc:

def print_tree(tree): 
    def emit(node,prefix): 
     if "sequence" in node: 
      print "%s%s"%(prefix[:-1],node["name"]) 
     else: 
      emit(node["left"],"%s_/ "%prefix.replace("/ "," /")[:-1].replace("_"," ")) 
      emit(node["right"],"%s \\ "%prefix.replace("\\ "," \\")[:-1]) 
    emit(tree,"")  

Những kết quả đầu ra này:

 _/hg19 
    _/ \rheMac2 
    _/ \mm9 
    /\_/bosTau4 
/\_/canFam2 
_/  \pteVam1 
\_/loxAfr3 
    \dasNov2 

Scope creep: nó sẽ là e xcellent nếu bạn có thể vượt qua trong một hàm sẽ trả về chuỗi để in của bất kỳ nút nào; theo cách này, đôi khi tôi cũng có thể in thông tin về các nút không rời. Vì vậy, cho dù một nút có bất cứ điều gì để in được kiểm soát bởi các chức năng thông qua trong như là một tham số.

Dưới đây là một số bài kiểm tra dữ liệu trong JSON:

{ 
    "left": { 
     "left": { 
      "left": { 
       "left": { 
        "name": "hg19", 
        "sequence": 0 
       }, 
       "right": { 
        "name": "rheMac2", 
        "sequence": 1 
       } 
      }, 
      "right": { 
       "name": "mm9", 
       "sequence": 2 
      } 
     }, 
     "right": { 
      "left": { 
       "name": "bosTau4", 
       "sequence": 3 
      }, 
      "right": { 
       "left": { 
        "name": "canFam2", 
        "sequence": 4 
       }, 
       "right": { 
        "name": "pteVam1", 
        "sequence": 5 
       } 
      } 
     } 
    }, 
    "right": { 
     "left": { 
      "name": "loxAfr3", 
      "sequence": 6 
     }, 
     "right": { 
      "name": "dasNov2", 
      "sequence": 7 
     } 
    } 
} 

Answer 1

Dưới đây là một số mã mà thực hiện, phương pháp đệ quy chung được mô tả ở những nơi khác. Biểu diễn bên trong của cây là một chuỗi (lá) hoặc một cặp (cặp) của các nút con. Biểu diễn bên trong của "đoạn" trung gian của một nút là số (above, below, lines), trong đó above và below là số dòng trên và dưới gốc và lines là một trình lặp trên mỗi dòng một phần (không có dấu cách ở bên trái).

#!/usr/local/bin/python3.3 

from itertools import chain 
from random import randint 


def leaf(t): 
    return isinstance(t, str) 

def random(n): 
    def extend(t): 
     if leaf(t): 
      return (t+'l', t+'r') 
     else: 
      l, r = t 
      if randint(0, 1): return (l, extend(r)) 
      else: return (extend(l), r) 
    t = '' 
    for _ in range(n-1): t = extend(t) 
    return t 

def format(t): 
    def pad(prefix, spaces, previous): 
     return prefix + (' ' * spaces) + previous 
    def merge(l, r): 
     l_above, l_below, l_lines = l 
     r_above, r_below, r_lines = r 
     gap = r_below + l_above 
     gap_above = l_above 
     gap_below = gap - gap_above 
     def lines(): 
      for (i, line) in enumerate(chain(r_lines, l_lines)): 
       if i < r_above: 
        yield ' ' + line 
       elif i - r_above < gap_above: 
        dash = '_' if i - r_above == gap_above - 1 else ' ' 
        if i < r_above + r_below: 
         yield pad(dash + '/', 2 * (i - r_above), line) 
        else: 
         yield pad(dash + '/', 2 * gap_below - 1, line) 
       elif i - r_above - gap_above < gap_below: 
        if i < r_above + r_below: 
         yield pad(' \\', 2 * gap_above - 1, line) 
        else: 
         spaces = 2 * (r_above + gap_above + gap_below - i - 1) 
         yield pad(' \\', spaces, line) 
       else: 
        yield ' ' + line 
     return (r_above + gap_above, gap_below + l_below, lines()) 
    def descend(left, t): 
     if leaf(t): 
      if left: 
       return (1, 0, [t]) 
      else: 
       return (0, 1, [t]) 
     else: 
      l, r = t 
      return merge(descend(True, l), descend(False, r)) 
    def flatten(t): 
     above, below, lines = t 
     for (i, line) in enumerate(lines): 
      if i < above: yield (' ' * (above - i - 1)) + line 
      else: yield (' ' * (i - above)) + line 
    return '\n'.join(flatten(descend(True, t))) 


if __name__ == '__main__': 
    for n in range(1,20,3): 
     tree = random(n) 
     print(format(tree)) 

Dưới đây là một số ví dụ đầu ra:

  _/rrrr 
     _/ \_/rrrlr 
    /\ \rrrll 
    _/ \_/rrlr 
    /\  \rrll 
/ \ _/rlrr 
/ \_/ \rlrl 
_/  \_/rllr 
\   \_/rlllr 
    \   \rllll 
    \  _/lrrr 
    \  _/ \lrrl 
    \ /\_/lrlr 
     \_/ \lrll 
     \ _/llrr 
     \_/ \llrl 
      \_/lllr 
      \_/llllr 
       \lllll 

Và một chút bất đối xứng hơn một cho thấy, có lẽ, tại sao tôi không dòng pad với không gian sang trái cho đến khi kết thúc (qua flatten). Nếu nửa dưới đã được đệm ở bên trái một số cánh tay trên sẽ vượt qua khu vực đệm.

   _/rrrrr 
      _/ \rrrrl 
      _/ \rrrl 
     _/ \_/rrlr 
     /\ \rrll 
    / \_/rlr 
    / \rll 
    /  /lrrr 
    /  _/ _/lrrlrr 
/ /\_/ \lrrlrl 
/ / \lrrll 
_/  _/  _/lrlrrr 
\ /\ _/ \lrlrrl 
    \ / \_/ \lrlrl 
    \_/  \lrll 
    \  _/llrrr 
     \ _/ \llrrl 
     \_/ \llrl 
     \lll 

Đó là thuật toán đệ quy "rõ ràng" - ma quỷ nằm trong chi tiết. Nó dễ nhất để viết mà không có "_", khiến cho logic trở nên phức tạp hơn một chút.

Có lẽ chỉ có "cái nhìn sâu sắc" là gap_above = l_above - đó là nói rằng "cánh tay phải" có chiều dài bên phải của cây con trái (bạn sẽ cần đọc vài lần). Nó làm cho mọi thứ tương đối cân bằng. Xem ví dụ bất đối xứng ở trên.

Cách hiểu biết chi tiết hơn là sửa đổi quy trình pad để lấy ký tự thay vì ' ' và cung cấp một ký tự khác cho mỗi cuộc gọi. Sau đó, bạn có thể thấy chính xác logic nào tạo ra không gian nào. Đây là những gì bạn nhận được bằng A. B, C và D cho các cuộc gọi đến pad từ trên xuống dưới, ở trên (rõ ràng là không có nhân vật khi dung lượng là zero):

   _/rrrr 
      /\rrrl 
      _/B _/rrlrr 
     /\_/ \rrlrl 
     /AA \rrll 
     _/BBB _/rlrrr 
    /\DD _/ \rlrrl 
    /AA \_/ \_/rlrlr 
    /AAAA \C \rlrll 
    /AAAAAA \_/rllr 
_/AAAAAAAA \rlll 
\DDDDDDDD _/lrrrr 
    \DDDDDD _/ \lrrrl 
    \DDDD/\lrrl 
    \DD _/B _/lrlrr 
    \_/ \_/ \lrlrl 
     \C \lrll 
     \_/llr 
      \lll 

Có nhiều lời giải thích here (mặc dù cây rất khác nhau).

Answer 2

Thực hiện một cấu trúc đại diện, liên quan đến một mảng chuỗi và một số dòng của "cánh hoa".

đại diện (lá) là [0, repr (lá giá trị)]

đại diện (nonleaf), được đưa ra top = nonleaf.left và bottom = nonleaf.right:

Pad mỗi dòng của đại diện (trên cùng) với không gian nếu trên cánh hoa hàng đầu của hoặc với dấu gạch chéo ở vị trí thích hợp nếu bên dưới. Tương tự như vậy, pad mỗi dòng của đại diện (dưới cùng) với khoảng trống nếu dưới cánh hoa dưới cùng, hoặc với dấu gạch chéo ngược ở một vị trí thích hợp nếu ở trên. repr (nonleaf) sau đó là [chiều cao của các hàng trên cùng, các dòng đệm phía trên cùng theo sau là các dòng đệm phía dưới].

Ví dụ:

rep(a): [0, ["a"]] 
rep(b): [0, ["b"]] 
rep(ab): [1, ["/"+"a", "\"+"b"]] 
rep(c): [0, ["c"]] 
rep(d): [0, ["d"]] 
rep(cd): [1, ["/"+"c", "\"+"d"]] 
rep(e): [0, ["e"]] 
rep(cde): [2, [" "+"/c", "/" + "\d", "\" + "e"]] 
rep(abcde): [2, [" "+"/a", "/"+"\b", "\ "+" /c", " \" + "/\d", " " + "\e"]] 

Lưu ý rằng trong trường hợp đầu, chiều rộng của đệm là số dòng bên dưới cánh hoa; trong trường hợp đáy, chiều rộng của padding tương ứng với cánh hoa. Vì vậy, trong (abcde) trường hợp, đầu có 2 dòng và cánh hoa 1, vì vậy đệm là (2 - 1 == 1) một nhân vật; phía dưới có cánh hoa 2, vì vậy đệm là 2 ký tự.

Nếu bạn muốn, bạn cũng có thể thêm dấu "_" vào mỗi dòng trống tại dòng thứ (cánh hoa-1) (và khoảng trắng thừa cho tất cả các dòng khác).

Rõ ràng, không có mã nào trong số này là mã ("\" là lỗi cú pháp đang chờ xảy ra), nhưng không quá khó để thực hiện từ đây.

Answer 3

Bạn cần phải tiếp cận theo cách đệ quy và theo dõi kích thước của các phụ đề riêng lẻ. Đặc biệt, nơi gốc là. Một cây không cân bằng có thể dễ dàng trông như thế này:

/ 
\/ 
\/ 
    \/ 
    \ 

Bây giờ xem xét bạn đã đã xây dựng được cây này, những gì bạn cần phải chuyển đổi này như sau khi thêm mức phụ huynh.

/
/\/ 
/\/ 
\ \/ 
\ \ 
    \ 

Ý tưởng chính là bắt đầu với lá. Họ là tầm thường. Sau đó, xác định một cách để tổng hợp hai subtrees, cho họ có một số lượng khác nhau của dòng và một vị trí khác nhau của nút gốc subtree.

Answer 4

Đây là một cây ngang thoải mái mà chỉ giúp tôi trong gỡ lỗi một dự án: http://www.acooke.org/cute/ASCIIDispl0.html

Kết quả tương tự như cách bố trí thư mục của các plugin VIM NERDtree nếu bạn đã nhìn thấy đó.

Đây là tôi lại thực hiện như một phương pháp __str__ trong một cây nhị phân:

def __str__(self): 
    """Recursive __str__ method of an isomorphic node.""" 
    # Keep a list of lines 
    lines = list() 
    lines.append(self.name) 
    # Get left and right sub-trees 
    l = str(self.left).split('\n') 
    r = str(self.right).split('\n') 
    # Append first left, then right trees 
    for branch in l, r: 
     # Suppress Pipe on right branch 
     alt = '| ' if branch is l else ' ' 
     for line in branch: 
      # Special prefix for first line (child) 
      prefix = '+-' if line is branch[0] else alt 
      lines.append(prefix + line) 
    # Collapse lines 
    return '\n'.join(lines)