二进制树:打印二进制树中节点祖先的非递归例程

Question

我必须编写一个非递归程序来打印二进制树中给定节点的祖先（父节点的父节点）。我应该使用什么逻辑？

Answer 1

使用非递归子例程遍历二进制树（请参阅http://en.wikipedia.org/wiki/Tree_traversal#Implementations)并维护一个堆栈来存储该数组中的所有父节点，并且每当您从堆栈中弹出时，都会从堆栈中适当地弹出元素。最后，当您找到元素时，堆栈中第二个最上面的元素将是祖先。

Answer 2

使用此处列出的任何迭代实现，并在到达父节点时停止（node.Left.Left=所需OR节点.Left.Right=所需OR节点.Right.Left=所需或节点.Right.Right=所需）。很明显，您首先需要测试候选节点是否确实有孙节点。

Answer 3

您只需执行标准的树遍历并记住最后两个步骤，就像有限的堆栈一样。下面的片段使用指针数组[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("Nulln"); 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;
}