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()
}