H*M
发帖数: 1268 | 1 u are given a binary search tree,
each node has a parent, left and right
do pre-order/in-order traversal without stack.
cannot change the structure of Node.
test cases: 8 6 7 5 4 9 10 11 12
test your codes using the test case above. |
t**r
发帖数: 512 | 2 does using recursion = using stack?
【在 H*M 的大作中提到】
: u are given a binary search tree,
: each node has a parent, left and right
: do pre-order/in-order traversal without stack.
: cannot change the structure of Node.
: test cases: 8 6 7 5 4 9 10 11 12
: test your codes using the test case above.
|
z***e
发帖数: 5393 | 3 of course.
theoritically, the stack is used to save parent, since there is pointer to
parent, no need to use stack/recursion. but coding might take a while...
【在 t**r 的大作中提到】
: does using recursion = using stack?
|
h*********e
发帖数: 56 | 4 what about building a finite state machine with 3 states? keep a pointer to the current node, and a state.
we can enter a node in three ways:
A. from parent,
B. from left child, and
C. from right child.
case A: go left, keep state A (if no left child, keep current, state=B)
case B: go right, state=A (if no right child, keep current, state=C)
case C: go up, change state to B or C
initial state is A, initial pointer is root. |
H*M
发帖数: 1268 | 5 ft.可以recursion还往这发吗
【在 t**r 的大作中提到】
: does using recursion = using stack?
|
k***e
发帖数: 556 | 6 geniusxsy has a post on this problem. you can search for it.
【在 H*M 的大作中提到】
: ft.可以recursion还往这发吗
|
H*M
发帖数: 1268 | 7 我看到过那个,可是是有问题的,not working.
【在 k***e 的大作中提到】
: geniusxsy has a post on this problem. you can search for it.
|
g*******y
发帖数: 1930 | 8 I remembered I posted a solution with stack.
If parent links are allowed, it's actually easier, but similar to the stack version.
in_order:
void go_to_leftmost(Node *&root){
while(root->left){ root = root->left;}
}
void in_order(Node *root){
go_to_leftmost(root);
while(root){
print(root);
if(root->right){ root = root->right; go_to_leftmost(root);}
else{
while(root->parent && root==root->parent->right) root = root->parent;
root = root->parent;
}
}
}
post_order:
void go_to_leftrightmost(Node *&roo
【在 H*M 的大作中提到】
: 我看到过那个,可是是有问题的,not working.
|
H*M
发帖数: 1268 | 9 这个不对吧,
你看这个BST:
insert order: 8 6 5 4 7 9 10 11 12
这个会stuck在右边9-10-11-12那块
你编译code就知道了. 用上面这个做test case
只有post order比较好写,in和pre的比较不好写
stack version.
【在 g*******y 的大作中提到】
: I remembered I posted a solution with stack.
: If parent links are allowed, it's actually easier, but similar to the stack version.
: in_order:
: void go_to_leftmost(Node *&root){
: while(root->left){ root = root->left;}
: }
: void in_order(Node *root){
: go_to_leftmost(root);
: while(root){
: print(root);
|
k***e
发帖数: 556 | 10 i did it with the same method. it works.
but i really did not like reading others' code :) I will write some analysis.
suppose we are doing inorder
i think the key point is:
when x is visited, we should know where to go next.
1. x has right kid, then sure go right.
2. x did not have right kid, then we need to go to an ancester of x, say y,
that has path to x as LRRR...R
3. if y cannot be found, done!
4. y exists. then visit y and start from y as above again.
stack version.
【在 g*******y 的大作中提到】
: I remembered I posted a solution with stack.
: If parent links are allowed, it's actually easier, but similar to the stack version.
: in_order:
: void go_to_leftmost(Node *&root){
: while(root->left){ root = root->left;}
: }
: void in_order(Node *root){
: go_to_leftmost(root);
: while(root){
: print(root);
|
|
|
g*******y
发帖数: 1930 | 11 are you talking about in order or post order?
for in order traversal, after it prints 9, since 9 has a right child 10, and
run go_to_leftmost() on 10 has virtually no effect, so next one to print is
10, and then 11, 12
after printing 12, in the part:
else{
while(...)...
...
}
root will become null, therefore end the traversal.
pre-order is a little more complicated, I agree, but in-order and post-order may be not that difficult.
I'm trying to write puseudo code for the pre-order traversal withou
【在 H*M 的大作中提到】
: 这个不对吧,
: 你看这个BST:
: insert order: 8 6 5 4 7 9 10 11 12
: 这个会stuck在右边9-10-11-12那块
: 你编译code就知道了. 用上面这个做test case
: 只有post order比较好写,in和pre的比较不好写
:
: stack version.
|
H*M
发帖数: 1268 | 12 是对的。my bad...
and
is
【在 g*******y 的大作中提到】
: are you talking about in order or post order?
: for in order traversal, after it prints 9, since 9 has a right child 10, and
: run go_to_leftmost() on 10 has virtually no effect, so next one to print is
: 10, and then 11, 12
: after printing 12, in the part:
: else{
: while(...)...
: ...
: }
: root will become null, therefore end the traversal.
|
x******r
发帖数: 249 | 13 What about this one for preorder?
void preorder(node *root)
{
if(!root)
return;
node *current;
node *end;
for(end=root;end->right!=NULL;end=end->right);
current=root;
while(1)
{
visit(current);
if(current==end) return;
if(current->left)
current=current->left;
else if(current->right)
current=current->right;
else
{
for(;current==current->parent->right||!current->parent->right;
cu |
g*******y
发帖数: 1930 | 14 有个问题了，
你的end没找对
应该这样：
end = root;
while(end has at least one child){
if(end->right){
end = end->right;
}else{
end = end->left;
}
}
不过算法貌似还是对的
【在 x******r 的大作中提到】
: What about this one for preorder?
: void preorder(node *root)
: {
: if(!root)
: return;
: node *current;
: node *end;
: for(end=root;end->right!=NULL;end=end->right);
: current=root;
: while(1)
|
x******r
发帖数: 249 | 15 Thank you very much.
My fault.
What about the rest?
【在 g*******y 的大作中提到】
: 有个问题了，
: 你的end没找对
: 应该这样：
: end = root;
: while(end has at least one child){
: if(end->right){
: end = end->right;
: }else{
: end = end->left;
: }
|
r****l
发帖数: 8 | 16 Ithink just need to add one more condition
current->Parent != NULL in for loop to ensure current->Parent is valid, so
you can visit current->Parent->right.
【在 x******r 的大作中提到】
: Thank you very much.
: My fault.
: What about the rest?
|
