非再帰的な二叉木のJavaScript版の遍歴を実現
14196 ワード
二叉樹の血涙に満ちた一日について
非再帰的な方法で二叉樹を実現して、本当に多くの脳細胞が死んで、私があまりにも料理したのかもしれません
タイトルの説明:1つのツリーの前、中、後、階層を非再帰的に符号化します.
入力説明:1行目の正の整数n(1<=n<=100)は、ツリーにn個のノードがあることを示す.次にn行、i行目の2つの整数li,ri(0<=li,ri<=n)は、i番目のノードの左息子と右息子をそれぞれ表し、0は空を表す.保証ルートは1で、入力が合法的な二叉木であることを保証します.
出力説明:4行の第1の動作の2つのツリーの前順の遍歴を出力します.第2の動作におけるシーケンス遍歴;第3の行為の後順に遍歴する.第4の動作階層が遍歴する.各行はn個の数を出力し、この方式で遍歴したノードの順序を表し、隣接する2つの数の間に1つのスペースで隔てられている.
入力例:
5 3 2 0 5 0 4 0 0 0 0
出力例:
1 3 4 2 5 3 4 1 2 5 4 3 5 2 1 1 3 2 4 5
入力した例は一定の処理が必要です.処理が完了して得られたのは木です.
この木を遍歴する.
以下に、この日と二叉樹が遍歴した愛憎の情仇を記す.
前順遍歴とは、先根遍歴、先根ノード、後左サブツリー、それから右サブツリーです.再帰でない場合はスタックの構造を利用します.1.(ルートノード)ルートからスタックに入る.2.(後ろの左のサブツリー)左ノードをスタックの左ノードに連続して巡回する.3.(さらに右のサブツリー)現在のノードに左ノードがない場合は、スタックを出て、現在のポインタをスタックの上部ノードに向け、右ノードに向けて右のサブツリーを巡り始めます.PS:現在のポインタが指すノードが存在する限り、ここに遍歴することを示し、そのノードをresに入れ、遍歴順序を示す.
中序遍歴は中根遍歴、すなわち左サブツリー、後ルート、最後右サブツリーである.再帰ではなく、スタックが使用されます.1.常に左に遍歴し、スタックに入るすべての通過ノード.2.現在のポインタが空の場合、スタックを出て、ポインタがスタックノードを指し、resにノードを入れ、ノードの右の子供をスタックに入れます.針が右の子を指す.3.現在のポインタが空で、スタックが空の場合は、ループが完了したことを示します.
後順遍歴とは後根遍歴で,まず左サブツリー,後右サブツリー,さらにルートノードである.非再帰的な実装では、スタックを使用する必要があります.しかし、後序には簡単な考え方があり、前序遍歴との関係を利用することである.後序遍歴とは、先右後左の先(前)序遍歴である.1.ルートノードがスタックに入る.2.左ノードがスタックに入ります.3.最後に右ノードがスタックに入ります.PS:スタックトップ要素を指すたびに.並出桟スタックトップは、各ラウンドの右ノードです.だから先右後左です.
特殊な点を階層的に遍歴するには、先に出る必要があります.上から下へ、左から右への順にストレージ構造に入るためですが、左から右へ上から下へ左右のノードを遍歴する必要があるので、キューが必要で、先に出る必要があります.
ps:データ処理部分のコードが必要な人がいたら、メッセージを残してください.必要があればまた貼ります.
非再帰的な方法で二叉樹を実現して、本当に多くの脳細胞が死んで、私があまりにも料理したのかもしれません
タイトルの説明:1つのツリーの前、中、後、階層を非再帰的に符号化します.
入力説明:1行目の正の整数n(1<=n<=100)は、ツリーにn個のノードがあることを示す.次にn行、i行目の2つの整数li,ri(0<=li,ri<=n)は、i番目のノードの左息子と右息子をそれぞれ表し、0は空を表す.保証ルートは1で、入力が合法的な二叉木であることを保証します.
出力説明:4行の第1の動作の2つのツリーの前順の遍歴を出力します.第2の動作におけるシーケンス遍歴;第3の行為の後順に遍歴する.第4の動作階層が遍歴する.各行はn個の数を出力し、この方式で遍歴したノードの順序を表し、隣接する2つの数の間に1つのスペースで隔てられている.
入力例:
5 3 2 0 5 0 4 0 0 0 0
出力例:
1 3 4 2 5 3 4 1 2 5 4 3 5 2 1 1 3 2 4 5
入力した例は一定の処理が必要です.処理が完了して得られたのは木です.
この木を遍歴する.
以下に、この日と二叉樹が遍歴した愛憎の情仇を記す.
ぜんじゅんかん遍歴
前順遍歴とは、先根遍歴、先根ノード、後左サブツリー、それから右サブツリーです.再帰でない場合はスタックの構造を利用します.1.(ルートノード)ルートからスタックに入る.2.(後ろの左のサブツリー)左ノードをスタックの左ノードに連続して巡回する.3.(さらに右のサブツリー)現在のノードに左ノードがない場合は、スタックを出て、現在のポインタをスタックの上部ノードに向け、右ノードに向けて右のサブツリーを巡り始めます.PS:現在のポインタが指すノードが存在する限り、ここに遍歴することを示し、そのノードをresに入れ、遍歴順序を示す.
var pretraver=function(pRoot){
var res=[];
var pCur=pRoot;
var stack=[];
stack.push(pRoot);
while(stack.length!=0){
if(pCur){
res.push(pCur.val);
stack.push(pCur);
pCur=pCur.left;
}else{
pCur=stack.pop();
pCur=pCur.right;
}
}
return res;
}
ちゅうかんじゅんかん遍歴
中序遍歴は中根遍歴、すなわち左サブツリー、後ルート、最後右サブツリーである.再帰ではなく、スタックが使用されます.1.常に左に遍歴し、スタックに入るすべての通過ノード.2.現在のポインタが空の場合、スタックを出て、ポインタがスタックノードを指し、resにノードを入れ、ノードの右の子供をスタックに入れます.針が右の子を指す.3.現在のポインタが空で、スタックが空の場合は、ループが完了したことを示します.
var intraver=function(pRoot){
var pCur=pRoot;
var res=[];
var stack=[];
stack.push(pCur);
var done=true;
while(!done){
if(pCur){
stack.push(pCur);
pCur=pCur.left;
}else{
if(stack.length!=0){
pCur=stack.pop();
res.push(pCur.val);
pCur=pCur.right;
}else{
done=false;
}
}
}
return res;
}
あとじゅんかん遍歴
後順遍歴とは後根遍歴で,まず左サブツリー,後右サブツリー,さらにルートノードである.非再帰的な実装では、スタックを使用する必要があります.しかし、後序には簡単な考え方があり、前序遍歴との関係を利用することである.後序遍歴とは、先右後左の先(前)序遍歴である.1.ルートノードがスタックに入る.2.左ノードがスタックに入ります.3.最後に右ノードがスタックに入ります.PS:スタックトップ要素を指すたびに.並出桟スタックトップは、各ラウンドの右ノードです.だから先右後左です.
var lasttraver=function(pRoot){
var pCur=pRoot;
var stack=[];
var res=[];
stack.push(pCur);
while(stack.length!=0){
pCur=stack.pop();
res.push(pCur.val);
if(pCur){
pCur=pCur.left;
stack.push(pCur);
}else{
pCur=pCur.right;
stack.push(pCur)
}
}
return res;
}
層ごとに遍歴する.
特殊な点を階層的に遍歴するには、先に出る必要があります.上から下へ、左から右への順にストレージ構造に入るためですが、左から右へ上から下へ左右のノードを遍歴する必要があるので、キューが必要で、先に出る必要があります.
var leveltraver=function(pRoot){
var pCur=pRoot;
var queue=[];
queue.push(pCur);
var res=[];
while(queue.length!=0){
res.push(queue.shift().val);
if(pCur.left){
queue.push(pCur.left);
}
if(pCur.right){
queue.push(pCur.right);
}
pCur=queue[queue.length-1];
}
return res;
}
ps:データ処理部分のコードが必要な人がいたら、メッセージを残してください.必要があればまた貼ります.