二叉树

时间： 2022-08-16 | 分类：技术 | 阅读： 435 字 ~1分钟

二叉树是很重要的数据结构。其他很多数据结构都是这之上演化而来，因此学好二叉树很有必要。

二叉树定义

每个节点最多只有左子树和右子树的树叫做二叉树。

type Node struct {
	Val int
	Left *Node
	Right *Node
}

二叉树遍历

前序遍历

根节点–>左子树–>右子树

import (
	"fmt"
)

func PreOrderTraverse(tree *Node) {
	if tree == nil {
		return
	}
	fmt.Println(tree.Val)
	PreOrderTraverse(tree.Left)
	PreOrderTraverse(tree.Right)
}

中序遍历

左子树–>根节点–>右子树

import (
	"fmt"
)

func InOrderTraverse(tree *Node) {
  if tree == nil {
    return
  }
  
  InOrderTraverse(tree.Left)
  fmt.Println(tree.Val)
  InOrderTraverse(tree.Right)
}

后序遍历

左子树–>右子树–>根节点

import (
	"fmt"
)

func PostOrderTraverse(tree *Node) {
  if tree == nil {
    return
  }
  
  PostOrderTraverse(tree.Left)
  PostOrderTraverse(tree.Right)
  fmt.Println(tree.Val)
}

二叉树遍历非递归方式

利用栈实现，这里栈用slice替代

前序遍历

import "fmt"

func PreOrder(n *Node) {
  arr := make([]*Node, 0)
  for n != nil {
    fmt.Println(n.Val)
    arr = append(arr, n)
    n = n.Left
  }
  
  n = arr[len(arr)-1]
  arr = arr[0 : len(arr)-1]
  n = n.Right
}

中序遍历

import "fmt"

func InOrder(n *Node) {
  arr := make([]*Node, 0)
  for n != nil {
    arr = append(arr, n)
    n = n.Left
  }
  
  n = arr[len(arr)-1]
  fmt.Println(n.Val)
  arr = arr[0 : len(arr)-1]
  n = n.Right
}

后序遍历

import "fmt"

func PostOrder(n *Node) {
  if n == nil {
    return
  }
  
  arr = make([]*Node, 0)
  out = make([]*Node, 0)
  arr = append(arr, n)
  
  for len(arr) > 0 {
    n = arr[len(arr)-1]
    out = append(out, n)
    arr = arr[0 : len(arr)-1]
    if n.Left != nil {
      arr = append(arr, n.Left)
    }
    if n.Right != nil {
      arr = append(arr, n.Right)
    }
  }
  
  for i := len(out)-1; i >= 0; i-- {
    fmt.Println(out[i])
  }
}

0%