ツリー遍歴(反復)

まず,二叉木の先順遍歴について,まず彼のアクセス順を検討する遍歴順はV|L|Rであるため,直接再帰版を採用することができる.

pre(Tree &root){
visit(root)
pre(root->left)
pre(root->right)
}

その法則をよく観察すると、スタック構造に類似した動作が発見されるのは難しくない(結局、再帰的な別のレベルもスタックで実現される).

stack s;
pre (Tree &root){
if(root)
s.push(root);
while(s!empty()){
Tree tem =s.top();
visit(tem);
s.pop();
if(tem->right!=null)s.push(tem->right);
if(tem->left!=null)s.push(tem->left);
}
}

コードの中のスタックの順序をよく理解すると~ポップアップするたびにスタックの頂点がアクセスされることがわかります~スタックの順序によって~先の順序にぴったり合っていることがわかります~それから、中の順序の遍歴~中の順序の遍歴の遍歴の順序がL|V|Rであることを感じてみましょうまず再帰版を見てみましょう

in(tree& root){
in(root->left);
visit(root);
in(root->right);
}

その順序は理解に難くありません:まず左の最下層~に再帰してからL|V|Rでアクセスしますが、ここのアクセスはよく理解できないかもしれません~図を描いてもいいです~だからこれは反復版のシーケンス遍歴のコードに戻ります

goleftBranch(Tree* x,stack s ){while(x){s.push(x);x=x->left;}}
stack s;
in(Tree &root){
while(true){
goleftBranch(root,s);
if(s.empty())break;
tem=s.pop();//          top  pop  1
visit(tem->data);
if(hasRightChild(tem))root=tem->right;
}
}

一方、ツリーの後順は、その順序L|R|V再帰バージョンコードを遍歴する

post(Tree x){
post(x->left);
post(x->right);
visit(x);
}

その反復版の実装については、そのアクセス順序の特殊性から~whileループは、前のシーケンスではなく中シーケンスに類似している.
したがって、中順のgoleft操作も使用できます.
post(Tree * x){stack s;while (true){goleftBranch(x,s);tem=s.pop();visit(x->data);if(hasrightchild(tem.parent))x=tem.parent.right;}}
実际には、右兄弟ノードがあるかどうかを书いて、オブジェクト向けの思想を発挥することを简単にすることができます~もう一つの遍歴は、ツリーの階層遍歴~トップダウン~左から右へ~階層遍歴をよく観察する思想に対して発见するのは难しくありません~これは、スタックと対立するもう一つのデータ构造-キュー用キューに似ていて、ツリーの階層遍歴~伪コードは次のとおりです.

level(Tree * x){
queue q;
q.enqueue(x);
whlie(!q.empty()){
x = q.top();
visit(x);
q.dequeue();
if(x.hasleft-child)q.enqueue(x->left);
if(x,hasright-child)q.enqueue(x->right);
}
}