package main
import (
"fmt"
queue "test2/Queue"
)
type Node struct {
value int
Left, Right *Node
}
var q queue.ItemQueue
//创建
func CreateNode(val int) *Node {
return &Node{value: val, Left: nil, Right: nil}
}
//设置节点的值
func (node *Node) SetValue(val int) {
node.value = val
}
//打印
func (node *Node) Print() {
fmt.Printf("%+v\n", *node)
}
//前序遍历
func (node *Node) PreOrder() {
if node == nil {
return
}
node.Print()
node.Left.PreOrder()
node.Right.PreOrder()
}
//中序遍历
func (node *Node) MidOrder() {
if node == nil {
return
}
node.Left.MidOrder()
node.Print()
node.Right.MidOrder()
}
//后序遍历
func (node *Node) PostOrder() {
if node == nil {
return
}
node.Left.PostOrder()
node.Right.PostOrder()
node.Print()
}
//广度优先遍历
func (root *Node) Bforder() {
q.Enqueue(root)
for {
item := q.Dequeue()
node, ok := item.(*Node)
if ok {
node.Print()
if node.Left != nil {
q.Enqueue(node.Left)
}
if node.Right != nil {
q.Enqueue(node.Right)
}
if q.IsEmpty() {
break
}
}
}
}
//获取高度
//取两个子节点中大的高度+1
func (node *Node) GetTreeHeight() int {
if node == nil {
return 0
}
lHight := node.Left.GetTreeHeight()
rHight := node.Right.GetTreeHeight()
if lHight >= rHight {
return lHight + 1
} else {
return rHight + 1
}
}
//二叉查找
func (node *Node) Find(val int) *Node {
if node == nil {
return nil
}
result := node
if node.value > val {
node = node.Left
result = node.Find(val)
} else if node.value < val {
node = node.Right
result = node.Find(val)
}
return result
}
//插入
func (node *Node) Insert(val int) (*Node, bool) {
if node == nil {
return CreateNode(val), true
}
if val < node.value {
newP, hasNew := node.Left.Insert(val)
if hasNew {
node.Left = newP
}
} else {
newP, hasNew := node.Right.Insert(val)
if hasNew {
node.Right = newP
}
}
return nil, false
}
//删除
func (node *Node) Delete(val int) *Node {
if node == nil {
return nil
}
// var pNode *Node
// pNode = node
if node.value > val {
node.Left = node.Left.Delete(val)
} else if node.value < val {
node.Right = node.Right.Delete(val)
} else {
//找到需要删除的节点了
//节点有两个子节点
if node.Left != nil && node.Right != nil {
//找到右树中最小的点
minNode := node.Right.FindMinNode()
node.Delete(minNode.value)
minNode.Left = node.Left
minNode.Right = node.Right
return minNode
}
//节点是叶子结点或者只有一个子节点
if node.Left != nil {
return node.Left
} else if node.Right != nil {
return node.Right
} else {
return nil
}
}
return node
}
//查找树中最小的节点
func (node *Node) FindMinNode() *Node {
if node == nil {
return nil
}
var minNode *Node
if node.Left != nil {
minNode = node.Left.FindMinNode()
} else if node.Right != nil {
minNode = node.Right.FindMinNode()
} else {
return node
}
return minNode
}
func main() {
root := CreateNode(33)
root.Left = CreateNode(16)
root.Right = CreateNode(50)
root.Left.Left = CreateNode(13)
root.Left.Right = CreateNode(18)
root.Right.Left = CreateNode(34)
root.Right.Right = CreateNode(58)
root.Left.Left.Right = CreateNode(15)
root.Left.Right.Left = CreateNode(17)
root.Left.Right.Right = CreateNode(25)
root.Right.Right.Left = CreateNode(51)
root.Right.Right.Right = CreateNode(66)
root.Left.Right.Right.Left = CreateNode(19)
root.Left.Right.Right.Right = CreateNode(27)
root.Right.Right.Left.Right = CreateNode(55)
// root.Insert(55)
// root = root.Delete(33)
root.Bforder()
}
有疑问加站长微信联系(非本文作者)