数据结构和算法-Go实现二叉搜索树

二叉树是面试经常考的

package main

import "fmt"

type Node struct{
    Value int
    leftNode *Node
    rightNode *Node
}
type BinaryTree struct{
    len int
    root *Node
}
func NewNode(data int) *Node{
    return &Node{data,nil,nil}
}
func (node *Node)Insert(data int){
    if node.Value > data {
        if node.leftNode != nil{
            node.leftNode.Insert(data)
        }else{
            node.leftNode = NewNode(data)
        }
    }else{
        if node.rightNode != nil{
            node.rightNode.Insert(data)
        }else{
            node.rightNode = NewNode(data)
        }
    }
}
func (node *Node)middleShow(){
    if node.leftNode != nil{
        node.leftNode.middleShow()
    }
    fmt.Println(node.Value)
    if node.rightNode != nil{
        node.rightNode.middleShow()
    }
}
func (node *Node)search(data int) *Node{
    if node.Value == data {
        return node
    }else if node.Value > data {
        if node.leftNode != nil {
            return node.leftNode.search(data)
        }
    }else{
        if node.rightNode != nil{
            return node.rightNode.search(data)
        }
    }
    return nil
}
//----------------------------------------------------
func NewTree() *BinaryTree{
    return &BinaryTree{0,nil}
}
//插入一个数据
func (tree *BinaryTree)Insert(data int){
    tree.len++
    if tree.root != nil{
        tree.root.Insert(data)
    }else{
        tree.root = NewNode(data)
    }
}
//查找值相等的节点
func (tree *BinaryTree)Search(data int) *Node{
    if tree.root != nil {
        return tree.root.search(data)
    }else{
        return nil
    }
}

//前序遍历 根节点->左子树->右子树
//中序遍历 左子树->根节点->右子树
func (tree *BinaryTree)MiddleShow(){
    if tree.root == nil{
        return
    }
    tree.root.middleShow()
}

func main(){
    tree := NewTree()
    tree.Insert(4)
    tree.Insert(6)
    tree.Insert(1)
    tree.Insert(9)
    tree.Insert(2)
    target := tree.Search(60)
    fmt.Println(target)
    tree.MiddleShow()
}

本作品采用《CC 协议》，转载必须注明作者和本文链接