1

私は次のことを行う任務を持っています：

次の問題を解決するために、Javaプログラムを作成し、（内部で）文書化し、テストします。

各ノードに次のものが含まれるリンク表現を使用して、バイナリツリーADTを実装します。

  • データ
  • 左の子への参照/リンク
  • 正しい子への参照/リンク

データが整数値であると想定します。

次の操作を実装します（教科書のセクション7.3で説明されています）。

  • サイズ
  • isEmpty
  • eplace
  • 根
  • 左
  • 右
  • hasLeft
  • hasRight
  • isInternal
  • isExternal
  • isRoot
  • insertLeft
  • insertRight
  • 添付
  • 削除する

また、次のトラバーサル：

  • 予約注文
  • ポストオーダー
  • 順番に

私は二分木がどのように機能するかを知っています、そしてほとんどの場合私はこれを行うのに問題はありません-しかし私が持っている問題は私が与えられた3つ以外のノードクラスに変数を持つことが許されないということです-つまり私は親リンクを作成できません。親ノードへのリンクがない場合、特定のノードがツリーのルートであるかどうかを確認するにはどうすればよいですか？

4

3 に答える 3

2

BinaryTreeクラスを定義Nodeし、その中にルートフィールドを保持することができます。だからあなたはすでにルートを知っています

于 2013-02-25T18:52:48.307 に答える
2

左右にリンクされたノードだけを知っている孤立したノードがあり、テストするノードのコレクションがない限り、ルートを決定する方法はありません。

明らかな方法は、もちろん、周囲のツリー構造のルートプロパティを使用することです。これは、実際にはツリーを定義します。つまり、ここに示す他のすべてのソリューションです。

ただし、何らかの理由でこれを実行できない場合は、使用可能なすべてのノードをテストする次のコードのように実行できます。副作用として、「親」プロパティの実装も提供されます。

実際、「ルート」は「親のないノード」として定義できます。

public TreeNode Parent(TreeNode node)
{
  TreeNode result = null;
  foreach (TreeNode candidate in allTheNodes)
    if (candidate.left == node || candidate.right == node)
      return candidate;

  return null;
}

public TreeNode root()
{
  foreach (node in allTheNodes)
    if (Parent(node)==null) 
      return node;

  return null;
}
于 2013-02-25T19:50:07.417 に答える
1

を使用すると、次のBinaryTree3つの属性を持つノードがあります。

int value; 
Node left;
Node right;

したがって、ツリーを構築したい場合は、次のことができます。

root = Node();
root.value = 5;
root.left = Node();
root.left.value = 3;
root.left.right = Node()
root.left.right.value = 4;
root.right = Node();
root.right.value = 6;
root.left.left = node();
root.left.left.value = 1;

これは木を与えるでしょう：

    5
   / \
  3   6
 / \
1   4

これrootで、このすべての情報が保持され、それに接続されている任意のノードにアクセスできます。

したがって、基本的に、これらすべての操作のラッパーを作成する必要があります。任意のノードがルートであるかどうかを確認するには、ルートとして保存したノードと比較するだけです。

構造は次のとおりです。

public class BinaryTree{
    class Node {
        int value;
        Node left;
        Node right;
    }
    Node root;
    //method declarations
}
于 2013-02-25T19:03:15.593 に答える