유니버설 알고리즘 - [트리 구조] - 두 갈래 나무의 기본 조작 (1)

1. 앞말

수조, 체인표, 두 갈래 나무, 동적 기획, 창고와 대열은 면접에서 자주 보는 지식점이다. 이 몇 가지 지식점에서 두 갈래 나무는 난이도가 비교적 높은 부분에 속하기 때문에 여기서 두 갈래 나무의 자주 보는 조작을 총괄한다. (1) 두 갈래 나무의 귀속 횟수를 포함한다.(2) 두 갈래 나무의 비귀속이 두루 다니기;(3) 두 갈래 나무 잎 노드의 개수 구하기;(4) 두 갈래 나무의 깊이를 구하기;(5) 두 갈래 나무에서 어떤 자목 찾기;(6) 두 갈래 나무와 어떤 값의 경로를 구한다.(7) 두 갈래 나무의 최대 경로와 구하기;(8) 두 갈래 나무의 거울;(9) 어떤 서열이 두 갈래 검색 트리의 뒷 서열인지 판단하기;(10) 두 갈래 검색 트리와 양방향 체인 테이블의 상호 전환;(11) 나무의 두 결점의 최근 조상;(12) 두 갈래 트리 검색 트리의 삽입과 삭제;(13) 무더기의 삽입과 삭제;(14) 나무 한 그루가 균형 있는 두 갈래 나무인지 판단하기;(15) 균형 두 갈래 나무의 조정;

2. 두 갈래 나무의 기본 조작

(1) 두 갈래 나무의 귀속이 반복적으로 귀속되는 형식은 매우 간결하여 몇 줄의 코드로 해결할 수 있다.전순, 후순, 중순이 두루 다니는 형식은 기본적으로 같고 결점 값을 출력하는 시기만 다르다.기본 사상: 만약에 이 결점이 잎결점이라면 바로 되돌아간다. 그렇지 않으면 이 결점의 왼쪽 아이가 비어 있는지, 만약 비어 있지 않으면 차례차례 그 왼쪽 아이를 훑어본다.이어서 오른쪽 아이가 비어 있는지 확인하고, 만약 비어 있지 않으면 차례차례 오른쪽 아이를 훑어본다.코드 구현:

    
def PreOrder_recursion(rootnode):

    if rootnode == None:

        return

    print(rootnode.val)

    if rootnode.left != None:

        PreOrder_recursion(rootnode.left)

    if rootnode.right != None:

        PreOrder_recursion(rootnode.right)

    return

def MidOrder_recursion(rootnode):

    if rootnode == None:

        return

    if rootnode.left != None:

        MidOrder_recursion(rootnode.left)

    print(rootnode.val)

    if rootnode.right != None:

        MidOrder_recursion(rootnode.right)

    return 

def BackOrder_recursion(rootnode):

    if rootnode == None:

        return 
    
    if rootnode.left != None:

        BackOrder_recursion(rootnode.left)

    if rootnode.right != None:

        BackOrder_recursion(rootnode.right)

    print(rootnode.val)

    return

(2) 두 갈래 나무의 비귀속 반복
기본 사상: 만약에 비귀환을 사용한다면 우리는 하나의 창고를 사용하여 함수의 귀환 호출을 모의해야 한다.세 가지 스트리밍 방식에 대해 우리는 모두push 현재 결점->push 왼쪽 트리->pop 왼쪽 트리->push 오른쪽 트리->pop 오른쪽 트리의 방식을 사용한다. 단지 서로 다른 스트리밍 방식으로 결점 값을 출력하는 시기가 다르다.
앞의 순서를 두루 훑어볼 때, 매번 하나의 노드에 접근할 때, 즉 매번 노드를 창고에 넣을 때, 이 노드의 값을 출력한다.[즉, 좌우 노드가 창고에 들어갈 때 좌우 하위 노드의 값을 출력합니다.]
중간 순서로 훑어볼 때 현재 노드의 오른쪽 노드를 창고에 넣을 때마다 현재 노드의 값을 출력합니다.[즉 오른쪽 노드가 창고에 들어가고 팝잎 노드가 들어갈 때 현재 노드의 값을 출력한다.]
뒷순서를 반복할 때, 매번 노드를 창고에서 꺼낼 때, 현재 노드의 값을 출력합니다.[즉, 팝을 할 때 현재 노드의 값을 출력합니다.]
그리고 last_팝 바늘로 지난번 팝의 노드를 기록한다.
현재 노드의 왼쪽 노드가 비어 있지 않고 왼쪽 노드와 하위 노드가 지난번last_pop, 왼쪽 노드를 창고에 넣는다.
현재 노드의 오른쪽 노드가 비어 있지 않으면last_pop, 현재 노드의 왼쪽 노드가 비어 있거나 왼쪽 노드가 last_pop, 오른쪽 노드를 창고에 넣는다.
그렇지 않으면 현재 노드를 창고에서 내보내고 현재 노드를last_로 표시합니다pop.

주의, 여기에는 두 가지 비교적 중요한 데이터 구조가 있다

현재 노드: 창고 원소;

last_팝: 지난번 팝이 나간 결점;

