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

Question

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

Answer 1

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

Answer 2

使用任何迭代实现listed here并在到达祖节点时停止(node.Left.Left = desired OR node.Left.Right = desired OR node.Right.Left = desired OR node.Right.Right = desired)。显然，您首先需要测试候选节点是否确实有孙子节点。

Answer 3

你可以只做一个标准的树遍历，并记住最后两步，就像一个有限的堆栈。下面的代码片段使用指针的array2来记住最后两个步骤(注意："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;
}