二叉検索ツリーの表示javascript


ツリーは非線形データ構造であり、階層的にデータを記憶する.ツリーは、ファイルシステム内のファイルなどの階層的関係を持つデータを格納するために使用される.ツリーはまた、シーケンステーブルを格納するために使用されます.ここでは特別な木を研究します.基本的なデータ構造ではなく、ツリーを選択するのは、二叉樹での検索が非常に速いからです.二叉樹に要素を追加または削除するのも非常に早いです.
木はn個の結点の有限集合である.一番上は根で、下は根の子樹です.ツリーのノードは、データ要素とそのサブツリーを指すいくつかの分岐を含む.結点がある子樹を結点といいます.度が0の結点を葉っぱまたは終端結点といいます.度が0でない結点を非端末結点または分岐結点と呼びます.木の度は樹内の各結点の度の最大値です.結点の階層はルートから定義され、ルートは0層目である.ツリーの中の接合点の最大の階層をツリーの深さまたは高さと呼びます.
二叉の木は特殊な木で、そのサブノードの数は二つを超えないです.二叉樹はいくつかの特殊な計算特性を持ち、それらより上のいくつかの動作が非常に効率的である.サブノードの個数を2に限定することで、効率的なプログラムをツリーに挿入、検索、削除することができます.
JavaScriptを使って二叉の木を作る前に、私たちの木に関する辞書に新しい名詞を二つ追加してください.1つの親ノードの2つのサブノードは、それぞれ左ノードと右ノードと呼ばれる.いくつかの二叉ツリーの実装において、左ノードは特定の値のセットを含み、右ノードは別のセットの特定の値を含む.二叉ルックアップツリーは特殊な二叉ツリーで、比較的小さい値は左ノードに保存され、大きな値は右ノードに保存されます.この特性は、検索の効率を高くし、数値型と非数値型のデータ、例えば単語と文字列についても同様である.
二叉検索ツリーはノードで構成されているので、Nodeオブジェクトを定義したいです.コードは以下の通りです.
function Node(data,left,right){//   
		this.data=data;
		this.left=left;
		this.right=right;
		this.show=show;
	}
	function show(){//       
		return this.data;
	}
このうち、leftとrightはそれぞれ左右の結点を指す.
次に、二叉検索ツリーのクラスを作成します.コードは以下の通りです.
function BST(){//  
		this.root=null;
		this.insert=insert;
		this.inOrder=inOrder;
		this.preOrder=preOrder;
		this.postOrder=postOrder;
	}
次にノードのコードを挿入します.小さいのを見て左に挿して、大きいのを右に挿します.コードは以下の通りです
function insert(data){//    
		var n=new Node(data,null,null);
		if(this.root==null){//     
			this.root=n;
		}else{
			var current=this.root;//       
			var parent;
			while(true){//                 
				parent=current;
				if(data<current.data){
					current=current.left;
					if(current==null){//       
						parent.left=n;
						break;
					}
				}else{
					current=current.right;
					if(current==null){//       
						parent.right=n;
						break;
					}//      ,   while    ,      parent      
				}
			}
		}
	}