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