问个打印树的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个打印树的问题

问个打印树的问题# JobHunting - 待字闺中

x*n2011-08-21 07:08

1 楼

大家好，想问一个基础的问题。假如有一个二叉树，
A
B C
怎么打印出AB, AC，就是从根到各个叶子结点的路径?请问有什么好的方法吗。谢谢！

r*y2011-08-21 07:08

2 楼

recursion?

！

【在 x***n 的大作中提到】

: 大家好，想问一个基础的问题。假如有一个二叉树，
: A
: B C
: 怎么打印出AB, AC，就是从根到各个叶子结点的路径?请问有什么好的方法吗。谢谢！

v*n2011-08-21 07:08

3 楼

DFS，全路径入栈，每次到底就打印全栈

P*c2011-08-21 07:08

4 楼

这个跟recursion应该是一样的。

【在 v***n 的大作中提到】

: DFS，全路径入栈，每次到底就打印全栈

v*n2011-08-21 07:08

5 楼

recursion是系统帮你管理栈
non-recursion实现得自己管理栈的
问题在于recursion实现的话怎么去遍历栈呢？

【在 P**********c 的大作中提到】

: 这个跟recursion应该是一样的。

i*e2011-08-21 07:08

6 楼

//Hope it works
print_bt(Node *p, string &a)
{
if(p->left)
{
a.push_back(p->data);
print_bt(p->left, a);
}
else if(p->right)
{
a.erase(a.rbegin()); //a.pop_back
a.push_back(p->data); //remove its sibling & add its data
print_bt(p->right, a);
}
else //leaf ?
{
cout << a << endl;
}
}

v*n2011-08-21 07:08

7 楼

你的assumption太强了
不是一定都有左右子树的
而且你这个也没有对每条路经提供完整的从root开始的历史

【在 i*****e 的大作中提到】

: //Hope it works
: print_bt(Node *p, string &a)
: {
: if(p->left)
: {
: a.push_back(p->data);
: print_bt(p->left, a);
: }
: else if(p->right)
: {

c*p2011-08-21 07:08

8 楼

#define DELIMITER '-'
void print_btree(node* root, const string path)
{

if (root == NULL)
return;
// Valid for single-letter named nodes;
string new_path = path + root->name;
// name delimiter needed otherwise
//string new_path = path + path.size()? DELIMITER : '' + root->name;
cout << new_path << ' ';
print_btree(root->left, new_path);
print_btree(root->right, new_path);
//return;
}
int main()
{
// create a btree rooted at btree_root;
print_btree(btree_root, string(""));
return;
}

！

【在 x***n 的大作中提到】

: 大家好，想问一个基础的问题。假如有一个二叉树，
: A
: B C
: 怎么打印出AB, AC，就是从根到各个叶子结点的路径?请问有什么好的方法吗。谢谢！

P*c2011-08-21 07:08

9 楼

跟你说的差不多。其实DFS也可以用recursion做哈。
void print_path(tree* root, vector& path){
if(!root)
return;
path.push_back(root);
if(!root->left_child && !root->right_child){
for(int i=0; icout<data<cout<}
else{
if(root->left_child)
print_path(root->left_child, path);
if(root->right_child)
print_path(root->right_child, path);
}
path.pop_back();
}
test tree:
3
1 5
0 2 4 6
-1
output:
3 1 0 -1
3 1 2
3 5 4
3 5 6
这道题我觉得要注意的是不能直接用NULL的时候就全部打出，因为那样每条path都会打
两遍。

【在 v***n 的大作中提到】

: recursion是系统帮你管理栈
: non-recursion实现得自己管理栈的
: 问题在于recursion实现的话怎么去遍历栈呢？

x*n2011-08-21 07:08

10 楼

谢谢啊。其实就一先根遍历，我把问题给想复杂了。recursion总是用不好。

【在 P**********c 的大作中提到】

: 跟你说的差不多。其实DFS也可以用recursion做哈。
: void print_path(tree* root, vector& path){
: if(!root)
: return;
: path.push_back(root);
: if(!root->left_child && !root->right_child){
: for(int i=0; i: cout<data<: cout<: }