ノードは、リンクリストやツリーデータ構造などのデータ構造の基本単位です。ノードはデータを保持し、他のノードにリンクすることもできます。ノード間のリンクは、多くの場合、ポインタによって実装されます。

グラフ理論では、この画像はネットワークを簡略化して表したもので、各数字は異なるノードを表します。

ノードとツリー

サイズが 9、高さが 3 で、ルート ノードの値が 2 である単純な二分木。上記の木は不均衡であり、ソートされていません。

ノードは多くの場合、ツリー構造に配置されます。ノードは、単一のデータ構造に含まれる情報を表します。これらのノードには、値または条件が含まれる場合があり、別の独立したデータ構造として機能することもあります。ノードは、単一の親ノードによって表されます。ツリー構造の最高点はルートノードと呼ばれ、親ノードを持たず、ツリー内でその下にあるすべてのノードの親または「祖父母」として機能します。ノードの高さは、そのノードから最も遠いリーフノードまでのパス上のエッジの総数によって決定され、ツリーの高さはルートノードの高さに等しくなります。[1]ノードの深さは、その特定のノードとルートノード間の距離によって決定されます。ルートノードの深さはゼロであると言われています。[2]データは、これらのネットワークパスに沿って検出できます。[3] IPアドレスは、この種のノードシステムを使用して、ネットワーク内の位置を定義します。

定義

  • 子: 子ノードは、別のノードから派生したノードです。例えば、インターネットにアクセスできるコンピュータは、インターネットを表すノードの子ノードとみなすことができます。逆の関係は親ノードです。ノードCがノードAの子である場合、ノードAはノードCの親ノードです。
  • 次数: ノードの次数は、そのノードの子の数です。
  • 深さ: ノードAの深さは、 Aからルートノードまでのパスの長さです。ルートノードの深さは0とされます。
  • エッジ: ノード間の接続。
  • 森林: 木の集合。
  • 高さ: ノードAの高さは、子ノードからリーフ ノードまでの最長パスの長さです。
  • 内部ノード: 少なくとも 1 つの子を持つノード。
  • リーフ ノード: 子を持たないノード。
  • ルートノード：ツリー内の他のノードとは区別されるノード。通常、ツリーの最上位ノードとして表されます。
  • 兄弟ノード: 同じ親ノードに接続されたノードです。

マークアップ言語

ノードツリーのもう一つの一般的な用途は、Web開発です。プログラミングにおいて、XMLはコンピュータプログラマーとコンピュータ間の情報伝達に用いられます。このため、XMLはオフィス生産性ソフトウェアで使用される共通の通信プロトコルの作成に用いられ、 XHTMLのような最新のWebマークアップ言語の開発基盤となっています。プログラマーによるアプローチはHTMLとCSSに似ていますが、ウェブサイトのテキストとデザインを開発する際には、一般的にHTMLとCSSが使用されます。XML、HTML、XHTMLが言語と表現を提供するのに対し、DOMは翻訳者として機能します。[4]

ノードタイプ

ツリー内の異なるタイプのノードは、特定のインターフェースによって表現されます。つまり、ノードタイプは、他のノードとの通信方法によって定義されます。各ノードには、兄弟ノードやリーフノードなど、ノードのタイプを指定するノードタイププロパティがあります。例えば、ノードタイププロパティがノードの定数プロパティである場合、このプロパティはノードのタイプを指定します。したがって、ノードタイププロパティが定数ノードである場合ELEMENT_NODE、このノードオブジェクトはオブジェクトであることがわかりますElement。このオブジェクトは、Elementインターフェースを使用して、その特定のノードのすべてのメソッドとプロパティを定義します。

さまざまな W3C World Wide Web Consortiumノード タイプと説明:

  • Documentドキュメント全体（DOMツリーのルートノード）を表します
  • DocumentFragmentDocument文書の一部を保持できる「軽量」オブジェクトを表します
  • DocumentType文書に定義されたエンティティへのインターフェースを提供する
  • ProcessingInstruction処理命令を表す
  • EntityReference実体参照を表す
  • Element要素を表す
  • Attr属性を表す
  • Text要素または属性内のテキストコンテンツを表す
  • CDATASection文書内のCDATAセクションを表します（パーサーによって解析されないテキスト）
  • Commentコメントを表す
  • Entity実体を表す
  • NotationDTDで宣言された表記法を表す

ノードオブジェクト

ノードオブジェクトは、ツリー内の単一のノードによって表されます。ノードオブジェクトは、要素ノード、属性ノード、テキストノード、または「ノード型」セクションで説明されている任意の型になります。すべてのオブジェクトは親ノードと子ノードを扱うためのプロパティとメソッドを継承できますが、すべてのオブジェクトが親ノードまたは子ノードを持つわけではありません。例えば、子ノードを持つことができないテキストノードに子ノードを追加しようとすると、DOMエラーが発生します。

DOMツリー内のオブジェクトは、オブジェクトのメソッドを用いてアクセスおよび操作できます。DOMのパブリックインターフェースは、アプリケーションプログラミングインターフェース（API）で規定されます。ドキュメントオブジェクトモデルの歴史は、1990年代後半のNetscape NavigatorとMicrosoft Internet Explorerの間の「ブラウザ戦争」の歴史、そしてWebブラウザのレイアウトエンジンに広く実装された最初のスクリプト言語であるJavaScriptとJScriptの歴史と密接に絡み合っています。

参照

参考文献

  1. ^ “tree (data structure)”. National Institute of Standards and Technology . 2014年11月24日時点のオリジナルよりアーカイブ。
  2. ^ テウコルスキー、ロゼリン (2013).バロンズ AP コンピュータサイエンス A .バロンズ. ISBN 978-1-4380-0152-4。
  3. ^ 「Simply Scheme: コンピュータサイエンス入門 第18章: ツリー」 カリフォルニア大学バークレー校工学部。2013年12月22日時点のオリジナルよりアーカイブ。
  4. ^ 「XML DOM入門」W3Schools . 2014年6月11日時点のオリジナルよりアーカイブ。2018年4月7日閲覧。
  • 複雑なデータ分析を提示する手段としてのデータツリー（サリー・ナイプ著）
  • STL風C++ツリークラス 2020年11月26日Wayback Machineにアーカイブ
  • ideainfo.8m.com からのツリーデータ構造の説明
  • WormWeb.org: C. elegans 細胞樹のインタラクティブな視覚化 - 線虫C. elegansの細胞系統樹全体を視覚化します(JavaScript)