ツリー抽象データ型

Question

私はデータ構造とアルゴリズムと呼ばれるユニットをやっています。私たちはちょうど始まったばかりです。私の教授は、Algebraic Semanticsの基礎と公理の基礎について教えてくれました。これまで、私はTreesを配列の形で使ってきました。 tree（value、tree、tree）としてpre-ordered treeのシグネチャを使用していません。ここで、valueはノード内の値で、左のノードは最初のツリーで、右のノードは2番目のツリーです。

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

各レベルではますます複雑になっていきます。そして、とにかく1つのレベルを1回スキャンして1時間のように試してみることはできません。代数は、私たちが木を下っていくにつれ、より多くのelsesに分かれていきます。私はそれを正しくしていますか？あなたは正しい方向に私を向けることができますか？または、ツリーをツリー（値、ツリー、ツリー）として実装することはできませんか？

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

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

編集2：うん、インターネットで説明するのは難しい。たとえば、「ツリー」という新しいデータ構造を定義しています。 私はそれをツリーとして定義します：tree（value、tree、tree）OR nil それはありません。プログラミングコード、それは私がそれを定義する方法です。ツリーは値+ 2の他のツリーです。ツリーはゼロです。 addNode（value、tree）は、ノードをツリーに追加します。 プログラミングコードではなく、単なる代数的意味論です。私はそれを正しく説明できるかどうかわかりません。しかし、私はキューまたはスタックを使用して達成できる解決策に達しましたが、それは私が定義しなければならない別のADTです。これは有効ではありません。

編集3：私は実際にそうなっていたよりも難しくなった多くのことを想定していたようです。まず、私が与えた少しの説明から、ガメカットの答えは完璧でした。しかし、私はコメントに同意する、それは完全に他の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

これは非常に曖昧なので、これは難しい質問です。私はあなたの教材の一部としてテキストブックまたは類似のものがあると仮定します。たとえそうであっても、問題を抱えているものの多くは、the Wikipedia entry（ バイナリツリー）などの基本リソースによって説明されているように感じられます。

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