Golang二叉查找树

前端之家收集整理的这篇文章主要介绍了Golang二叉查找树前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

为简单起见,键值均为整型。


定义接口(tree.go):

  
  
type Tree interface { Put(k, v int) //新增或修改 Getk int//查询 Delete//删除 Size()//树的大小 Min//最小键 DeleteMin//删除最小键}
二叉查找树(binary_tree.go):
//二叉查找树type BinaryTreestruct root *node n }//创建节点func newNodenode return&node: k v sz 1}//创建二叉查找树func NewBinaryTree*BinaryTree&BinaryTree{}//增加修改func bt *BinaryTree bt.root _ = putbt)//查找get size//选出最小键 min).//删除最小键root deleteMindelete}
节点(node.go):
//节点type node sz //键,值,大小 left right node //左右子节点//在以nd为根节点的树下增加修改一个节点//如果创建了新节点,第二个参数返回true,//如果只是修改,第二个参数返回falsefunc putnd (*boolif nd ==nil newNode),123)">true} hasNew :=false//检测是否创建了新节点 k < ndk leftndelse>rightv v //仅修改,不会增加增加节点,就不更新节点大小//如果创建了新节点就更新树的大小 updateSize hasNew//在以nd为根节点的树中获取键为k的值func k -1v//获取以nd为根节点的树的大小func size0sz//更新以nd为根节点的树的大小func updateSizesz +//选出以nd为根节点的树的最小键节点func minleft !=//删除以nd为根节点的树的最小键节点//返回被删除的节点func deleteMin//找到最小节点right //用右子节点代替自己//还有更小的//删除以nd为根节点的树并且键为k的节点right //命中要删除的节点//只有一个或零个子节点leftright//同时具有两个子节点//先找出大于本节点的最小节点作为后继节点 t ndtk//用后继节点代替本节点 t}
原文链接:https://www.f2er.com/go/189897.html

猜你在找的Go相关文章