0301-实现二叉树先序、中序和后序遍历
【题目】
按照二叉树先序、中序和后序打印所有的节点。 我们约定：先序遍历顺序为根、左、右；中序遍历顺序为左、根、右；后序遍历顺序为左、右、根。
【难度】
校 ★★★☆
package main
import (
"fmt"
"math/rand"
"time"
)
type Node struct {
value int
left, right *Node
}
type Tree struct {
root *Node
}
func NewTree() *Tree {
return &Tree{nil}
}
func NewNode(data int) *Node {
return &Node{data, nil, nil}
}
func (node *Node) addNode(newNode *Node) *Node {
if node.value > newNode.value {
if node.left == nil {
node.left = newNode
} else {
node.left.addNode(newNode)
}
} else {
if node.right == nil {
node.right = newNode
} else {
node.right.addNode(newNode)
}
}
return node
}
func (tree *Tree) Insert(data int) {
newNode := NewNode(data)
if tree.root == nil {
tree.root = newNode
} else {
tree.root.addNode(newNode)
}
}
func preOrder(node *Node) {
if node != nil {
fmt.Printf("%d -> ", node.value)
preOrder(node.left)
preOrder(node.right)
}
}
func (tree *Tree) PreOrder() {
cur := tree.root
if cur != nil {
preOrder(cur)
}
fmt.Println()
}
func inOrder(node *Node) {
if node != nil {
inOrder(node.left)
fmt.Printf("%d -> ", node.value)
inOrder(node.right)
}
}
func (tree *Tree) InOrder() {
cur := tree.root
if cur != nil {
inOrder(cur)
}
fmt.Println()
}
func posOrder(node *Node) {
if node != nil {
posOrder(node.left)
posOrder(node.right)
fmt.Printf("%d -> ", node.value)
}
}
func (tree *Tree) PosOrder() {
cur := tree.root
if cur != nil {
posOrder(cur)
}
fmt.Println()
}
func main() {
rand.Seed(time.Now().UnixNano())
tree := NewTree()
for i := 1; i < 9; i++ {
tree.Insert(rand.Intn(1000))
}
tree.PreOrder()
tree.InOrder()
tree.PosOrder()
}