ツリーの遍歴(再帰と非再帰)

本論文では,前シーケンス(preorder),中シーケンス(inorder),後シーケンス(postorder),層シーケンス(level order)を含む二叉木の一般的な遍歴方式のコード(Java)実装について議論し,再帰および非再帰の実装方式をさらに考慮する.
再帰的な実装方法は比較的簡単であるが、再帰的な実行方法は毎回新しいメソッド呼び出しスタックを生成するため、再帰レベルが深いとメモリオーバーヘッドが大きくなり、それに比べて非再帰的な方法ではこの問題を回避することができる.再帰ループは容易に実現され、非再帰はそれほど簡単ではなく、非再帰呼び出しは本質的にスタックを維持することによって、再帰呼び出しの方法をシミュレートしてスタックを呼び出す行為である.
その前に、ノードのデータ構造を簡単に定義します.
ツリーノードは最大2人の息子のみであり,1つのノードの値を保存し,実験の便宜上intと仮定した.同時に、JavaのSystem.out.printメソッドを直接使用してノード値を出力し、遍歴結果を表示します.

1
2
3
4
5
6
7
8
9

public class Node {  public int value;  public Node leftNode;  public Node rightNode;   public Node(int i) {  value = i;  }  } 

詳細コードはリンクを参照:BSTとその様々な便利な詳細な実装コード
ぜんじゅんかん遍歴
再帰的な実装
再帰的な実装は簡単で、あるノードにアクセスするたびに、ノード値を出力してから、左の息子、右の息子に対して順次遍歴を呼び出す方法です.コードは次のとおりです.

1
2
3
4
5
6
7

public void preOrderTrav(Node n) {  if (n != null) {  System.out.print(n.value + " ");  preOrderTrav(n.leftNode);  preOrderTrav(n.rightNode);  } } 

非再帰調実装
方法1

1
2
3
4
5
6
7
8
9
10
11
12

public void preOrderTravNoRecur(Node n) {  Stack<Node> stack = new Stack<Node>();  stack.add(root);  while (!stack.empty()) {  Node t = stack.pop();  System.out.print(t.value + " ");  if (t.rightNode != null)  stack.add(t.rightNode);  if (t.leftNode != null)  stack.add(t.leftNode);  } } 

スタックを維持し、ルートノードをスタックに押し込む方法を説明します.その後、スタックからスタックトップのノードを読み出すたびに、ノードへのアクセスとして、そのノードの息子ノードを右から左の順にスタックに押し込み、再帰シミュレーションを実現する.
このスタックを解析する再帰戦略は良好な拡張性を備えておらず,他の遍歴方式ではこの戦略は使用できない.実際には、プログラム呼び出しスタックのシミュレーションではなく、現在のノードに先にアクセスした後、再帰的に息子ノードに対する遍歴を呼び出し、息子ノードの遍歴が終了した後に振り返って現在のノードを処理する必要はありません.したがって,シミュレーションの再帰においても,以前の呼び出しスタック情報を格納する必要はなく,将来のサブノードを生成するアクセス計画と同様にすればよい.
方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public void preOrderTravNoRecurII(Node n) {  System.out.println("No Recursive: ");  Stack<Node> s = new Stack<Node>();  while (n != null | !s.empty()){  while (n!=null ){  System.out.print(n.value + " ");  s.add(n);  n = n.leftNode;  }  n = s.pop();  n = n.rightNode;  }  System.out.println(); } 

説明1.スタックsと現在のノードnを維持する.初期にnをルートノードに割り当てます.2.現在のノードnの左サブチェーン上のノードに1つずつアクセスし、左の息子がいないまでスタックに押し込む.3.スタックトップのノードを取り出し、nをそのノードの右の息子に割り当てる.4.スタックが空で、現在のノードも空になるまで、2、3を繰り返します.
この方法を解析して,再帰的前シーケンス遍歴におけるプログラム呼び出しスタックの挙動過程をシミュレートした:呼び出しスタックでは,左息子がいないまで左息子チェーンに再帰的に入り,右息子に対する処理に入る.再帰メソッドの呼び出しスタックとは異なり、内層whileループは、再帰メソッドにおける左サブチェーン上のすべてのノードに対する再帰プロセスを集約する.
ちゅうかんじゅんかん遍歴
再帰的な実装

1
2
3
4
5
6
7

public void inorderTrav(Node n) {  if (n != null) {  inorderTrav(n.leftNode);  System.out.print(n.value + " ");  inorderTrav(n.rightNode);  } } 

