实现比较简单。

只需在二叉树节点内加入一个bool hasdata成员，表示此节点包含有效位串。

在插入时,遍历位串每一位，如果为1,则二叉树向右，如为0,则向左，在遍历位完成时，设置当前节点hasdata值为true。

最后的中序遍历更为简单

普通中序遍历原型为 middleOrder(currentNode)

代码为

判断 NODE不为NULL;

midlleOrder(currentNode->left);

printKey(currentNode);

middleOrder(currentNode->right);

基数树只需要加个形参即可。

原型 middleOrder(currentNode, string pre = string())

代码：

判断NODE不为NULL

   middleOrder(currentNode->left, pre +"0");

  if (currentNode->hasData)

      print(string);

  middleOrder(currentNode->right, pre +"1");

调用：

middleOrder(Tree)