二叉木遍歴非再帰C++実現
ツリーは非常に重要なデータ構造であり、他の多くのデータ構造はツリーの基礎に基づいて発展してきた.二叉木には,前序,中序および後序の3つの遍歴方法がある.ツリーの定義自体が再帰定義であるため,再帰的手法を用いてツリーの3つの遍歴を実現することは理解しやすいだけでなく,コードが簡潔である.ツリーの遍歴に対して非再帰的な方法を採用すると,スタックを用いてシミュレーションを行う.3つのループでは,前シーケンスと中シーケンスの非再帰アルゴリズムが容易に実現され,非再帰後シーケンスのループは相対的に難しい.
一.ぜんじゅんかん遍歴
前順ループは、「ルートノード-左子供-右子供」の順にアクセスします.
1.再帰的実現
void preOrder1(BinTree *root) //
{
if(root!=NULL)
{
cout<<root->data<<" ";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
} 2.非再帰的実現
前の順序でアクセスする順序に従って、ルートノードを優先し、左の子供と右の子供をそれぞれアクセスします.すなわち、いずれかのノードについては、ルートノードと見なすことができるので、直接アクセスすることができ、アクセスが完了した後、左の子供が空でなければ、同じルールで左のサブツリーにアクセスすることができる.左サブツリーにアクセスすると、右サブツリーにアクセスします.したがって、その処理手順は次のとおりです.
いずれかのノードPについて:
1)ノードPにアクセスし、ノードPをスタックに入れる.
2)ノードPの左の子が空であるかどうかを判断し、空であれば、スタックトップノードを取り、スタックアウト操作を行い、スタックトップノードの右の子を現在のノードPとして1)にループする.空でなければ、Pの左の子を現在のノードPにする.
3)PがNULLでスタックが空になるまで、遍歴は終了する.
void preOrder2(BinTree *root) //
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
} 二.ちゅうかんじゅんかん遍歴
中順遍歴は「左の子-ルートノード-右の子」の順にアクセスします.
1.再帰的実現
void inOrder1(BinTree *root) //
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<<root->data<<" ";
inOrder1(root->rchild);
}
} 2.非再帰的実現
中順にループする順序に従って、いずれかのノードについて左の子を優先的にアクセスし、左の子ノードを1つのノードと見なし、左の子ノードが空のノードに遭遇するまで左の子ノードにアクセスし続け、同じルールで右の子ツリーにアクセスします.したがって、その処理手順は次のとおりです.
いずれのノードPについても、
1)左の子が空でない場合、Pをスタックに入れ、Pの左の子を現在のPにし、現在のノードPに対して同じ処理を行う.
2)左の子が空である場合、スタックトップ要素を取り、そのスタックトップノードにアクセスし、現在のPをスタックトップノードの右の子とする.
3)PがNULLになり、スタックが空になるまで遍歴が終了する
void inOrder2(BinTree *root) //
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
} 三.あとじゅんかん遍歴
後順ループは、「左-右-子-ルートノード」の順にアクセスします.
1.再帰的実現
void postOrder1(BinTree *root) //
{
if(root!=NULL)
{
postOrder1(root->lchild);
postOrder1(root->rchild);
cout<<root->data<<" ";
}
} 2.非再帰的実現
後順遍歴の非再帰的実現は3つの遍歴方式の中で最も難しいものである.ルートノードにアクセスするには、左の子供と右の子供がアクセスされ、右の子供の前に左の子供がアクセスすることを保証するため、プロセスの制御に難題があります.2つの考え方を紹介します.
1つ目の考え方:いずれかのノードPについて、スタックに入れ、左の子ツリーに沿って左の子ツリーに沿って左の子がいないノードが検索されるまで、そのノードがスタックの上部に表示されるが、このときスタックから出てアクセスできないため、右の子はアクセスされる.したがって、次に同じルールに従って右のサブツリーを同じ処理し、右の子供にアクセスしたときにスタックの上部にノードが表示され、スタックを出てアクセスできます.これにより、正しいアクセス順序が保証されます.このプロセスでは、各ノードがスタックトップに2回表示され、スタックトップに2回目に表示された場合にのみアクセスできることがわかります.したがって、ノードがスタックの上部に初めて現れるかどうかを識別する変数を複数設定する必要があります.
void postOrder2(BinTree *root) //
{
stack<BTNode*> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) // ，
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else //
{
cout<<temp->btnode->data<<" ";
p=NULL;
}
}
}
} 第2の考え方:ルートノードは左の子供と右の子供が訪問した後にアクセスできることを保証するため、いずれかのノードPについては、先にスタックに入れる.Pに左の子と右の子が存在しない場合は、直接アクセスできます.あるいはPには左または右の子が存在するが,左および右の子が既に訪問されている場合,同様にノードに直接アクセスすることができる.上記の2つ以外の場合、Pの右の子と左の子を順番にスタックに入れることで、スタックトップ要素を取るたびに左の子が右の子の前に訪問され、左の子と右の子がルートノードの前に訪問されることを保証します.
void postOrder3(BinTree *root) //
{
stack<BinTree*> s;
BinTree *cur; //
BinTree *pre=NULL; //
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<<cur->data<<" "; //
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
} 四.プログラム全体の完全なコード
#include
>data<<";s.push(p);p=p>>lchild;}if(!s.empty()) { p=s.top(); s.pop(); p=p->rchild; } } } void inOrder 2(BinTree*root)/非再帰中順遍歴{stack