『アルゴリズム導論』第12章二叉ルックアップツリー(1)遍歴

ツリーの効率化
ツリーで実行される基本操作の時間は、ツリーの高さに比例します.最悪の場合、
木の高さはNで、チェーンテーブルのように、好ましくはlgNです.そのため、木の高さがポイントです.
次の章で学習する赤と黒の木は、ツリーの高さを維持することによって、ツリーを検索するための改善です.
赤と黒の木の操作が効率的であることを保証します.
各種遍歴アルゴリズム
中順遍歴アルゴリズム:サブツリーのルートのキーワードは、出力時に左サブツリーと右サブツリーのキーワードの間にあります.
つまり、ツリー内のすべてのキーワードを並べ替え順に出力します.
従って、前順遍歴は、サブツリーのルートのキーワードが左右のサブツリーの前に出力されることである.
後続のベースツリーでは、前シーケンスループ(中シーケンスループではなく)は、バイナリ列のソート出力です.
再帰的に二叉木の遍歴を簡単に実現できます.

//               
struct _BSTNode {
     struct _BSTNode *parent, *left, *right;    
     int key;    
     char *value;
};

typedef struct _BSTNode BSTNode;

//     
void bst_inorder_walk(BSTNode *node)
{
     if (node != NULL) {
          bst_inorder_walk(node->left);
          printf("key: %d, val: %s
", node->key, node->value);
          bst_inorder_walk(node->right);
     }         
}

非再帰的インプリメンテーションにおけるシーケンシャルループ
二叉木の一番左のノードに沿って遍歴し、一つずつスタックに入り、一番左のノードに着いてからスタックを出ます.
ポップアップスタックのノードの値を印刷し、そのノードの右の子をルートノードとして、最も左のノードに沿って処理を続けます.

void bst_inorder_walk(BSTNode *node)
{
     BSTNode *stack[20];
     int top = 0;     

     while (node || top != 0) {     
          // Push most-left children to stack
          while (node) {
               stack[top++] = node;
               node = node->left;
          }

          // Print and continue to handle right child
          node = stack[--top];
          printf("%d, %s
", node->key, node->value);
          node = node->right;
               
     }
}