N-ary Tree

16th March 2021 at 5:07pm
Tree

N 个分支的树。

遍历

二叉树 类似,区别点在于:

  • 二叉树是左右子节点,N-ary 树是若干 children 节点
  • N-ary 没有中序遍历,因为有无数种所谓「中序」,比如 (child1, root, chid2, child3, ...)

下面的代码以这颗树作为测试用例:

中序遍历、后序遍历、按层遍历的实现:

package main

import "fmt"

type Node struct {
    Val      int
    Children []*Node
}

func preorder(root *Node) []int {
    answer := []int{}
    if root == nil {
        return answer
    }

    stack := []*Node{root}
    for len(stack) != 0 {
        curr := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        answer = append(answer, curr.Val)
        for i := len(curr.Children) - 1; i >= 0; i-- {
            stack = append(stack, curr.Children[i])
        }
    }

    return answer
}

func postorder(root *Node) []int {
    answer := []int{}
    if root == nil {
        return answer
    }

    firstStack := []*Node{root}
    secondStack := []*Node{}

    for len(firstStack) != 0 {
        curr := firstStack[len(firstStack)-1]
        firstStack = firstStack[:len(firstStack)-1]

        secondStack = append(secondStack, curr)
        firstStack = append(firstStack, curr.Children...)
    }

    for len(secondStack) != 0 {
        answer = append(answer, secondStack[len(secondStack)-1].Val)
        secondStack = secondStack[:len(secondStack)-1]
    }
    return answer
}

func levelOrder(root *Node) [][]int {
    answer := make([][]int, 0)
    if root == nil {
        return answer
    }

    queue := []*Node{root}

    for len(queue) != 0 {
        levelAnswer := []int{}
        nextQueue := []*Node{}
        for _, node := range queue {
            levelAnswer = append(levelAnswer, node.Val)
            nextQueue = append(nextQueue, node.Children...)
        }
        queue = nextQueue
        answer = append(answer, levelAnswer)
    }

    return answer
}

func main() {
    root := &Node{
        1, []*Node{
            {2, nil},
            {3, []*Node{
                {6, nil},
                {7, []*Node{
                    {11, []*Node{
                        {14, nil},
                    }},
                }},
            }},
            {4, []*Node{
                {8, []*Node{
                    {12, nil},
                }},
            }},
            {5, []*Node{
                {9, []*Node{
                    {13, nil},
                }},
                {10, nil},
            }},
        },
    }
    fmt.Println(preorder(root))
    fmt.Println(postorder(root))
    fmt.Println(levelOrder(root))
}