星海's Blog

老头初学编程
算法导论9.1-1 用O(N + lgn -2 )的运行时间找出第二小元素
二叉树的C++模板,摘自Mark Alen Weiss,中序用栈遍历摘自microgoogle

算法导论习题 12-2

星海 posted @ 2012年11月15日 01:25 in 数据结构与算法分析 , 952 阅读

实现比较简单。

 

只需在二叉树节点内加入一个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)


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter