二叉樹：非遞歸例程打印二叉樹節點的祖先？

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