JavaScript バイナリツリー (二分探索ツリー) の詳細な紹介-jsチュートリアル-php.cn

この記事では、JavaScript バイナリツリー (バイナリサーチツリー) について詳しく説明します。必要な方は参考にしてください。

前回の記事で書いたバイナリヒープをまだ読んでいない人もいるかもしれないので、バイナリツリーの基本的な概念を読んだことがあればここにコピーします。バイナリツリーの基本概念については無視してください。また、リンクリストのデータ構造がよくわからない場合は、以前に書いた js データ構造を参照することをお勧めします。

バイナリツリー

バイナリツリー (バイナリツリー) は、各ノードが最大 2 つの分岐ノードを持つことを特徴とする木構造です。バイナリツリーは、通常、ルートノード、分岐ノード、および分岐ノードで構成されます。葉のノード。各ブランチノードはサブツリーと呼ばれることがよくあります。

JavaScript バイナリツリー (二分探索ツリー) の詳細な紹介

ルートノード: バイナリツリーの最上位ノード
ブランチノード: ルートノードに加えてリーフノードがあります
リーフノード: それ自体を除き、他の子ノードはありません

共通用語二分木では、親ノードと子ノードを使って説明することがよくあります。たとえば、図の 2 は 6 と 3 の親ノードであり、逆に 6 と 3 は子ノードです。 / 2

バイナリツリーの 3 つのプロパティ

バイナリツリーの i 番目のレベルには、最大 2^i-1 個のノードがあります

A深さ k の二分木には最大 2^k-1 ノード

任意の木二分木 T について、要約点の数が n0、次数 2 (部分木の数が 2) のノードの数が n2 の場合、n0=n2 1

ツリーとバイナリツリーの 3 つの主な違い

バイナリツリーは、完全バイナリツリーと完全バイナリツリーに分類されます

JavaScript バイナリツリー (二分探索ツリー) の詳細な紹介二分探索ツリー

二分探索ツリーは次のプロパティを満たします:

データのセット: 12,4,18,1,8,16,20

下の図からわかるように、左側の図は、それぞれの左側の子ノードが親ノードより小さく、右側の子ノードが親ノードより大きいです。同時に、左側のサブツリーのノードはルートノードより小さく、右側のサブツリーのノードはルートノードより大きくなります

JavaScript バイナリツリー (二分探索ツリー) の詳細な紹介二分探索木の主な操作:

#Search

Insert
Traverse (横断) )
二分探索ツリーの連鎖ストレージ構造

次の図から、通常、二分探索ツリーのノードには 4 つの各フィールドとデータ要素は、それぞれその左ノードと右ノードを指すポインタと、親ノードを指すポインタで構成されます。この格納構造は、一般に 3 方向リンクリストと呼ばれます。

JavaScript バイナリツリー (二分探索ツリー) の詳細な紹介コードを使用して二分探索ツリーのノードを初期化します:

親ノードparentへのポインター

左ノードへのポインタ left
右ノードへのポインタ right
aデータ要素 (キーと値にすることができます)

    class BinaryTreeNode {
        constructor(key, value){
            this.parent = null;
            this.left = null;
            this.right = null;
            this.key = key;
            this.value = value;
        }
    }

ログイン後にコピー

次に、コードを使用してバイナリ検索ツリーを初期化します

在二叉搜索树中我们会维护一个root指针，这个就相当于链表中的head指针，在没有任何节点插入的时候它指向空，在有节点插入以后它指向根节点。

    class BinarySearchTree {
        constructor() {
            this.root = null;
        }
    }

ログイン後にコピー

创建节点

    static createNode(key, value) {
        return new BinarySearchTree(key, value);
    }

ログイン後にコピー

插入操作

看下面这张图，13是我们要插入的节点，它插入的具体步骤：

跟根节点12做比较，比12大，所以我们确定了，这个节点是往右子树插入的
而根节点的右边已经有节点，那么跟这个节点18做比较，结果小于18所以往18的左节点找位置
而18的左节点也已经有节点了，所以继续跟这个节点做比较，结果小于16
刚好16的左节点是空的(left=null)，所以13这个节点就插入到了16的左节点

