二叉树:非递归例程打印二叉树节点的祖先?
使用非递归子程序来遍历二叉树(请参阅http://en.wikipedia.org/wiki/Tree_traversal#Implementations)并维护一个堆栈以将所有父节点存储在该数组中,并且每当从堆栈弹出时适当地从堆栈中弹出该元素。最后,当你找到元素时,堆栈中第二个最顶层的元素就是祖先。
使用任何迭代实现listed here并在到达祖父节点节点时停止(node.Left.Left = desired OR node.Left.Right = desired OR node.Right.Left = desired OR node.Right.Right =需要的话)。显然你首先需要测试一个候选节点的确有孙子。
你可以做一个标准的树走,记住最后两步,就像一个有限的堆栈。下面片段使用阵列[2]指针记住最后两个步骤的(注:“OPA”是荷兰为“爷爷”):
#include <stdio.h>
#include <stdlib.h>
struct tree_node {
struct tree_node * left;
struct tree_node * right;
int data;
};
/* a bonsai-tree for testing */
struct tree_node nodes[10] =
/* 0 */ {{ nodes+1, nodes+2, 10}
/* 1 */ ,{ nodes+3, nodes+4, 5}
/* 2 */ ,{ nodes+5, nodes+6, 17}
/* 3 */ ,{ nodes+7, nodes+8, 3}
/* 4 */ ,{ nodes+9, NULL, 7}
/* 5 */ ,{ NULL, NULL, 14}
/* 6 */ ,{ NULL, NULL, 18}
/* 7 */ ,{ NULL, NULL, 1}
/* 8 */ ,{ NULL, NULL, 4}
};
struct tree_node * find_opa(struct tree_node *ptr, int val)
{
struct tree_node *array[2] = {NULL,NULL};
unsigned step=0;
for (step=0; ptr; step++) {
if (ptr->data == val) break;
array[ step % 2] = ptr;
ptr = (val < ptr->data) ? ptr->left : ptr->right;
}
return ptr ? array[step %2] : NULL;
}
void show(struct tree_node *ptr, int indent)
{
if (!ptr) { printf("Null\n"); return; }
printf("Node(%d):\n", ptr->data);
printf("%*c=", indent, 'L'); show (ptr->left, indent+2);
printf("%*c=", indent, 'R'); show (ptr->right, indent+2);
}
int main(void)
{
struct tree_node *root, *opa;
root = nodes;
show (root, 0);
opa = find_opa(root, 4);
printf("Opa(4)=:\n");
show (opa, 0);
return 0;
}
什么是盆景树?它是一种特定类型的树吗? – 2013-02-17 15:54:41
这是一棵小树,只因其美丽而存在;-) – wildplasser 2013-02-17 16:07:16
此外,您的代码仅适用于二叉搜索树。你有没有适合普通树的代码(这个问题需要二叉树的一般实现)? – 2013-02-17 16:12:48
我试着首先想到为BST做上述事情。然后我试着想,如果以任何方式我可以扩展二叉树的逻辑。但是这种逻辑不适用于非递归例程。 BST的逻辑:在无限循环中,不断更新根指针,直到您确认该根指针是节点的祖先(或者如果BST中不存在此类节点,则返回null)。 – 2013-02-16 07:22:13
或者只是修改BST,以便子节点拥有对父节点的引用... – nhahtdh 2013-02-16 07:27:51
@nhahtdh我觉得你的建议有点过于模糊,无法使用。你有没有更好的解释你的观点的链接? – 2013-02-17 16:14:09