# golang 区块链：默克尔树(Merkle Tree)

## 生成默克尔树

``````type MerkleTree struct {

RootNode *MerkleNode
}
type MerkleNode struct {

Left *MerkleNode
Right *MerkleNode
Data []byte
}
/* 对默克尔节点进行hash256 */
func hashMerkleNodes(isLeaf bool ,merkleNodes []*MerkleNode) (returnMerkleNodes []*MerkleNode) {

//如果不是叶子，且只有一个节点传入，这是根节点，返回
if !isLeaf && len(merkleNodes) == 1 {

return merkleNodes
}
var nodeLen = len(merkleNodes)
//判断节点奇偶，奇数复制最后一份
var isHaveCopy = false
if nodeLen % 2 != 0 {

copyNode := *merkleNodes[nodeLen - 1]
merkleNodes = append(merkleNodes, &copyNode)
nodeLen = nodeLen + 1
isHaveCopy = true
}
for i:=0; i<nodeLen; i=i+2 {

//两个节点的data相加，后进行hash256
data := append(merkleNodes[i].Data, merkleNodes[i+1].Data...)
//sha256Bytes := sha256.Sum256(data)
//生成新的merkleNode，并加入到返回值
//node := MerkleNode{merkleNodes[i],merkleNodes[i+1],data}
node := MerkleNode{
merkleNodes[i],merkleNodes[i+1],sha256Bytes[:]}
returnMerkleNodes = append(returnMerkleNodes, &node)
}
//处理最后一个（如果是复制前一个的，则子节点置空）
if isHaveCopy {

merkleNodes[nodeLen - 1].Right = nil
merkleNodes[nodeLen - 1].Left = nil
}
//递归进行
return hashMerkleNodes(false,returnMerkleNodes)
}
``````

## 测试正确与否

``````func TestMerkle(t *testing.T) {

//生成叶子
n1 := &MerkleNode{
nil,nil,[]byte("1")}
n2 := &MerkleNode{
nil,nil,[]byte("2")}
n3 := &MerkleNode{
nil,nil,[]byte("3")}
n4 := &MerkleNode{
nil,nil,[]byte("4")}
n5 := &MerkleNode{
nil,nil,[]byte("5")}
//生成tree
nodes := []*MerkleNode{
n1,n2,n3,n4,n5}
tree := NewMerkleTree(true,nodes)
//打印
printTree(tree)
}
func printTree(tree *MerkleNode) {

if tree == nil {

return
}
fmt.Printf("%s\n",tree.Data)
if tree.Left != nil {

printTree(tree.Left)
}
if tree.Right != nil {

printTree(tree.Right)
}
}
``````