アルゴリズム(ツリー)

3827 ワード

アルゴリズム#アルゴリズム# テキストリンク

バイナリツリー

バイナリツリーは非線形の資料構造である.バイナリ・ツリーは、データの閲覧速度を速めるために使用されます.
バイナリツリーが出現する以前の通常のツリーでは,サブツリーの数を制限しないため,データの統一管理が困難であった.また、必要なデータを検索するプロセスは煩雑で非効率です.したがって,Izenツリーが出現してから,ほとんどのツリーがIjinツリーとして表現されている.
バイナリツリーは、すべてのノードに2つのサブツリーがあるツリーです.
ルートと左サブツリー、右サブツリーからなるノードの集合、およびzenツリーのサブツリーは、バイナリツリーでなければなりません.

ほうわバイナリ

ツリーの各レベルにノードのバイナリツリーがあります.

完全バイナリツリー

完全バイナリツリーとは、ツリーの高さがhの場合、1レベルからh−1レベルまでのすべてのノードが充填され、最後のレベルhでノードが順番に充填されるツリーである.つまり上から順番に木を埋めていく形です.

その他のバイナリツリー

飽和バイナリツリー、完全バイナリツリーを除き、すべてのバイナリツリーを他のバイナリツリーと呼ぶ.

バイナリツリーの性質

ノードの個数がnであれば、幹線の個数はn−1である.(ルートノードの親がいないので.)

高さがnの場合、n~2ⁿ−1個のノードがある.

バイナリツリーの配列表現

配列を作成するときは、バイナリツリーのプロパティを考慮すると、ツリーの空白部分はいつでも値を持つことができるので、配列にも空に割り当てます.
ノードiの親ノードインデックス=i/2=>//は、1つのノードが共有されている場合、残りのノードを捨てる必要があるためです.
ノードiの左サブノードインデックス=2 i
ノードiの右サブノードインデックス=2 i+1

バイナリツリーの演算

ぐるりと回る

ツリー内のすべてのノードを巡回
線形サブ構造の順序は簡単です=>順番にアクセスするだけです
ツリーには様々な方法ex)(BFS、DFS)

前列巡回VLR(ルート->左->右)=DFS

def preorder(n):
	if n is not None:
    	print(n.data, end='') // 루트노드 처리
        preorder(n.left) // 왼쪽 서브트리 처리
        preorder(n.right) // 오른쪽 서브트리 처리

中尉巡回LVR(左->根->右)

def inorder(n):
	if n is not None:
        inorder(n.left) // 왼쪽 서브트리 처리
        print(n.data, end='') // 루트노드 처리
        inorder(n.right) // 오른쪽 서브트리 처리

後方巡回LV(左->右->根)

def postorder(n):
	if n is not None:
        postorder(n.left) // 왼쪽 서브트리 처리
        postorder(n.right) // 오른쪽 서브트리 처리
        print(n.data, end='') // 루트노드 처리

レベルポーリング(ノードのポーリング方法をレベル別にチェック)

キューを使用して実装します.
ループを使用しません.
操作順序の計算に使用可能(操作の優先度)

def levelorder(root):
	queue = CircularQueue() //큐 객체 초기화
    queue.enqueue(root)  // 최초의 큐에는 루트 노드만 들어있음
    while not queue.isEmpty(): // 큐가 공백이 아닌 동안
    	n = queue.dequeue //큐에서 맨 앞의 노드 n을 꺼냄
        if n is not None:
        	print(n.data, end='') //먼저 노드의 정보를 출력
            queue.enqueue(n.left) // n의 왼쪽 자식 노드를 큐에 삽입
            queue.enqueue(n.right) // n의 오른쪽 자식 노드를 큐에 삽입