非再帰的な二叉木のJavaScript版の遍歴を実現


二叉樹の血涙に満ちた一日について
非再帰的な方法で二叉樹を実現して、本当に多くの脳細胞が死んで、私があまりにも料理したのかもしれません
タイトルの説明: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:データ処理部分のコードが必要な人がいたら、メッセージを残してください.必要があればまた貼ります.