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を参照)、スタックを維持してすべての親ノードをその配列に格納し、スタックから適切にポップするたびにスタックから要素をポップします。最後に要素を見つけると、スタックの 2 番目に上にある要素が祖先になります。

Answer 3

限られたスタックのように、標準的なツリー ウォークを実行し、最後の 2 つのステップを覚えておくことができます。以下のフラグメントは、ポインターの配列 [2] を使用して、最後の 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;
}