JavaScript バイナリ ツリーとさまざまなトラバーサル アルゴリズムの詳細な紹介

この記事は、javascript に関する関連知識を提供します。主に JavaScript バイナリ ツリーとさまざまなトラバーサル アルゴリズムの詳細を紹介します。この記事では、このトピックに関する詳細な紹介が提供されており、一定の参考価値があります。必要な方は参考にしていただければ幸いです。

[関連する推奨事項: JavaScript ビデオ チュートリアル 、Web フロントエンド ]

バイナリとはツリー

バイナリ ツリーは、次の図に示すように、各ノードが最大 2 つの子ノードのみを持つことができるツリーです。

#バイナリ ツリーには次の特徴があります:

i には 2^(i-1)

ノードしかありません。

レイヤー;
• このバイナリ ツリーの深さが k の場合、バイナリ ツリーには最大 2^k-1
ノードがあります;
• 空ではないバイナリ ツリーで、葉ノードの数を表すのに n0 を使用し、次数 2 の非葉ノードの数を n2
とすると、次のようになります。 2 つは関係
• n0 = n2 1 を満たします。 完全なバイナリ ツリーバイナリ ツリー内で、
リーフ ノードを除き、残りのノードの各次数が 2 である場合、バイナリ ツリーは完全なバイナリです。ツリー

,

下図のように

## 通常のバイナリの特性を満たすことに加えてツリーと同様に、完全なバイナリ ツリーには次の機能もあります。 特徴:

完全なバイナリ ツリーの

n 番目のレベルには 2^(n- 1)

ノード;

• k の深さの完全なバイナリ ツリーには 2^k-1 ノードが必要で、リーフ ノードの数は
2^(k-1)
• ;n ノードを持つ完全なバイナリ ツリーの深さは log_2^(n 1) です。
• 完全なバイナリ ツリーバイナリ ツリーが最後の層を削除した後の完全なバイナリ ツリーであり、最後のノードが左から右に
分散されている場合、このバイナリ ツリーは完全なバイナリ ツリーです。

次の図に示すように:

バイナリ ツリーのストレージ

バイナリ ツリーのストレージ 一般的な方法は 2 つあり、1 つは

配列ストレージ を使用する方法、もう 1 つはリンク リスト ストレージを使用する方法です。

配列ストレージ

配列を使用してバイナリ ツリーを保存します。完全なバイナリ ツリーが見つかった場合、保存順序は、図に示すように、上から下、左から右の順になります。次の図:

下に示すように、不完全なバイナリ ツリーの場合:

##必須 次の図に示すように、まず完全なバイナリ ツリーに変換してから保存します。ストレージスペースの無駄がはっきりわかります。

リンク リスト ストレージ

リンク リスト ストレージを使用すると、通常、バイナリ ツリーは以下に示すように 3 つの部分に分割されます。

この 3 つの部分は、左のサブツリーへの参照、ノードに含まれるデータ、右のサブツリーへの参照となり、格納方法は下図のようになります。

バイナリ ツリーに関連するアルゴリズム

次のアルゴリズムで走査に使用されるツリーは次のとおりです

:

// tree.js
const bt = {
  val: 'A',
  left: {
    val: 'B',
    left: { val: 'D', left: null, right: null },
    right: { val: 'E', left: null, right: null },
  },
  right: {
    val: 'C',
    left: {
      val: 'F',
      left: { val: 'H', left: null, right: null },
      right: { val: 'I', left: null, right: null },
    },
    right: { val: 'G', left: null, right: null },
  },
}
module.exports = bt

深さ優先トラバーサル

バイナリ ツリーの深さ優先トラバーサルは、ツリーの深さ優先トラバーサルと同じ考え方を持っています。その考え方は次のとおりです:

はルート ノードにアクセスします。

はルート ノードの

left にアクセスします。

ルート ノードにアクセスするには

right

2 番目と 3 番目のステップを繰り返します

• 実装コードは次のとおりです。

• const bt = {
    val: 'A',
    left: {
      val: 'B',
      left: { val: 'D', left: null, right: null },
      right: { val: 'E', left: null, right: null },
    },
    right: {
      val: 'C',
      left: {
        val: 'F',
        left: { val: 'H', left: null, right: null },
        right: { val: 'I', left: null, right: null },
      },
      right: { val: 'G', left: null, right: null },
    },
  }
  
  function dfs(root) {
    if (!root) return
    console.log(root.val)
    root.left && dfs(root.left)
    root.right && dfs(root.right) 
  }
  dfs(bt)
  /** 结果
  A B D E C F H I G
  */

  幅優先トラバーサル
• 実装アイデアは次のとおりです:
• キューを作成し、ルート ノードをキューに追加します

相手のキューを終了して

## にアクセスします# キューの先頭にある left と

