频道导航

Golang二叉查找树

2019-11-15 Go 前端之家

前端之家收集整理的这篇文章主要介绍了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}