C で次のスレッド化されたツリー表現があるとします。
typedef struct threaded_binary_tree {
int value;
// Flag that tells whether right points to a right child or to a next
// node in inorder.
bool right_is_child;
struct threaded_binary_tree *left, *right;
} threaded_binary_tree;
次に、メモリ内でトラバースすると、O(1)
次のようになります。
void inorder(threaded_binary_tree *node)
{
threaded_binary_tree *prev = NULL;
// Ignore empty trees
if (node == NULL)
return;
// First, go to the leftmost leaf of the tree
while (node->left != NULL)
node = node->left;
while (node != NULL) {
// Nodes are visited along going upward in the tree
printf("%d\n", node->value);
prev = node;
node = node->right;
if (prev->right_is_child) {
// We're descending into tree
if (node != NULL) {
// Again, go to the leftmost leaf in this subtree
while (node->left != NULL)
node = node->left;
}
}
// else, we're climbing up in the tree
}
}
警告: このコードは実行していません。