ホームページ >ウェブフロントエンド >jsチュートリアル >JavaScript バイナリ ツリー (二分探索ツリー) の詳細な紹介

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

不言
不言転載
2019-01-08 10:15:582972ブラウズ

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

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

バイナリ ツリー

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

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

  • ルート ノード: バイナリ ツリーの最上位ノード

  • ブランチノード: ルート ノードに加えてリーフ ノードがあります

  • リーフ ノード: それ自体を除き、他の子ノードはありません

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

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

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

    #i=1 の場合、A ルート ノードのみ、2^(i-1) = 2^0 = 1
A深さ k の二分木には最大 2^k-1 ノード
    • #i=2, 2^k-1 = 2^2 - 1 = 3 ノード
    任意の木 二分木 T について、要約点の数が n0、次数 2 (部分木の数が 2) のノードの数が n2 の場合、n0=n2 1
  • ツリーとバイナリ ツリーの 3 つの主な違い

      ツリー内のノードの数は少なくとも 1 ですが、ノードの数は少なくとも 1 です。バイナリ ツリーのノードの最大次数は 0
    • ツリー内のノードの最大次数 (ノード数に制限はありません) ですが、バイナリ ツリーのノードの最大次数は です。 2
    • ツリーのノードは左右に分割されていませんが、二分木のノードは左右に分割されています
    • # #バイナリ ツリーの分類

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

      完全バイナリ ツリー: 深さ k のツリーと深さ k のバイナリ ツリー2^k - 1 ノードは完全なバイナリ ツリーと呼ばれます
    • 完全なバイナリ ツリー: 完全なバイナリ ツリーとは、最後の層の左​​側がいっぱいで、右側が完全であることを意味します。満杯か満杯でないか、残りのレベルが満杯であるバイナリ ツリーは完全バイナリ ツリーと呼ばれます (完全バイナリ ツリーは完全バイナリ ツリーでもあります)

    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是我们要插入的节点,它插入的具体步骤:

    1. 跟根节点12做比较,比12大,所以我们确定了,这个节点是往右子树插入的

    2. 而根节点的右边已经有节点,那么跟这个节点18做比较,结果小于18所以往18的左节点找位置

    3. 而18的左节点也已经有节点了,所以继续跟这个节点做比较,结果小于16

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

    声明:
    この記事はsegmentfault.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。