BPG树(面试题)

--write by zhuwx 2019-10-31 11:14:12 +0800 CST


package main

import "fmt"

import (
"strings"
"unicode/utf8"
)

type Node struct {
Value string
Left, Right *Node
}

func (node *Node) Print() {
// fmt.Print(node.Value, " ",)
fmt.Print(Ifin(node.Value), " ")
}

func (node *Node) SetValue(v string) {
if node == nil {
fmt.Println("setting value to nil.node ignored.")
return
}
node.Value = v
}

// //前序遍历
// func (node *Node) PreOrder() {
// if node == nil {
// return
// }
// node.Print()
// node.Left.PreOrder()
// node.Right.PreOrder()
// }

// //中序遍历
// func (node *Node) MiddleOrder() {
// if node == nil {
// return
// }
// node.Left.MiddleOrder()
// node.Print()
// node.Right.MiddleOrder()
// }

//后序遍历
func (node *Node) PostOrder() {
if node == nil {
return
}
node.Left.PostOrder()
node.Right.PostOrder()
node.Print()
}

//层次遍历(广度优先遍历)
func (node *Node) BreadthFirstSearch() {
if node == nil {
return
}
result := []string{}
nodes := []*Node{node}
for len(nodes) > 0 {
curNode := nodes[0]
nodes = nodes[1:]
result = append(result, curNode.Value)
if curNode.Left != nil {
nodes = append(nodes, curNode.Left)
}
if curNode.Right != nil {
nodes = append(nodes, curNode.Right)
}
}
for _, v := range result {
fmt.Print(Ifin(v), " ")
}
}

func CreateNode(v string, t string) *Node {
return &Node{Value: v}
}

func Ifin(v string) string {
if (strings.Index(v, "1") != -1) && (strings.Index(v, "0") != -1) {
return "G"
} else if strings.Index(v, "1") != -1 {
return "P"
} else {
return "B"
}
}

func Addnode(node *Node, v string) {
if utf8.RuneCountInString(v) >= 1 {
l_v := v[:utf8.RuneCountInString(v)/2]
r_v := v[utf8.RuneCountInString(v)/2:]
if l_v == "1" || l_v == "0" {
node.Left = &Node{}
node.Left.SetValue(l_v)
node.Right = &Node{}
node.Right.SetValue(r_v)
return
}
if node.Left == nil {
node.Left = &Node{}
node.Left.SetValue(l_v)
Addnode(node.Left, l_v)
}
if node.Right == nil {
node.Right = &Node{}
node.Right.SetValue(r_v)
Addnode(node.Right, r_v)
}
} else {
return
}
}

func main() {
root := Node{Value: "10001101"}
Addnode(&root, root.Value)
fmt.Print("\n后序遍历: ")
root.PostOrder()
fmt.Print("\n层次遍历: ")
root.BreadthFirstSearch() }