JavaScript二分探索木の定義と使用例

この記事では、JavaScript データ構造の二分探索木の定義と表現方法を主に紹介し、二分探索木の概念と特徴、および作成、挿入、走査などの操作に関連する JavaScript の実装手法について簡単に説明します。必要な友達はそれを参照してください

この記事では、JavaScript データ構造の二分探索木の定義と表現方法を例を用いて説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

ツリーは、データを階層的に格納する非線形データ構造です。ツリーは、階層関係を持つデータを格納するために使用されます。たとえば、ファイル システム内のファイルは、順序付きリストを格納するためにも使用されます。ここでは特別な種類のツリー、つまり二分木について研究します。これらの基本的なデータ構造よりもツリーが選択された理由は、バイナリ ツリーでの検索は非常に高速で (リンク リストでの検索は高速ではありません)、バイナリ ツリーへの要素の追加または削除は (配列への要素の追加または削除の間) 非常に高速であるためです。そうではありません）そうです）。

ツリーは n 個のノードの有限集合です。一番上がルートで、下がルートのサブツリーです。ツリー ノードには、データ要素とそのサブツリーを指す枝が含まれます。ノードが所有する部分木をノードの次数と呼びます。次数 0 のノードは、葉 または 端末ノード と呼ばれます。次数が 0 以外のノードは、非終端ノード または 分岐ノード と呼ばれます。 ツリーの次数は、ツリー内の各ノードの次数の最大値です。ノードの階層は、レベル 0 であるルートから開始して定義されます。ツリー内のノードの最大レベルは、ツリーの 深さ または 高さ と呼ばれます。

バイナリ ツリーは、2 つ以下の子ノードを持つ特別な種類のツリーです。バイナリ ツリーには、バイナリ ツリーに対する一部の操作を非常に効率的にする特別な計算特性があります。子ノードの数を 2 に制限することで、ツリー内のデータを挿入、検索、削除する効率的なプログラムを作成できます。

JavaScript を使用してバイナリ ツリーを構築する前に、木に関する 2 つの新しい用語を辞書に追加する必要があります。親ノードの 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重新开始判断
        }
      }
    }
}

以上がJavaScript二分探索木の定義と使用例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。