Golang二叉查找树

发布时间：2020-12-16 18:33:20 所属栏目：大数据来源：网络整理

导读：为简单起见，键值均为整型。定义接口(tree.go)： type Tree interface { Put ( k , v int ) //新增或修改 Get k int //查询 Delete //删除 Size () //树的大小 Min //最小键 DeleteMin //删除最小键 } 二叉查找树(binary_tree.go)： //二叉查找树 type Bina

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

定义接口(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}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!