ツリー(Tree)


ツリー

  • 階層ツリー構造の抽象ルート値、および親と子の関係を示すサブツリーと相互接続ノードのセット.
  • 構造
  • はコンピュータ上で私たちの周囲のコンテキスト概念を表現した.
  • 再帰的に定義されたデータ構造
  • ツリーの構成

  • 本:ルートノードとも呼ばれ、ツリーの開始ノードです.根が生えると言って、根だと言っています.ツリーを構築するときに、一番上のノードを配置するように表示します.Aはルートノードです.
  • 親ノード:特定のノードの直接親ノード-DノードがH,Iノードの親ノードである.
  • サブノード:特定のノードの直属サブノード-H、IはDノードのサブノードである.
  • leafノード:ノードを持たない最下位ノード.木の末尾では,ルートノードとは反対に葉ノードと呼ばれる.
  • 深さ:特定のノードからルートノードまでの距離を深さと呼びます.図のレベルと同じ概念です.
  • 高さ:ツリー内の最も深いノードの深さ.写真ではH,I,Jが最も深いノードであり,高さは3である.
  • 部分木:現在の木の一部を表すより小さな木で、D、H、Iからなる木でsub-treeと呼ばれています.
  • ツリーの使用

  • コンピュータ科学における様々な問題を巧みに解決する.整列または圧縮
  • 複数の抽象タイプ(テーブル形式でデータを格納し、格納されたデータを効率的に検索):優先キュー、dict、set
  • ツリーのタイプ


    正二叉木


    すべてのノードに2つのサブノードまたはゼロサブノードを持つツリー

    完全バイナリツリー

  • 最後のレベルより前にすべてのノードが満たされたツリー「完全バイナリツリー」
  • の最後のレベルでは、すべてのノードが埋め込まれていない場合でも、左から右に埋め込まなければなりません.
  • ぐるりと回る


    データ構造に格納されているすべてのデータを迂回する->すべてのノードを出力するだけです.

    ツリー巡り


    再帰出力ツリー内のすべてのノードの使用
  • 予約書ツアー
  • post-order巡回
  • in-orderツアー
  • プリシーケンス巡回



    「ルート」(Root)ノード→左側サブツリー→右側サブツリーの順に出力する方法.
  • 現在のノードデータ出力
  • 再帰左ツリー
  • を巡る
  • 再帰右ツリー
  • を巡る
    class Node:
        """이진 트리 노드를 나타내는 클래스"""
    
        def __init__(self, data):
            """이진 트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
            self.data = data
            self.left_child = None
            self.right_child = None
    
    def traverse_preorder(node):
        """in-order 순회 함수"""
        # 코드를 쓰세요
        if node is None:
            pass
        else:
        	print(node.data)
            traverse_inorder(node.left_child)
            traverse_inorder(node.right_child)
    現在のノードデータをprint()に出力し、->左ノード->右ノード

    post-order巡回



    左サブツリー→右サブツリー→ルートノードの順にループします.実施方法は以下のとおりである.
  • 再帰左ツリー
  • を巡る
  • 再帰右ツリー
  • を巡る
  • 現在のノードデータ出力
  • class Node:
        """이진 트리 노드를 나타내는 클래스"""
    
        def __init__(self, data):
            """이진 트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
            self.data = data
            self.left_child = None
            self.right_child = None
    
    def traverse_postorder(node):
        """in-order 순회 함수"""
        # 코드를 쓰세요
        if node is None:
            pass
        else:
            traverse_inorder(node.left_child)
            traverse_inorder(node.right_child)
    	print(node.data)

    n.巡回



    左サブツリー→ルートノード→右サブツリーの順にループします.
  • 再帰左ツリー
  • を巡る
  • 現在のノードデータ出力
  • 再帰右ツリー
  • を巡る
    class Node:
        """이진 트리 노드를 나타내는 클래스"""
    
        def __init__(self, data):
            """이진 트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
            self.data = data
            self.left_child = None
            self.right_child = None
    
    def traverse_inorder(node):
        """in-order 순회 함수"""
        # 코드를 쓰세요
        if node is None:
            pass
        else:
            traverse_inorder(node.left_child)
            print(node.data)
            traverse_inorder(node.right_child)
    
    ソース:https://geonlee.tistory.com/78