木データ構造によるブラッシュアップ

以下はバイナリサーチツリーです.すべての円はノードと呼ばれ、各ノードは2つの他のノードに接続することができます.そういうわけで、彼らは二進木と呼ばれています、彼らは2「子供」ノードを持っています、そして、それは木のように見えます!

左の子ノードは常に親の値より小さいか等しいです、そして、右は常により大きいか等しいです.いくつかの実装では、左または右のノードだけが親に等しくなります.個人的に、私は平等なノードを置くのが好きです😁
ここでは、Python 3を使ったバイナリ検索ツリーです.

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

左と右のツリーのデフォルト値はNULL/Noneです、そして、デフォルトVALは0です.

横断線

各traversalのために、私はそれがルート(一番上の)から始まる二進木を通してどのように動くかの簡単な説明をするつもりです.次に、Pythonを使用してtraversalのコードを表示し、最後に、プログラムがツリーを移動する方法を視覚化します.また、GIFサイズはあまりに大きくなっていて、私はそれを短くしなければならなかったので、GIFはすべての木全体を通過することなく早く終了します🤷‍♂️.
最初の3は非常に似ており、1行のコードだけで異なりますが、非常に異なる結果を与える!私は、彼らを横断三つ子と呼びます.

順に

このメソッドは「順序で」ツリーを移動します.すべてのノードの値を最小から最大に順番に印刷することを意味します.
再帰を使用すると、関数は左のサブツリーに自分自身を呼び出し、現在の値を出力し、右のサブツリーにそれ自体を呼び出します.
その結果、ツリーの値を出力します.順序で.

def in_order(node):
    if node == None:
        return
    in_order(node.left)
    print(node.val)
    in_order(node.right)

深さ優先探索

深さ優先探索は木とグラフのための古典的な横断法です.それが最初の現在のノード、次に、左右の子ノードで動くので、このメソッドはpre - order横断です.
深さ優先探索は一般的な横断と同様に木のコピーを作るのに非常に人気があります.

def dfs(node):
    if node == None:
        return
    print(node.val)
    dfs(node.left)
    dfs(node.right)

郵便為替

横断三つ子の最後それは最初に左と右の子ノード、次に現在のノードで動作します.
それが下から行くように、post - orderは木を削除するのに非常に役に立ちます.

def post_order(node):
    if node == None:
        return
    post_order(node.left)
    post_order(node.right)
    print(node.val)

幅の最初の検索

これは少しトリッキーであり、キューを使用してのみ行うことができます.それは再帰で可能かもしれませんが、反復的に理解するのは簡単です.それは、ノードがノードに追加されるようにツリーを通過するので、横断するときにキューを使用します.その結果、ツリーを通ってレベルごとに行きます.これは、同様にグラフで人気の検索アルゴリズムを幅広く最初に検索します.
私はこの1つのアニメーションを作ることができなかったが、私はノードがどのような順序で表示されるかを示すために番号付きの図を作成しました!

# deque is a python queue library
from collections import deque

def bfs(root):
    q = deque([root])
    while len(q) > 0:
        node = q.popleft()
        print(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

結論

これらの4つの横断的な方法を理解することによって、あなたは二分木にかかわるほとんどのインタビュー問題を説明することができます.あなたが正しい横断方法を知っているならば、彼らの多くは簡単に解決可能な塊に分解されることができます!あなたは正確な方法論に興味があるなら、私はすぐに出てくるガイドを持っている!私は、それがバイナリ木問題を解くのに必要な唯一の資源であることを望みます.
また、すべてのアニメーションはhttp://btv.melezinek.cz/binary-search-tree.htmlの礼儀だった.場合は、アニメーションを再生する場合は、それらをチェックアウトしてください!

ところで、ガイドを作っています

私はLeetCode(したがって、インタビューのほとんどすべてのバイナリツリーの問題を解決する方法についてのガイドを作っている)!私の旅に加わる
ここでスニークピーク😃


アブディサラン

アイデア:私はLeetCode上のすべての141のバイナリツリーの質問を解決するつもりだし、どのように私は1441の理由のうち18を行ったことを解決するためのガイドを公開するつもりですか?正直に何かそれは私の次の仕事ハント年のための良いノートになります.
午後19時30分- 2020年8月30日
0
5