현재 결점이 pop에 의해 두 가지 상황이 있는데 하나는 현재 결점이 잎 노드(왼쪽 노드와 오른쪽 노드가 모두 비어 있음)이고, 다른 하나는 현재 결점의 좌우 결점이 모두 접근되었다(오른쪽 노드는last_pop)
두 갈래 나무의 전순, 중순, 후순은 모두 깊이 우선 전략을 채택한다.
코드 구현:

def PreOrder_Norecursion(rootnode):
    stack = []

    stack.append(rootnode)

    print(rootnode.val,end="")

    last_pop = rootnode

    while len(stack) != 0:

        curnode = stack[-1]

        if curnode.left != None and curnode.left != last_pop and curnode.right != last_pop:

            stack.append(curnode.left)

            print(curnode.left.val,end="")

        elif curnode.right != None and curnode.right != last_pop and (curnode.left == None or curnode.left == last_pop):

            stack.append(curnode.right)

            print(curnode.right.val,end="")

        else:

            stack.pop()

            last_pop = curnode

    return


def MidOrder_Norecursion(rootnode):
    stack = []

    stack.append(rootnode)

    last_pop = rootnode

    while len(stack) != 0:

        curnode = stack[-1]

        if curnode.left != None and curnode.left != last_pop and curnode.right != last_pop:

            stack.append(curnode.left)

        elif curnode.right != None and curnode.right != last_pop and (curnode.left == None or curnode.left == last_pop):

            stack.append(curnode.right)

            print(curnode.val,end="")

        else:

            stack.pop()

            last_pop = curnode

            if curnode.right == None:
                print(curnode.val,end="")

    return


def BackOrder_Norecursion(rootnode):
    stack = []

    stack.append(rootnode)

    last_pop = rootnode

    while len(stack) != 0:

        curnode = stack[-1]

        if curnode.left != None and curnode.left != last_pop and curnode.right != last_pop:

            stack.append(curnode.left)

        elif curnode.right != None and curnode.right != last_pop and (curnode.left == None or curnode.left == last_pop):

            stack.append(curnode.right)

        else:

            stack.pop()

            last_pop = curnode

            print(curnode.val,end="")
    return

(3) 이차수종 잎 노드의 개수 기본 사고방식: 변수leaf_ 사용count는 잎 노드를 계수하여 두 갈래 나무를 훑어볼 때 잎 노드를 만나면leaf_count의 값에 1을 추가합니다.
코드 구현:

def LeafNums_Norecursion(rootnode):
    leaf_count = 0

    stack = []

    stack.append(rootnode)

    last_pop = rootnode

    while len(stack) != 0:

        curnode = stack[-1]

        if curnode.left != None and curnode.left != last_pop and curnode.right != last_pop:

            stack.append(curnode.left)

        elif curnode.right != None and curnode.right != last_pop and (curnode.left == None or curnode.left == last_pop):

            stack.append(curnode.right)

        else:

            stack.pop()

            last_pop = curnode

            if curnode.left == None and curnode.right == None:
                leaf_count += 1

    return leaf_count

leaf_count2 = 0
def LeafNums_Recursion(rootnode):
    if rootnode == None:
        return

    if rootnode.left == None and rootnode.right == None:

        global leaf_count2

        leaf_count2 += 1

    if rootnode.left != None:
        LeafNums_Recursion(rootnode.left)

    if rootnode.right != None:
        LeafNums_Recursion(rootnode.right)

    return

(4) 두 갈래 나무의 깊이 기본 사상: (1) 귀속: 노드가 비어 있으면 깊이가 0이다. 그렇지 않으면 이 나무의 깊이는 왼쪽 나무의 깊이와 오른쪽 나무의 깊이의 최대치+1(2) 비귀속: stack 아날로그 함수의 귀속 호출과 같다. 그러면 창고의 요소의 최대 수량은 나무의 깊이다.
코드 구현:

def Maxdepth_Recursion1(rootnode):
    #  

    if rootnode == None:
        return 0

    left_depth = Maxdepth_Recursion1(rootnode.left)

    right_depth = Maxdepth_Recursion1(rootnode.right)

    root_depth = max(left_depth, right_depth) + 1

    return root_depth


def Maxdepth_Recursion2(rootnode):
    #  ， ， 。

    if rootnode == None:
        return 0

    if rootnode.left == None and rootnode.right == None:
        return 1

    left_depth = 0

    if rootnode.left != None:
        left_depth = Maxdepth_Recursion2(rootnode.left)

    right_node = 0

    if rootnode.right != None:
        right_depth = Maxdepth_Recursion2(rootnode.right)

    root_depth = 0

    root_depth = max(left_depth, right_depth) + 1

    return root_depth


def Maxdepth_NoRecursion(rootnode):

    stack = []

    stack.append(rootnode)

    last_pop = rootnode

    depth = 0

    while len(stack) != 0:

        curnode = stack[-1]

        depth = max(len(stack), depth)

        if curnode.left != None and curnode.left != last_pop and curnode.right != last_pop:

            stack.append(curnode.left)

        elif curnode.right != None and curnode.right != last_pop and (curnode.left == None or curnode.left == last_pop):

            stack.append(curnode.right)

        else:

            stack.pop()

            last_pop = curnode

    return depth

>>다음편: 유니버설 알고리즘-[트리 구조]-이차 트리의 일부 기본 조작(二)