안녕하세요.
이번에는 Graphviz를 사용하여 요소가 반복되는 2분의 검색 트리를 그려 보았습니다.

2분 탐색 나무는?

↓에서 보듯이 암노드보다 작은 것은 암노드의 왼쪽 아래에 배치되고, 큰 것은 오른쪽 아래에 배치된 이분수이다.
부모 노드와 같은 값을 가진 모든 노드는 가능하지만 어느 쪽에 통일적으로 배치해야 합니다.

※ 이미지는 위키백과의 2분 검색 트리 항목입니다

Graphviz란 무엇입니까?

이것은 도표를 그릴 수 있는 도구 패키지입니다.원래 DOT라는 언어로 기술했어요.
그래프viz라는 라이브러리가 있어서 이번에 사용했습니다.

코드

Graphviz에서 같은 값의 노드는 임의로 하나로 통합됩니다.
이번에도 그걸 피하는 코드를 넣었어요.
※ 추적
@shiracamus 선생의 평어에 따라 대폭 (거의 전부) 다시 썼다.거의 복제품이 됐어요...
최소 저항(?)댓글에 해설 같은 걸 넣었어요.

from graphviz import Digraph


class Node:

    def __init__(self, value, depth=0):
        self.value = value
        self.left = None
        self.right = None
        self.depth = depth

    #再帰的にすべての要素が返される。
    #if文はオブジェクトの中身が存在するならTrue,存在しないならFalseを返す
    #という仕組みがある
    def __iter__(self):
        if self.left:
            yield from self.left
        yield self
        if self.right:
            yield from self.right


class BinarySearchTree:

    def __init__(self, values):
        self.root = None
        for value in values:
            self.insert(value)

    def insert(self, value):
        parent_node = None
        #グラフ内を走査しているときの現在地を表すノード
        tmp_node = self.root
        depth = 0
        #ノードを追加する場所を探索
        while tmp_node:
            parent_node = tmp_node
            tmp_node = tmp_node.left if value < tmp_node.value else tmp_node.right
            depth += 1
        #「parent_nodeではないなら」
        #ではなく
        #「parent_nodeが存在しないなら」
        if not parent_node:
            self.root = Node(value, depth)
        else:
            if value < parent_node.value:
                parent_node.left = Node(value, depth)
            else:
                parent_node.right = Node(value, depth)

    def __iter__(self):
        #main関数の下三行でこれが呼び出されている。
        #self.rootはNodeであるので上のNodeクラスの__iter__()がこの後呼び出される
        if self.root:
            yield from self.root

    def print_text(self):
        depth = -1
        #in の後ではsortedにより第一位に深さ、第二位に値、の順に並べられたBinarySearchTreeオブジェクトを
        #リスト化している
        for node in sorted(self, key=lambda node: (node.depth, node.value)):
            if depth != node.depth:
                depth = node.depth
                #print("深さ＝{}".format{depth})と同じ。古いpythonのバージョンでは
                #以下の書き方ではエラーが出るので注意。
                print(f"深さ＝{depth}")
            print(f"\t\t{node.value}")

    def view_graph(self):
        graph = Digraph(format="png")
        #tree(BinSearchTreeクラス)がselfである。
        for node in self:
            #値が同じノードの判別のために深さを組み合わせてノードの名前を決定する
            name = f"{node.value} of {node.depth}"
             #Graphvizでノードを追加
            graph.node(name, str(node.value))
            if node.left:
                #値が同じノードの判別のために深さを組み合わせてノードの名前を決定する
                child = f"{node.left.value} of {node.left.depth}"
                #Graphvizで辺を追加
                graph.edge(name, child, label="left", color="blue")
            if node.right:
                child = f"{node.right.value} of {node.right.depth}"
                graph.edge(name, child, label="right", color="red")
        graph.view("bin_tree")


def main():
    A = [32, 75, 30, 31, 65, 5, 435, 4, 5, 43, 523, 5, 534, 5, 43, 534, 5, 43, 534, 5]
    tree = BinarySearchTree(A)
    tree.print_text()
    tree.view_graph()

if __name__ == "__main__":
    main()

실행 결과

위쪽은 Graphviz 출력 이미지이고 아래쪽은 터미널에 표시된 이미지입니다.


사실 나는 오른쪽의 큰 노드, 왼쪽의 작은 노드를
내 조사에 의하면 Graphviz로 방향을 지정할 수 없을 것 같아서 ↑ 이미지처럼
가장자리의 색깔과 라벨로 방향을 표현했다.
아는 사람이 있으면 알려주면 좋겠어요.
※ 추적
상술한 바와 같이 해결되었다!
모서리 색상과 레이블이 필요하지 않으면
self.graph.edge()
의 매개 변수 라벨과 색이 사라지면 일반적인 검은색 테두리, 라벨이 없는 도표가 출력됩니다.
이런 느낌↓

참조 사이트

끝났어!