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

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

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

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

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

二分探索木は、比較的小さな値が左側のノードに格納され、より大きな値が右側のノードに格納される特別な種類の二分木です。この機能により、数値データと非数値データ (単語や文字列など) の両方の検索が非常に効率的になります。

function Node(data,left,right){//结点类
    this.data=data;
    this.left=left;
    this.right=right;
    this.show=show;
}
function show(){//显示节点中数据
    return this.data;
}

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 サイトの他の関連記事を参照してください。