python 데이터 구조 - 두 갈래 트리

python 데이터 구조 - 두 갈래 트리

두 갈래 나무는 노드마다 최대 두 개의 자목이 있는 나무 구조다.보통 하위 트리는'왼쪽 하위 트리'(left subtree)와'오른쪽 하위 트리'(right subtree)라고 불린다

두 갈래 나무의 성질(특성)

성질1: 두 갈래 나무의 i층에서 기껏해야 2(i−1)개의 결점(i>0)이 있다
성질2: 깊이가 k인 두 갈래 나무는 2(k−1)개의 결점이 있다(k>0)
성질 3: 임의의 두 갈래 나무에 대해 잎의 결점 수가 N0이고 도수가 2인 결점 총수가 N2이면 N0=N2+1;

노드의 도: 한 노드에 함유된 서브트리의 개수를 이 노드의 도라고 부른다

성질4: n개의 결점을 가진 완전한 두 갈래 나무의 깊이는log2(n+1)
성질 5: 완전 두 갈래 나무에 대해 위에서 아래로, 왼쪽에서 오른쪽으로 번호를 매기면 번호는 i의 결점이고 왼쪽 아이의 번호는 2i이고 오른쪽 아이의 번호는 2i＋1이다.양친의 번호는 반드시 i/2(i=1시는 루트, 제외)
(1) 완전 두 갈래 나무 - 두 갈래 나무의 높이가 h라면 h층을 제외한 다른 각 층(1~h-1)의 결점수는 최대 개수에 달하고 h층은 잎결점이 있으며 잎결점은 모두 왼쪽에서 오른쪽으로 순서대로 배열된다. 이것이 바로 완전 두 갈래 나무다.
(2) 두 갈래 나무가 가득하다. 잎 결점을 제외한 모든 결점은 좌우 자엽이 있고 잎 결점은 맨 밑에 있는 두 갈래 나무다.

두 갈래 나무의 노드 표시 및 나무 생성

Node 클래스를 사용하여 세 가지 속성을 정의합니다. 각각elem 자체의 값, 그리고lchild 왼쪽 아이와 rchild 오른쪽 아이입니다.

class Node(object):
    """ """
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

트리의 생성, 트리의 클래스를 만들고 루트 루트 노드를 줍니다. 처음에는 비어 있다가 나중에 노드를 추가합니다.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Created by xuehz on 2017/8/24

class Node(object):
    """ """
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

class Tree(object):
    """ """

    def __init__(self, root=None):
        self.root = root

    def add(self, elem):
        """ """
        node = Node(elem)

        #  ， 
        if self.root == None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            #  
            while queue:
                #  
                cur = queue.pop(0)
                if cur.lchild == None:
                    cur.lchild = node
                    return
                else:
                    queue.append(cur.lchild)# ， 
                if cur.rchild is None:
                    cur.rchild = node
                    return
                else:
                    queue.append(cur.rchild)# ， 

    def breadth_travel(self):
        """ """
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print cur_node.elem,
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

    def preorder(self, node):
        """ """
        if node is None:
            return
        print(node.elem, )
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def inorder(self, node):
        """ """
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.elem, )
        self.inorder(node.rchild)

    def postorder(self, node):
        """ """
        if node is None:
            return
        self.postorder(node.lchild)
        self.postorder(node.rchild)
        print(node.elem, )

if __name__ == "__main__":
    tree = Tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)
    tree.breadth_travel()
    print(" ")
    tree.preorder(tree.root)
    print(" ")
    tree.inorder(tree.root)
    print(" ")
    tree.postorder(tree.root)
    print(" ")

두 갈래 나무가 두루 다니다

넓이 우선 반복 (차원 반복)

나무의 루트에서 시작하여 위에서 아래로 왼쪽에서 오른쪽으로 전체 나무의 노드를 훑어보다

def breadth_travel(self, root):
        """ """
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print node.elem,
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)

깊이 우선 반복

이 세 가지 역력은 각각 선차역력(preorder), 중차역력(inorder)과 후차역력(postorder)이라고 부른다
차례차례 두루 다니다
먼저 순서대로 반복합니다. 우리는 먼저 루트 노드를 방문한 다음에 순서대로 왼쪽 트리에 접근한 다음에 순서대로 오른쪽 트리에 접근합니다.
루트 노드 -> 왼쪽 트리 -> 오른쪽 트리

def preorder(self, root):
      """ """
      if root == None:
          return
      print root.elem
      self.preorder(root.lchild)
      self.preorder(root.rchild)

중서 역행
뒷차례 반복에서, 우리는 먼저 뒷차례 반복해서 왼쪽 트리와 오른쪽 트리를 방문하고, 마지막에 루트 노드를 방문한다
왼쪽 트리 -> 오른쪽 트리 -> 루트 노드

def postorder(self, root):
      """ """
      if root == None:
          return
      self.postorder(root.lchild)
      self.postorder(root.rchild)
      print root.elem

뒤돌아 다니다
뒷차례 반복에서, 우리는 먼저 뒷차례 반복해서 왼쪽 트리와 오른쪽 트리를 방문하고, 마지막에 루트 노드를 방문한다
왼쪽 트리 -> 오른쪽 트리 -> 루트 노드

def postorder(self, root):
      """ """
      if root == None:
          return
      self.postorder(root.lchild)
      self.postorder(root.rchild)
      print root.elem

선중, 중 후 유일하게 나무 한 그루를 확정하다