Python 데이터 구조 구현 이 진 트 리

2448 단어
나무의 정의
나 무 는 중요 한 비 선형 데이터 구조 로 직관 적 으로 보면 데이터 요소 (나무 에서 결점 이 라 고 함) 가 분기 관계 에 따라 조직 된 구조 로 자연계의 나무 와 같다.나무 구 조 는 객관 세계 에서 광범 위 하 게 존재 한다. 예 를 들 어 인류 사회의 족보 와 각종 사회 조직 기 구 는 모두 나무 이미지 로 표시 할 수 있다.트 리 는 컴퓨터 분야 에서 도 광범 위 하 게 응용 되 고 있다. 예 를 들 어 원본 프로그램 을 컴 파일 할 때 트 리 로 원본 프로그램의 문법 구 조 를 표시 할 수 있다.또한 데이터베이스 시스템 에서 트 리 구조 도 정보의 중요 한 조직 형식 중 하나 이다.모든 계층 적 관 계 를 가 진 문 제 는 나무 로 설명 할 수 있다.
나무 구조의 특징 은 모든 결점 은 하나의 직접적인 후계 만 있 는 것 이 아니 라 뿌리 결점 을 제외 한 모든 결점 이 있 고 하나의 직접적인 전구 만 있 는 것 이다.
나무의 귀속 정 의 는 다음 과 같다.
  • 적어도 하나의 결점 (뿌리 라 고 함)
  • 이 있다.
  • 다른 것 은 서로 교차 하지 않 는 나무
  • 이 진 트 리
    이 진 트 리 는 n (n ≥ 0) 개의 결점 으로 구 성 된 유한 한 집합 이 고 모든 결점 은 최대 두 개의 나무 가 있 는 질서 있 는 나무 이다.그것 은 빈 집 이나 왼쪽, 오른쪽 나무 라 고 불 리 는 두 개의 교차 하지 않 는 이 진 트 리 로 구성 되 어 있다.
    특징:
  • 이 진 트 리 는 질서 있 는 나무 로 한 개의 나무 만 있어 도 왼쪽, 오른쪽 나 무 를 구분 해 야 한다.
  • 이 진 트 리 의 모든 노드 의 도 는 2 보다 크 면 안 되 고 0, 1, 2 세 가지 중 하나 만 얻 을 수 있다.
  • 이 진 트 리 의 모든 결점 의 형 태 는 5 가지 가 있다. 빈 결점, 좌우 자수의 결점 이 없고 왼쪽 자수의 결점 만 있 으 며 오른쪽 자수의 결점 과 좌우 자수의 결점 만 있다.

  • 원본 코드:
    #-*- encoding:utf-8 -*-
    
    '''
        :
         5
      6     7
    8         9
    '''
    
    class Tree():
       '    '
        def __init__(self,ltree = 0,rtree = 0,data = 0):
            self.ltree = ltree
            self.rtree = rtree
            self.data = data
    class BTree():
        '      '
        def __init__(self,base = 0):
            self.base = base
        def _Empty(self):
            '     '
            if self.base == 0:
                return True
            else:
                return False
        def qout(self,tree_base):
            '    : - - '
            if tree_base == 0:
                return
            print tree_base.data
            self.qout(tree_base.ltree)
            self.qout(tree_base.rtree)
        def mout(self,tree_base):
            '    : - - '
            if tree_base == 0:
                return
            self.mout(tree_base.ltree)
            print tree_base.data
            self.mout(tree_base.rtree)
        def hout(self,tree_base):
            '    : - - '
            if tree_base == 0:
                return
            self.hout(tree_base.ltree)
            self.hout(tree_base.rtree)
            print tree_base.data
    #test
    
    tree1 = Tree(data=8)
    tree2 = Tree(data=9)
    tree3 = Tree(tree1,data=6)
    tree4 = Tree(tree2,0,data=7)
    base = Tree(tree3,tree4,5)
    btree = BTree(base)
    print '      :'
    btree.qout(btree.base)
    print '      :'
    btree.mout(btree.base)
    print '      :'
    btree.hout(btree.base)

    좋은 웹페이지 즐겨찾기