JavaScript バイナリツリー (二分探索ツリー) の詳細な紹介

通过上面的描述，我们来看看代码是怎么写的

定义两个指针，分别是p和tail，最初都指向root，p是用来指向要插入的位置的父节点的指针，而tail是用来查找插入位置的，所以最后它会指向null，用上图举个例子，p最后指向了6这个节点，而tail最后指向了null（tail为null则说明已经找到了要插入的位置）
循环，tail根据我们上面分析的一步一步往下找位置插入，如果比当前节点小就往左找，大则往右找，一直到tail找到一个空位置也就是null
如果当前的root为null，则说明当前结构中并没有节点，所以插入的第一个节点直接为跟节点，即this.root = node
将插入后的节点的parent指针指向父节点

    insert(node){
        let p = this.root;
        let tail = this.root;
        
        // 循环遍历，去找到对应的位置
        while(tail) {
            p = tail;
            // 要插入的节点key比当前节点小
            if (node.key <h3>查找</h3><p>查找就很简单了，其实和插入差多，都是去别叫左右节点的大小，然后往下找</p>

ログイン後にコピー

如果root = null, 则二叉树中没有任何节点，直接return，或者报个错什么的。
循环查找

    search(key) {
        let p = this.root;
        if(!p) {
            return;
        }
        
        while(p && p.key !== key){
            if(p.key<key><h3>遍历</h3>
<ul class=" list-paddingleft-2">
<li><p>中序遍历(inorder)：先遍历左节点，再遍历自己，最后遍历右节点，输出的刚好是有序的列表</p></li>
<li><p>前序遍历(preorder)：先自己，再遍历左节点，最后遍历右节点</p></li>
<li><p>后序遍历(postorder)：先左节点，再右节点，最后自己</p></li>
</ul>
<p>最常用的一般是中序遍历，因为中序遍历可以得到一个已经排好序的列表，这也是为什么会用二叉搜索树排序的原因</p>
<p>根据上面对中序遍历的解释，那么代码就变的很简单，就是一个递归的过程，递归停止的条件就是节点为null</p>
<ul class=" list-paddingleft-2">
<li><p>先遍历左节点-->yield* this._transverse(node.left)</p></li>
<li><p>遍历自己 --> yield* node</p></li>
<li><p>遍历左节点 --> yield* this._transverse(node.right)</p></li>
</ul>
<pre class="brush:php;toolbar:false">    transverse() {
        return this._transverse(this.root);
    }
    
    *_transverse(node){
        if(!node){
            return;
        }
        yield* this._transverse(node.left);
        yield node;
        yield* this._transverse(node.right)
    }

ログイン後にコピー

JavaScript バイナリツリー (二分探索ツリー) の詳細な紹介

看上面这张图，我们简化的来看一下，先访问左节点4，再自己12，然后右节点18，这样输出的就刚好是一个12，4，8

补充：这个地方用了generater，所以返回的一个迭代器。可以通过下面这种方式得到一个有序的数组，这里的前提就当是已经有插入的节点了

   const tree = new BinaryTree();
   //...中间省略插入过程
    
   // 这样就返回了一个有序的数组 
   var arr = [...tree.transverse()].map(item=>item.key);

ログイン後にコピー

完整代码

class BinaryTreeNode {
  constructor(key, value) {
    // 指向父节点
    this.p = null;

    // 左节点
    this.left = null;

    // 右节点
    this.right = null;

    // 键
    this.key = key;

    // 值
    this.value = value;
  }
}

class BinaryTree {
  constructor() {
    this.root = null;
  }

  static createNode(key, value) {
    return new BinaryTreeNode(key, value);
  }

  search(key) {
    let p = this.root;
    if (!p) {
      return;
    }

    while (p && p.key !== key) {
      if (p.key <h3>总结</h3><p>二叉查找树就讲完了哈，其实这个和链表很像的，还是操作那么几个指针，既然叫查找树了，它主要还是用来左一些搜索，还有就是排序了，另外补充一下，二叉查找树里找最大值和最小值也很方便是不是，如果你大致读懂了的话。</p><p class="comments-box-content"></p>

ログイン後にコピー

以上がJavaScript バイナリツリー (二分探索ツリー) の詳細な紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。