데이터 구조-트 리-학습 노트

http://interactivepython.org/courselib/static/pythonds/index.html
Problem Solving with Algorithms and Data Structures 
나무.
Examples of Trees
컴퓨터 과학 에는 많은 응용 이 있다.
        운영 체제,데이터베이스,컴퓨터 네트워크
        파일 시스템
         홈 페이지
Vocabulary and Definitions
원소:
        root，branches，leaves
특성:
        hierarchical
               각 노드 에 질문 을 하고 적당 한 답 의 경 로 를 선택 하여 계속 아래로 내 려 갑 니 다.
               임의의 키 나 무 를 움 직 일 수 있 으 며,저층 의 구조 에 영향 을 주지 않 는 다.
        한 노드 의 children 과 다른 노드 의 children 은 독립 적 이다.
               따라서 하위 노드 를 바 꿀 때 다른 하위 노드 에 영향 을 주지 않 습 니 다.
        모든 잎 노드 는 유일한 것 이다.
               따라서 뿌리 에서 잎 노드 까지 유일한 경로 가 있다.
개념:
        node： name->key, additional information->payload
        edge:   노드 간 의 관계,한 노드 에 하나의 incoming edge 만 있 고 여러 개의 outgoing edge 가 있 습 니 다.
        root:트 리 에 유일 하 게 incoming edge 가 없 는 노드
        path，
children，parent，sibling，subtree
        leaf node:children 없 는 node
        level:루트 에서 노드 까지 path 의 edge 갯 수
        이 나무 에서 가장 큰 level
        biary tree:나무의 모든 노드 는 최대 두 명의 children 만 있 습 니 다.
정의:
Definition One: A tree consists of a set of nodes and a set of edges that connect pairs of nodes.
Definition Two: A tree is either empty or consists of a root and zero or more subtrees, each of which is also a tree. The root of each subtree is connected to the root of the parent tree by an edge.
List of Lists Representation
a tree represented by a list of lists
creating a simple tree using a list

myTree = ['a',['b',['d',[],[]],['e',[],[]]],['c',['f',[],[]],[]]]
print(myTree)
print('left subtree =',myTree[1])
print(myTree[1][1])
print(myTree[1][1][1])

각 list 의 첫 번 째 요 소 는 root 이 고 두 번 째 요 소 는 left subtree 이 며 세 번 째 요 소 는 right subtree 입 니 다.
잎 노드 에 루트 하나 와 빈 list 두 개가 있 습 니 다.

def BinaryTree(r):
    return [r, [], []]


#to insert a left child
def insertLeft(root,newBranch):
    t = root.pop(1)             #1st level left subtree
    if len(t) > 1:              #if null, len is 0
        root.insert(1,[newBranch,t,[]])       #insert newBranch in left position
    else:
        root.insert(1,[newBranch, [], []])
    return root



r = BinaryTree(3)
print(r)
    #[3, [], []]
print(len(r.pop(1)))
    #0

insertLeft(r,4)
print(r)
    #[3, [4, [], []]]

insertLeft(r,5)
print(r)
    #[3, [5, [4, [], []], []]]


root = r
newBranch = 6

t = root.pop(1)
print(t)
    #[5, [4, [], []], []]

print(len(t))
    #3

root.insert(1,[newBranch,t,[]])
print(root)
    #[3, [6, [5, [4, [], []], []], []]]

t = root.pop(1)
print(t)
    #[6, [5, [4, [], []], []], []]

print(len(t))
    #3

def BinaryTree(r):
    return [r, [], []]


#to insert a left child
def insertLeft(root,newBranch):
    t = root.pop(1)             #1st level left subtree
    if len(t) > 1:              #if null, len is 0
        root.insert(1,[newBranch,t,[]])       #insert newBranch in left position
    else:
        root.insert(1,[newBranch, [], []])
    return root

r = BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)

def insertRight(root,newBranch):
    t = root.pop(2)
    if len(t)>1:
        root.insert(2,[newBranch,[],t])
    else:
        root.insert(2,[newBranch,[],[]])
    return root

insertRight(r,6)
print(r)

insertRight(r,7)
print(r)


def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

print(getLeftChild(r))
print(getRightChild(r))
print(getRightChild(getLeftChild(r)))


def getRootVal(root):
    return root[0]

def setRootVal(root,newVal):
    root[0] = newVal
    return root[0]

print(getRootVal(r))

setRootVal(r,10)
print(getRootVal(r))