golang 두 갈래 검색 트 리 구현 (대상 지향, 비 귀속)

두 갈래 검색 트 리
golang 은 재 귀적 이지 않 은 두 갈래 검색 트 리 (OO) 를 실현 합 니 다.실현 시 index 를 색인 으로 비교 하고 data 에 노드 데 이 터 를 기록 합 니 다.실현 방법: 1. 이 진 트 리 에 노드 삽입 (Insert);2. 이 진 트 리 에서 노드 찾기 (Search);3. 이 진 트 리 에서 노드 삭제 (Delete) - > 여러 가지 상황 을 고려 해 야 합 니 다. 하위 트 리 는 없고 왼쪽 이나 오른쪽 트 리 만 있 으 며 왼쪽 트 리 와 오른쪽 트 리 가 있 습 니 다.
이 진 트 리 검색 은 밸 런 스 트 리 가 아 닙 니 다. 최 악의 경우 검색 (n), 최 적의 경우 log(n)소스 코드

package main

import (
    "container/list"
    "errors"
    "fmt"
)

var (
    errNotExist       = errors.New("index is not existed")
    errTreeNil        = errors.New("tree is null")
    errTreeIndexExist = errors.New("tree index is existed")
)

type BSTree struct {
    root *Node
}
type Node struct {
    lchild *Node
    rchild *Node
    parent *Node
    index  int
    data   int
}

//       
func (tree *BSTree) Search(index int) (*Node, error) {
    node := tree.root
    for {
        if node == nil {
            return nil, errNotExist
        }
        if index == node.index { //   index  
            return node, nil
        } else if index > node.index {
            node = node.rchild
        } else {
            node = node.lchild
        }
    }
}

func (tree *BSTree) Delete(node *Node) error {
    if node == nil {
        return errNotExist
    }
    //        
    var n *Node
    if node.lchild == nil && node.rchild == nil {
        n = nil
    } else if node.lchild == nil || node.rchild == nil {
        //              
        if node.lchild != nil {
            n = node.lchild
        } else {
            n = node.rchild
        }
    } else if node.lchild != nil && node.rchild != nil {
        //          
        n = node.lchild
        //        
        for {
            if n.rchild == nil {
                break
            }
            n = n.rchild
        }
        //          
        if n.index > n.parent.index {
            n.parent.rchild = nil
        } else {
            n.parent.lchild = nil
        }
        //      
        n.parent = node.parent
        n.lchild = node.lchild
        n.rchild = node.rchild
    }
    if node.parent == nil { //   
        tree.root = n
    } else if node.parent.index > node.index {
        node.parent.lchild = n
    } else {
        node.parent.rchild = n
    }
    return nil
}

func (tree *BSTree) Insert(index int, data int) error {
    //     
    if tree.root == nil {
        tree.root = &Node{lchild: nil, rchild: nil, parent: nil, index: index, data: data}
        return nil
    }
    //         
    node := tree.root
    for {
        if node.index == index {
            return errTreeIndexExist
        }
        //    ，    
        if node.index > index {
            if node.lchild == nil {
                node.lchild = &Node{lchild: nil, rchild: nil, parent: node, index: index, data: data}
                return nil
            } else {
                node = node.lchild
                break
            }
        }
        if node.index < index {
            if node.rchild == nil {
                node.rchild = &Node{lchild: nil, rchild: nil, parent: node, index: index, data: data}
                return nil
            } else {
                node = node.rchild
                break
            }
        }
    }
    return nil
}

//     ，           
func (tree *BSTree) Midtraverse(handle func(interface{}) error) error {
    //func (tree *BSTree) Midtraverse() error {
    if tree.root == nil {
        return errTreeNil
    }
    l := list.New()
    //  、    ----> list      ：push      ， get      
    l.PushBack(tree.root)
    for {
        e := l.Front()
        if e == nil {
            break
        }
        //container/list        Element  ，Element Value interface{}       ，            
        node := e.Value.(*Node)
        l.Remove(e)

        if err := handle(node); err != nil {
            return err
        }
        //     
        if node.lchild != nil {
            l.PushBack(node.lchild)
        }
        //     
        if node.rchild != nil {
            l.PushBack(node.rchild)
        }
    }
    return nil
}

//test
func main() {
    tree := &BSTree{}
    //       
    tree.Insert(3, 6)
    tree.Insert(4, 6)
    tree.Insert(2, 7)
    //        
    f := func(node interface{}) error {
        if node.(*Node).parent == nil {
            fmt.Printf("this node is tree root node. node.index:%d node.data:%d
", node.(*Node).index, node.(*Node).data)
        } else {
            fmt.Printf("node.index:%d node.data:%d node.parent.index:%d
", node.(*Node).index, node.(*Node).data, node.(*Node).parent.index)
        }
        return nil
    }
    //       ,    
    if err := tree.Midtraverse(f); err != nil {
        fmt.Printf("Midtraverse failed err:%v
", err)
    }
    //      
    node, err := tree.Search(3)
    if err != nil {
        fmt.Printf("Search failed, err:%v", err)
    } else {
        f(node) //          
    }
    //    ，         
    fmt.Printf("Delete node.index:%d
", node.index)
    tree.Delete(node)

    if err := tree.Midtraverse(f); err != nil {
        fmt.Printf("Midtraverse failed err:%v
", err)
    }

}

실행 결과

$ go run main.go
this node is tree root node. node.index:3 node.data:6
node.index:2 node.data:7 node.parent.index:3
node.index:4 node.data:6 node.parent.index:3
this node is tree root node. node.index:3 node.data:6
Delete node.index:3
this node is tree root node. node.index:2 node.data:7
node.index:4 node.data:6 node.parent.index:3