光辉 的个人资料胡言乱语照片日志列表更多 ![]() | 帮助 |
|
2006/10/28 常数附加空间的非递归方法遍历二叉树class TreeNode
{
TreeNode* leftchild; TreeNode* rightchild;
TreeNode* parent;
T data;
}
//前序遍历
PreOrder(TreeNode* root)
{
TreeNode* t = root;
while(1)
{
visit(t);
if (null != t->leftchild) {
t = t->leftchild;
} else if (null != t->rightchild) {
t = t->rightchild;
} else {
while (t->parent && ( null == t->parent->rightchild || t == t->parent->rightchild) )
t = t->parent;
if (null == t->parent)
break;
else
t = t->parent->rightchild;
}
}
}
如果要遍历的树有n个节点,则运行时间的上界为3n。
这是因为对于树中的每个节点,最多有3个指针指向它(父节点的指针以及两个孩子的父指针),
所以对于某个给定的节点,最多经过3次。所以对于有n个节点的树来说,遍历时间的上界为3n。
由于根节点和叶子节点的存在,事实上不可能达到3n。
2006/10/14 C++中结构的内存结构1) 无数据成员的结构 2006/10/11 C++中浮点变量与零值的比较今天下午参加了一个笔试,考的题目就是《高质量C/C++编程指南》后面附带的试题。当时感觉还不错,回来后看了一下答案,发现还是很有差距。
其中第一题问道:写出 float x 与 “零值”比较的 if 语句。我当下就写下了 if ( 0.0 == x ),可答案是:
const float EPSINON = 0.00001;
if ( (x >= -EPSINON) && (x <= EPSINON ) )
看完后还不明所以!
再看《高质量C/C++编程指南》,有如下解释:
【规则4-3-3】不可将浮点变量用“==”或“!=”与任何数字比较。
千万要留意,无论是float 还是double 类型的变量,都有精度限制。所以一定要避 免将浮点变量用“==”或“!=”与数字比较,应该设法转化成“>=”或“<=”形式。 假设浮点变量的名字为x,应当将 if (x == 0.0) // 隐含错误的比较 转化为 if ((x>=-EPSINON) && (x<=EPSINON)) 其中EPSINON 是允许的误差(即精度)。 |
|
|