非再帰的実装

1
2
3
4
5
6
7
8
9
10
11
12
13

public void inorderTravNoRecu(Node n) {  System.out.println("No Recursive: ");  Stack<Node> s = new Stack<Node>();  while (n != null | !s.empty()){  while (n!=null ){  s.add(n);  n = n.leftNode;  }  n = s.pop();  System.out.print(n.value + " ");  n = n.rightNode;  } } 

説明1.スタックsと現在のノードnを維持する.初期にnをルートノードに割り当てます.2.現在のノードnの左サブチェーン上のノードを、左の息子がいないまでスタックに1つずつ押し込む.3.スタックトップのノードを取り出し、そのノードにアクセスし、nをそのノードの右の息子に割り当てる.4.スタックが空で、現在のノードも空になるまで、2、3を繰り返します.
分析前シーケンス遍歴の非再帰的実現方法2は類似している.唯一の違いは、現在のノードにアクセスするタイミングです.前のシーケンスはスタックに入る前にアクセスし、中のシーケンスはスタックを出る後にアクセスします.
あとじゅんかん遍歴
再帰的な実装

1
2
3
4
5
6
7

public void postOrderTrav(Node n) {  if (n != null) {  inorderTrav(n.leftNode);  inorderTrav(n.rightNode);  System.out.print(n.value + " ");  }  } 

非再帰的実装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public void postOrderTravNoRecu(Node n) {  Stack<Node> stack = new Stack<Node>();  int[] flag = new int[max];   while (n != null) {  stack.push(n);  flag[stack.size()] = 0;  n = n.leftNode;  }   while (!stack.empty()) {  n = stack.peek();  while (n.rightNode != null && flag[stack.size()] == 0) {  n = n.rightNode;  flag[stack.size()] = 1;  while (n != null) {  stack.push(n);  flag[stack.size()] = 0;  n = n.leftNode;  }  n = stack.peek();  }  n = stack.pop();  System.out.print(n.value + " ");  }   } 

説明1.スタックstack、現在のノードn、およびタグ配列flagを維持する.ルートノードの左サブチェーン上のすべてのノードをstackに押し込み、値が0.2に設定されているため、タグ配列をスタックの上部に割り当てます.ノードに右の子があり、処理されていない場合(マーキング配列で判定される)、右の子ツリーのルートノードとその左の子はすべてスタックに押し込まれます.3.現在のノードを付志偉スタックのトップのノードにアクセスし、そのノードをスタックからpopします.4.スタックが空になるまで2、3の2ステップをループします.
非再帰法でスタックシミュレータでスタックを呼び出すことを解析し,最も大きな問題は再帰法が置かれている状態をシミュレートすることである.エンコードメンテナンスのスタックはノードを記録できますが、ノードをどのように処理するかは記録できません.ここでは,ノードの右サブツリーがアクセスされたか否かを記録するためにflag配列を用い,各ノードにアクセスする際に,左右サブツリーの処理が完了したことを保証した(左サブチェーンを主線として先に押し込み,スタック内の各ノードを処理する際に右サブを押し込むことで実現する).
層順遍歴
再帰メソッドを使用できません
レイヤシーケンスループは他のループとは異なり、再帰的な実装は使用できません.
反証法は,Aノードに対する層順再帰が実現できれば,Aノードに対する処理中に,再帰すべき2人の息子BとCに対してそれぞれ層順遍歴が呼び出されることを実証した.この場合、BとCの同じ階層の息子を集中時間で遍歴させることはできない.言い換えれば、Bの第1層の息子はBの呼び出しで遍歴され、Cの第1層の息子はCの呼び出しで遍歴され、これは分離される.成立しない.
非再帰的アプローチ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public void levelOrderTrav(Node n) {  System.out.print("Level OrderTrav: ");   Queue<Node> q = new LinkedList<Node>();  q.add(n);  while (q.size() != 0) {  n = q.poll();  System.out.print(" " + n.value);  if (n.leftNode != null)  q.add(n.leftNode);  if (n.rightNode != null)  q.add(n.rightNode);   } } 

解析は1つのキューで層シーケンス遍歴を実現し,トポロジーソートにおいてもこの方法が有用である.
まとめ
非再帰的に実装されるコードは、再帰的に実装される直感的ではない.そのコアは、ステータスを保存するためにスタックを維持し、スタックを呼び出す方法が多すぎてメモリ領域を浪費することを回避することです.