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

Question

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

Answer 1

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

Answer 2

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

Answer 3

你可以做一个标准的树遍历并记住最后两个步骤，就像一个有限的堆栈。下面的片段使用一个指针数组[2] 来记住最后两个步骤（注意：“opa”是荷兰语的“granddad”）：

#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;
}