yahoo面试题
不用递归循环，遍历树形结构，就这。
昵称: wz_910 时间: 2008-08-13 11:17:00
不懂,关注
昵称: 小蚂蚁 时间: 2008-08-13 11:19:00
等15..........
昵称: 于安 时间: 2008-08-13 11:34:00
等十五
昵称: 小蚂蚁 时间: 2008-08-13 11:34:00
我通知十五了
昵称: 网鬼 时间: 2008-08-13 11:43:00
帮顶，想知道答案 昵称: 17too 时间: 2008-08-13 11:43:00
等~
昵称: hedgelog 时间: 2008-08-13 11:43:00
大家都在等十五？
昵称: blankyao 时间: 2008-08-13 12:08:00
为嘛不给用递归
昵称: 生命如蓝 时间: 2008-08-13 12:17:00
void visit_tree_pre_stk (bintree t) {
pstack ts = new_pstack(32);
pstack_push(ts, t);
while (!pstack_is_empty(ts)) {
bintree u = pstack_pop(ts);
if (u != NULL) {
visit_node(u->val);
pstack_push(ts, u->rt);
pstack_push(ts, u->lt);
}
}
}
pstack ts = new_pstack(32);
pstack_push(ts, t);
while (!pstack_is_empty(ts)) {
bintree u = pstack_pop(ts);
if (u != NULL) {
visit_node(u->val);
pstack_push(ts, u->rt);
pstack_push(ts, u->lt);
}
}
}
昵称: fastso 时间: 2008-08-13 12:33:00
所有用递归写的程序都能改为不是递归的，因为递归要占用stack有些人很讨厌的undefined
昵称: fastso 时间: 2008-08-13 12:35:00
用数据表结构实现？
昵称: wukewei00o 时间: 2008-08-13 12:45:00
现在我都不懂递归是什么算法
昵称: 小蚂蚁 时间: 2008-08-13 12:53:00
不懂・・・・・・・・・・・・・・ 昵称: piaomiao163 时间: 2008-08-13 13:00:00
二叉树
昵称: wz_910 时间: 2008-08-13 13:37:00
昵称: kukukyky 时间: 2008-8-13 13:42
其实堆栈和递归在算法也没什么本质不同，一个是在数据层面上堆栈，一个是在代码层面上堆栈
昵称: kukukyky 时间: 2008-08-13 13:42:00
关注
昵称: 异度冰晶 时间: 2008-08-13 16:13:00
偶手机的背景跟你滴一样耶
昵称: kemy88 时间: 2008-08-13 16:16:00
那肯定挺不错的
昵称: 小蚂蚁 时间: 2008-08-13 16:27:00
假设二叉树的每个节点由对象作为表述，value属性表示该节点值，visited值表示该节点是否已被访问，left属性表示左子树，right属性表示右子树。无子树则标记为null。
$root为已经预定义的二叉树的顶节点
$root为已经预定义的二叉树的顶节点
复制PHP内容到剪贴板
PHP代码:
$stack = array();
$cur = $root;
while(1) {
if($cur->left != null && !$cur->left->visited) {
$stack[] = $cur;
$cur = $cur->left;
} else if($cur->right != null && !$cur->right->visited) {
$stack[] = $cur;
$cur = $cur->right;
} else {
$cur->visited = true;
echo $cur->value,'<br />';
if(($cur = array_pop($stack)) === null) break;
}
}
昵称: Ck_php_kira 时间: 2008-08-13 16:29:00
以前学的算法都忘了，不知道现在这个算法还凑合不。。。
//BFS
1
11
12
111
112
121
1112
1121
//DFS
1
11
111
1112
112
1121
12
121
[ 本帖最后由 sentrychen 于 2008-8-16 18:34 编辑 ]
复制PHP内容到剪贴板
结果PHP代码:
$tree = array(
'value'=>'1',
'left'=>array(
'value'=>'11',
'left'=>array(
'value'=>'111',
'right'=>array(
'value'=>'1112'
)
),
'right'=>array(
'value'=>'112',
'left'=>array(
'value'=>'1121'
)
)
),
'right'=>array(
'value'=>'12',
'left'=>array(
'value'=>'121'
)
)
);
//广度优先
function BFS( &$t){
$s = array();
$s[0] = &$t;
do{
if (isset($s[0]['value'])) echo $s[0]['value'] , "<br>";
if (isset($s[0]['left'])) $s[]= &$s[0]['left'];
if (isset($s[0]['right'])) $s[]= &$s[0]['right'];
array_shift($s);
}while(!empty($s));
}
//深度优先
function DFS( &$t){
$s = array();
$s[0] = &$t;
do{
$c = &$s[0];
if (isset($c['value'])) echo $c['value'] , "<br>";
array_shift($s);
if (isset($c['right'])) array_unshift($s,&$c['right']);
if (isset($c['left'])) array_unshift($s,&$c['left']);
}while(!empty($s));
}
BFS($tree);
DFS($tree);
//BFS
1
11
12
111
112
121
1112
1121
//DFS
1
11
111
1112
112
1121
12
121
[ 本帖最后由 sentrychen 于 2008-8-16 18:34 编辑 ]
昵称: 异度冰晶 时间: 2008-08-13 16:32:00
谁告诉你们是二叉树
递归转非递归
1.归纳法
直接根据1，2，得到N的公式。
2.自建堆栈，模拟递归
有点机器人走迷宫游戏的味道，先记住上一步的位置，如果下一步被堵（代表成功获取返回值），退回到上一步。
自建堆栈，存储程序入口，出口，返回值
推荐阅读：
http://www.javaeye.com/post/567240
http://www.javaeye.com/topic/201241
[ 本帖最后由 hemon 于 2008-8-16 19:39 编辑 ]
递归转非递归
1.归纳法
直接根据1，2，得到N的公式。
2.自建堆栈，模拟递归
有点机器人走迷宫游戏的味道，先记住上一步的位置，如果下一步被堵（代表成功获取返回值），退回到上一步。
自建堆栈，存储程序入口，出口，返回值
推荐阅读：
http://www.javaeye.com/post/567240
http://www.javaeye.com/topic/201241
[ 本帖最后由 hemon 于 2008-8-16 19:39 编辑 ]
昵称: sentrychen 时间: 2008-08-16 18:31:00
不要搞得太复杂，楼主只是要遍历一棵树而已，利用PHP的数组就能轻松搞掂。
昵称: hemon 时间: 2008-08-16 19:11:00
不懂
昵称: sentrychen 时间: 2008-08-16 23:37:00
38.107.179.219 CCBot/1.0 (+http://www.commoncrawl.org/bot.html)