ツリー抽象データ型

Question

Data Structures and Algorithmsというユニットをやっています。私たちは始めたばかりで、私の教授は代数的意味論や公理などの基本を教えてくれました。今まで、配列の形でツリーを使用しました。事前に順序付けられたツリーのシグネチャをtree（value、tree、tree）として使用しません。valueはノードの値で、左ノードは最初のツリーで、右ノードは2番目のツリーです。

今、ツリーをtree（value、tree、tree）またはNilとして定義しているので、addNode（value、tree）の代数を定義する方法を理解できません。

各レベルでますます複雑になっているだけでなく、1時間ごとに1つのレベルを1回スキャンすることも考えられません。代数は、ツリーを下るにつれてますますif-elsesに分岐します。私はそれを正しくやっていますか？私を正しい方向に向けることができますか？または、ツリーをtree（value、tree、tree）として実装することはできませんか？

これは私のチュートリアルの一部です（追加の質問でマークを付ける価値はありません）が、すぐに答えを探しているわけではありません。主題が好きなので、もっと学びたいです。

編集1：ウィキペディアをチェックアウトしましたが、明確な答えに教科書を使いたくありません。正しい方向へのヒントを探しています。ツリーとしてのツリー（値、ツリー、ツリー）。リストの形でツリーADTを表現できることを知っています。しかし、私はそれについて本当に考えたかった。それが理にかなっていることを願っています。どうもありがとう！

編集2：うーん、インターネットで説明するのは難しいです。 「tree」という新しいデータ構造を定義しているとしましょう。好きなように定義でき、バランスの取れたバイナリツリーのように動作する必要があります（ただし、親と子の値は関係ありません） だから私はそれをツリーとして定義します：tree（value、tree、tree）OR nil プログラミングコードではなく、定義方法です。 Treeは値+他の2つのツリー、またはTreeはnilです。ここで、addNode（value、tree）は、ノードをツリーに追加しながら、バランスを維持します。 それはプログラミングコードではなく、単に代数的なセマンティクスです。適切に説明できるかどうかはわかりません。しかし、キューまたはスタックを使用して達成できるソリューションに到達しましたが、それは定義する必要がある別のADTであり、有効ではありません。

編集3：問題を実際よりも困難にする多くのことを想定していたようです。まず第一に、私が与えた小さな説明から、Gamecatの答えは完璧でした。しかし、私はコメントに同意します。他のADTを含めることは完全に有効です。実際、Intを使用するものを作成する場合、その構造にはADTを使用しています。各ADTは一意でなければならないと思いました。とにかく、答えてくれてありがとう！

Answer 1

ノードをツリーに追加する場合、再帰関数を使用できます。

ツリーが順序付けられていると仮定します。そのため、次のようになります：

AddNode(value, tree)

if tree is empty, create a new tree with value as node and no subtrees.
if value lesser than the treenode, call AddNode on the left branch.
else call AddNode on the right branch. (if duplicates are allowed).

サブツリーが変更された場合は、必ず更新してください！

次の方法で、これを非再帰関数に変換できます。

if tree is empty, return a new tree with value as node and no subtrees.
if value is lesser than treenode, and there is no left subtree, create a new left subtree with value as node and no subtrees.
if value is lesser that treenode, and there is a left subtree, try again with the left subtree.
if value is greater or equal than treenode, and there is no right subtree, create a new right subtree with value as node and no subtrees.
if value is greater or equal than treenode, and there is a right subtree, try again with the right subtree.

ツリーのバランスを取る必要がある場合。バランスウェイトを取得する必要があります（-1、0、1のいずれか）。 「重い」ノードにノードを追加する必要がある場合サイト、あなたはこれを改造する必要があります。たとえば、左側に1つ以上のノードがあり、左側にもう1つノードを追加する必要がある場合。左のサブツリーから最高値を持つノードを取得し、それを現在のトップにプロモートする必要があります。前のトップが右側のサブツリーに追加されます。サブツリーもバランスを保つようにしてください。

例：ノード0、1、2、3、4を追加します

Add(0)           0

Add(1)           0
                  \
                   1

Add(2)           0 (2)  =>      1 (2) =>  1
                  \            /         / \
                   1          0         0   2

Add(3)           1
                / \
               0   2
                    \ 
                     3

Add(4)           1 (4)     => 2 (4)  =>      2
                / \          / \            / \
               0   2        1   3          1   3
                    \      /              /     \
                     3    0              0       4

Answer 2

これはあいまいなので、難しい質問です。教材の一部として類似のテキストまたは何かがあると思います。それでも、ウィキペディアのエントリ バイナリツリー。

このページでは、さまざまなツリートラバーサルの方法と、ツリーの表現方法について説明します。