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

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 =需要的话）。显然你首先需要测试一个候选节点的确有孙子。

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("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; 
}