9.2ツリーの遍歴

9.2ツリーの遍歴
ツリーの遍歴とは、ツリーに一定の順序でアクセスするすべてのノードを指します.遍歴方法は一般的に4種類ある:先序遍歴、中序遍歴、後序遍歴および階層遍歴、そのうち、前の3種類は一般的に深さ優先探索(DFS)で実現され、階層遍歴は一般的に広さ優先探索(BFS)で実現される.
まず、前の3つの遍歴方法を見てみましょう.前に二叉木の再帰定義を示したが,この定義方式はここでよく遍歴法と融合する.1本の二叉木を3つの部分に分けます.根ノード、左サブツリー、右サブツリーで、左サブツリーと右サブツリーを同じように区分します.これにより、ツリーの遍歴はこの3つの部分の遍歴に分解されます.読者はまず、この3つの遍歴のいずれにしても、左の木が右の木より優先されることを覚えておいてください.また、「先中後」とは、ルートノードrootが遍歴中の位置を指すため、先順遍歴のアクセス順はルートノード→左サブツリー→右サブツリー、中順遍歴のアクセス順は左サブツリー→ルートノード→右サブツリー、後順遍歴のアクセス順は左サブツリー→右サブツリー→ルートノードである.
9.2.1先順遍歴
先順遍歴については、常にルートノードrootにアクセスしてから左サブツリーと右サブツリーにアクセスするので、先順遍歴の便利な順序はルートノード→左サブツリー→右サブツリーである.
再帰的なシーケンスループを実現するには,再帰式と再帰境界の2つのものが必要である.ここで、再帰式は、線順遍歴の定義によって直接得ることができる.すなわち、まず係ええにアクセスし、左サブツリーに再帰的にアクセスし、最後に右サブツリーに再帰的にアクセスする.では、このようにして左サブツリーと右サブツリーに再帰的にアクセスし続けると、再帰境界は何でしょうか.二叉木の再帰定義における再帰境界は二叉木が空の木であることも同様にここで用いることができ,他の再帰がサブツリーにアクセスする際に,サブツリーが空であると,デッドホールに達したことを示し,再帰式と再帰境界に達し,先順遍歴のコードを書くことができる.

void preorder(node *root)
{
    if (root == NULL)
    {
        return;
    }
    else
    {
        printf("%d",root->data);
        preorder(root->lc);
        preorder(root->rc);
    }
}

2.先行遍歴の性質
ルートノードにアクセスする前にルートを順次巡回するため、1本のツリーの先順に巡回すると、シーケンスの最初のノードはルートノードに違いありません.
中序遍歴と後序遍歴は方法と先序遍歴が同じで方法紹介をしないため、性質だけを述べる.
9.2.2.2のシーケンス遍歴

void inorder(node *root)
{
    if (root == NULL)
    {
        return;
    }
    else
    {
        printf("%d",root->lc->data);
        inorder(root);
        inorder(root->rc);
    }
}

2.中序遍歴の性質
中間ループは常にルートノードを左サブツリーと右サブツリーの間に置くため,ルートノードが分かれば,ルートノードの中間ループにおけるルートノードの位置で左サブツリーと右サブツリーを区別することができる.
9.2.3後序遍歴

void postorder(node *root)
{
    if (root == NULL)
    {
        return;
    }
    else
    {
        printf("%d",root->lc->data);
        postorder(root->rc);
        postorder(root);
    }
}

2.後段遍歴の性質
後順ループは常にルートノードを最後にアクセスし、これは先順ループとは正反対であるため、後順ループにとってシーケンスの最後の1つはルートノードに違いない.
総じて、ツリーを一意に決定するには、先行シーケンスでも後続シーケンスでも、中シーケンスでのみシーケンスをループすることを知っておく必要があります.これは,先順遍歴シーケンスと後順遍歴シーケンスではルートノードのみが得られ,中順遍歴シーケンスでのみルートノードを利用して左右のサブツリーを分離し,1本の二叉木に再帰するためである.もちろん、この方法はすべての要素が異なる場合に使用されることを保証する必要があります.
9.2.4層遍歴
レイヤシーケンシャルループとは、ルートノードから階層順にレイヤごとにループし、同じレイヤのノードを左から右にループすることです.このプロセスはBFSとよく似ています.BFSの検索は常に広さを第一のキーワードとし、二叉木に対応する広さは階層に適切に現れているため、階層遍歴は二叉木のルートノードからの広さを優先的に検索することに相当します.その基本的な考え方は以下の通りです.
1.ルートノードrootをキューqに入れる
2.キューの先頭ノードを取り出してアクセス
3このノードに左の子供がいる場合は、左の子供をチームに入れます.
4.このノードに右の子供がいる場合は、右の子供をチームに入れます.
5.キューが空になるまで2を返します.

void layerorder(node * root)
{
	queue< node*> q;
	q.push(root);
	while(!q.empty())
	{
		node *p = q.front();
		q.pop();
		printf("%d",p->data);
		if(p->lchild != NULL)
		{
			q.push(p->lchild);
		}
		if(p->rchild != NULL)
		{
			q.push(p->rchild);
		}
	}
}