right

を順番にキューに追加します

キューが空になるまで手順 2 と 3 を繰り返します

実装コードは次のとおりです:

• function bfs(root) {
    if (!root) return
    const queue = [root]
    while (queue.length) {
      const node = queue.shift()
      console.log(node.val)
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
    }
  }
  bfs(bt)
  /** 结果
  A B C D E F G H I
   */

• Pre-order traversal
• バイナリの pre-order traversal の実装アイデアツリーは次のとおりです: <ul> <li>访问根节点;</li> <li>对当前节点的左子树进行先序遍历；</li> <li>对当前节点的右子树进行先序遍历；</li> </ul> <p><strong>如下图所示：</strong></p> <p style="text-align:center"><img alt="" src="https://img.php.cn/upload/article/000/000/067/2e21b01585b271b13affdc606b633cfb-8.png"></p> <p><strong>递归方式实现如下：</strong></p><pre class="brush:js;">const bt = require(&amp;#39;./tree&amp;#39;) function preorder(root) { if (!root) return console.log(root.val) preorder(root.left) preorder(root.right) } preorder(bt) /** 结果 A B D E C F H I G */</pre><p><strong>迭代方式实现如下：</strong></p><pre class="brush:js;">// 非递归版 function preorder(root) { if (!root) return // 定义一个栈，用于存储数据 const stack = [root] while (stack.length) { const node = stack.pop() console.log(node.val) /* 由于栈存在先入后出的特性，所以需要先入右子树才能保证先出左子树 */ node.right &amp;&amp; stack.push(node.right) node.left &amp;&amp; stack.push(node.left) } } preorder(bt) /** 结果 A B D E C F H I G */</pre><h3>中序遍历</h3> <p><strong>二叉树的中序遍历实现思想如下：</strong></p> <ul> <li>对当前节点的左子树进行中序遍历；</li> <li>访问根节点;</li> <li>对当前节点的右子树进行中序遍历；</li> </ul> <p><strong>如下图所示：</strong></p> <p style="text-align:center"><img alt="" src="https://img.php.cn/upload/article/000/000/067/2e21b01585b271b13affdc606b633cfb-9.png"></p> <p><strong>递归方式实现如下：</strong></p><pre class="brush:js;">const bt = require(&amp;#39;./tree&amp;#39;) // 递归版 function inorder(root) { if (!root) return inorder(root.left) console.log(root.val) inorder(root.right) } inorder(bt) /** 结果 D B E A H F I C G */</pre><p><strong>迭代方式实现如下：</strong></p><pre class="brush:js;">// 非递归版 function inorder(root) { if (!root) return const stack = [] // 定义一个指针 let p = root // 如果栈中有数据或者p不是null，则继续遍历 while (stack.length || p) { // 如果p存在则一致将p入栈并移动指针 while (p) { // 将 p 入栈，并以移动指针 stack.push(p) p = p.left } const node = stack.pop() console.log(node.val) p = node.right } } inorder(bt) /** 结果 D B E A H F I C G */</pre><h3>后序遍历</h3> <p><strong>二叉树的后序遍历实现思想如下：</strong></p> <ul> <li>对当前节点的左子树进行后序遍历；</li> <li>对当前节点的右子树进行后序遍历；</li> <li>访问根节点;</li> </ul> <p><strong>如下图所示：</strong></p> <p style="text-align:center"><img alt="" src="https://img.php.cn/upload/article/000/000/067/22c7972cfbc281b5fff6fa9a742258c6-10.png"></p> <p><strong>递归方式实现如下：</strong></p><pre class="brush:js;">const bt = require(&amp;#39;./tree&amp;#39;) // 递归版 function postorder(root) { if (!root) return postorder(root.left) postorder(root.right) console.log(root.val) } postorder(bt) /** 结果 D E B H I F G C A */</pre><p><strong>迭代方式实现如下：</strong></p><pre class="brush:js;">// 非递归版 function postorder(root) { if (!root) return const outputStack = [] const stack = [root] while (stack.length) { const node = stack.pop() outputStack.push(node) // 这里先入left需要保证left后出，在stack中后出，就是在outputStack栈中先出 node.left &amp;&amp; stack.push(node.left) node.right &amp;&amp; stack.push(node.right) } while (outputStack.length) { const node = outputStack.pop() console.log(node.val) } } postorder(bt) /** 结果 D E B H I F G C A */</pre><p>【相关推荐：<a href="https://www.php.cn/course/list/17.html" target="_blank" textvalue="javascript视频教程">javascript视频教程</a>、<a href="https://www.php.cn/course/list/1.html" target="_blank">web前端</a>】</p>

以上がJavaScript バイナリ ツリーとさまざまなトラバーサル アルゴリズムの詳細な紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。