이 진 트 리 의 기본 연산 2

이 편 은 이 진 트 리 의 기본 연산 이다.
두 갈래 나무의 옮 겨 다 니 기
이 진 트 리 는 세 가지 로 나 뉜 다. 앞 순서, 중간 순서, 뒤 순서 (뿌리 노드 에 달 려 있다):

앞 순서 옮 겨 다 니 기: 뿌리 결점 - > 왼쪽 나무 - > 오른쪽 나무

중간 순서: 왼쪽 나무 - > 뿌리 결산 점 - > 오른쪽 나무

후 순서 옮 겨 다 니 기: 왼쪽 나무 - > 오른쪽 나무 - > 뿌리 결산 점

또 한 층 한 층 이 왼쪽 에서 오른쪽으로 옮 겨 다 니 는 층 도 있다.예 를 들 면, 아래 의 두 갈래 나무 에 대해
이전 순서 옮 겨 다 니 기: abdefgc 중간 순서 옮 겨 다 니 기: debgfac 후 순서 옮 겨 다 니 기: edgfbca 차원 옮 겨 다 니 기: abcdfeg
실현 방법
트 리 의 정의 자체 가 재 귀적 정의 이기 때문에 재 귀적 인 방법 으로 트 리 의 세 가지 옮 겨 다 니 는 것 은 이해 하기 쉬 울 뿐만 아니 라 코드 도 간결 하 다.나무 가 옮 겨 다 니 는 것 에 대해 서 는 재 귀적 이지 않 은 방법 을 사용 하면 스 택 으로 시 뮬 레이 션 을 해 야 한다.세 가지 옮 겨 다 니 는 과정 에서 앞 순서 와 중간 순서 가 옮 겨 다 니 는 비 재 귀 알고리즘 은 모두 쉽게 실현 되 고 재 귀 후 순서 가 없 으 면 상대 적 으로 어렵 습 니 다.
우선 순 서 를 옮 겨 다 니 기 (비 재 귀적)
go 실현

//     ，    
func preOrderBinaryTree1(root *BinaryTreeNode) {
    if root == nil {
        return
    }
    stack := []*BinaryTreeNode{}
    top := -1
    stack = append(stack, root)
    top++

    for top >= 0 {
        item := stack[top]
        stack = stack[:top]
        top-- //   

        fmt.Print(item.data)
        //       
        if item.rChild != nil {
            stack = append(stack, item.rChild)
            top++
        }
        if item.lChild != nil {
            stack = append(stack, item.lChild)
            top++
        }
    }
}

중간 순서 로 옮 겨 다 니 기 (비 재 귀적)
go 실현

//     ，    
func inOrderBinaryTree1(root *BinaryTreeNode) {
    if root == nil {
        return
    }
    stack := []*BinaryTreeNode{}
    top := -1

    for top >= 0 || root != nil {
        for root != nil {
            stack = append(stack, root)
            top++
            root = root.lChild
        }
        item := stack[top]
        stack = stack[:top]
        top-- //   

        fmt.Print(item.data)
        if item.rChild != nil {
            root = item.rChild
        }
    }
}

뒤 순 서 를 옮 겨 다 닌 다.

//     ，    
func postOrderBinaryTree1(root *BinaryTreeNode) {
    if root == nil {
        return
    }
    stack := []*BinaryTreeNode{}
    top := -1
    var p *BinaryTreeNode = nil
    flag := -1

    for root != nil {
        stack = append(stack, root)
        top++
        root = root.lChild
    }
    flag = 1
    p = nil

    for top != -1 && flag > 0 {
        root = stack[top] //      
        if root.rChild == p {
            fmt.Print(root.data)
            stack = stack[:top]
            top-- //   
            p = root
        } else {
            root = root.rChild
            flag = 0
        }
    }

    for top != -1 {
        for root != nil {
            stack = append(stack, root)
            top++
            root = root.lChild
        }
        flag = 1
        p = nil

        for top != -1 && flag > 0 {
            root = stack[top] //      
            if root.rChild == p {
                fmt.Print(root.data)
                stack = stack[:top]
                top-- //   
                p = root
            } else {
                root = root.rChild
                flag = 0
            }
        }
    }
}

층 차 를 편력 하 다
관건 은 대열 을 이용 하여 먼저 나 가 는 것 이다.

func travelLevelBinaryTree(root *BinaryTreeNode) {
    if root == nil {
        return
    }
    queue := []*BinaryTreeNode{}
    queue = append(queue, root)
    for len(queue) > 0 {
        item := queue[0]
        fmt.Print(item.data)
        queue = queue[1:] //   

        if item.lChild != nil {
            queue = append(queue, item.lChild)
        }

        if item.rChild != nil {
            queue = append(queue, item.rChild)
        }
    }
}