我想要一个用Euler遍历(this is how it works)遍历二叉树的函数当然,递归很容易实现这一点——我知道它是如何工作的但现在我想用堆栈而不是递归来实现这个算法的迭代版本。我的想法是在堆栈上存储我们正在遍历的方向。我的代码不起作用,而且我也不知道该怎么解决这个问题。你能给我一些关于如何解决这个问题的提示吗?这是我目前的代码:
#define LEFT (struct Node*) 0xBADF00D
#define RIGHT (struct Node*) 0xDEADBEEF
struct Node {
int data;
struct Node* parent;
struct Node* left;
struct Node* right;
};
void eulerTree(struct Node* root)
{
stack<struct Node*> s;
s.push(root);
s.push(RIGHT);
s.push(root);
s.push(LEFT);
while(!s.empty()) {
struct Node* direction = s.top(); s.pop();
struct Node* node = s.top(); s.pop();
visit(node);
if(direction == LEFT) {
if(node->left) {
s.push(node->left);
s.push(RIGHT);
s.push(node->left);
s.push(LEFT);
}
}
if(direction == RIGHT) {
if(node->right) {
s.push(node->right);
s.push(RIGHT);
s.push(node->right);
s.push(LEFT);
}
}
}
}
最佳答案
想想一个简单的二叉树:
1
2 3
euler遍历是:
1 2 1 3 1
你可以看到这里的模式:
root, root->left, root, root->right, root
所以你的堆栈顺序应该是:
root
root->left
root
root->right
root
但如果你的根是一片叶子呢?然后不要推任何东西,只要打印值。
同样,在您向左、向右推节点之后,请确保将它们设置为根节点的
0
,这样您就不会一直推它们了。尽管如此,cpp中的代码将是:
编辑:
我之前发布的代码有一个bug正确的代码如下:
void eulerTree(struct Node* root)
{
stack<struct Node*> s;
s.push(root);
while(!s.empty()) {
struct Node* node = s.pop();
visit(node);
if(node->right) {
s.push(node);
s.push(node->right);
}
if(node->left) {
s.push(node);
s.push(node->left);
}
node->left = 0;
node->right = 0;
}
}
不破坏树:
但是,是的,即使代码很简单,这会破坏不需要的树。为了解决这个问题,我将在euler树遍历中对树的叶子使用两个属性。
如果叶是父级的左子级,而该父级的右子级为空
(或)
如果叶子是对的孩子
-打印此叶之后,将父节点一直打印到根节点。
如果叶为左子项,而右子项不为空
-打印此页后,仅打印其直接父页。
为了说明,请看下面的树。
1 2 3 4 5 6 7
如果叶子是
5
的,则在打印之后,再打印所有小于cc>的父对象。如果叶子是
1
的,那么在它被打印之后,就只打印它的直接父项4
。为了简化实现,除了当前堆栈之外,我还将使用父堆栈。
void eulerTree(struct Node* root) {
stack<struct Node*> s;
s.push(root);
struct Node* original = root;
stack<struct Node*> p;
while(!s.empty()) {
struct Node* node = s.top();
s.pop();
visit(node);
if ( !node->right && !node->left && !p.empty() ) {
struct Node* pNode = p.top();
if ( pNode->left == node && !pNode->right || pNode->right == node ) {
while ( !p.empty() ) {
visit(p.top());
p.pop();
}
p.push(original);
} else {
visit(pNode);
}
}
if(node->left || node->right) {
p.push(node);
}
if(node->right) {
s.push(node->right);
}
if(node->left) {
s.push(node->left);
}
}
}