バイナリツリー

木とは何ですか。

ループ構造のないルートディレクトリのグラフィック.
倒木階層非線形データ構造

ツリー用語の整理

ノード:ツリーにデータを格納する基本要素
Root Node:ツリー上部のノード
≪レベル｜Level｜oem_src≫:上位レベルのノードが0の場合、サブブランチに接続されているノードの深さを示します.
Parent Node:ノードに接続されている上位レベルのノード
Child Node:あるノードに接続されている下位レベルのノード
Leaf Node(ターミナルノード):Child Nodeのノードは1つもありません
Sibling:同じParentノードを持つノード
Depth:ツリー内のノードの最大レベル
heightツリーの高さはdepthと同じです

バイナリツリーとは?

各ノードには最大2つのサブノードがあります.
必ず1~2個あるという意味です

  o
o o o 이런 구조면 이진트리가 아니다

バイナリツリー探索の時間的複雑度はO(log(N))であり,一般的な線形データ構造スタックキュー配列の時間的複雑度はO(N)であり,大きな差がある.
従って,非線形構造による探索は線形構造による探索よりも有効である.

Pythonで実施

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def make_tree_by(lst, idx):
    parent = None
    if idx < len(lst): # 재귀함수로 인덱스를 2* 부모 +1 해주니깐 리프노드에선 실행하지 않도록 걸러줌
        value = lst[idx]
        if value is None:
            return

        parent = TreeNode(value)
        #배열로 만들때 [0,1,2,null,null,5,6]
        #  0
        #1   2
        #   5 6
        parent.left = make_tree_by(lst, 2 * idx + 1) #왼쪽은 부모인덱스 * 2 + 1
        parent.left = make_tree_by(lst, 2 * idx + 2) #왼쪽은 부모인덱스 * 2 + 1

    return parent

完全バイナリツリー

バイナリツリーでは、一番下の左側からゆっくりと埋めます.

  o      Level 0
o   o    Level 1
 o o     Level 2  # -> 이진 트리 O 완전 이진 트리 X

   o      Level 0
 o   o    Level 1
o o o     Level 2  # -> 이진 트리 O 완전 이진 트리 O

Pythonで実施

from collections import deque

class TreeNode:
 def __init__(self, val, left=None, right=None):
     self.val = val
     self.left = left
     self.right = right

def sorted_array_to_bst(lst):
 if not lst:
     return None

 mid = len(lst) // 2

 node = TreeNode(lst[mid])
 node.left = sorted_array_to_bst(lst[:mid]) #0의 왼쪽 노드
 node.right = sorted_array_to_bst(lst[mid + 1:]) #0의 오른쪽노드
 return node


def make_lst_by_bst(root, limit):
 if not root:
     return []

 lst = []
 q = deque([root])

 while q:
     if len(lst) > limit: #none을 추가했기떄문에 limit로 제한
         break

     node = q.popleft()
     if node:
         lst.append(node.val)
         q.append(node.left)
         q.append(node.right)
     else:
         lst.append(None) #배열에 none추가를 위한 bfs의 변형

 return lst