-1

バイナリ ツリー データ構造に変換されるように、リンク リスト データ構造に対して実行できる変更を 2 つ挙げてください。

4

2 に答える 2

1

質問はかなり漠然としていますが、これは私が意味することだと思います。

リンクされたリストで使用される構造には、nextポインターがあります。

struct LinkedListNode {
    LinkedListNode *next;
    // data element(s)
};

二分木で使用される構造体にはleftrightポインタが含まれます。

struct BinaryTreeNode {
    BinaryTreeNode *left;
    BinaryTreeNode *right;
    // data element(s)
}

したがって、質問が参照する2つの変更は次のようになると思います。

  1. nextポインターをポインターにleft変更する
  2. rightポインターを追加する
于 2013-09-01T04:47:11.580 に答える
0

「2つの変更」という点はわかりませんが、 aLinkedListを aに変換するにはBinaryTree、2つのアプローチに従うことができます

  1. 一気飲み
  2. トップダウン

1) トップダウンアプローチ:

このメソッドではLinkedList、2 つのサブリストに分割でき、中央の要素が親ノードになり、それぞれが左右のサブリストに対してこの再帰メソッドを呼び出します。

この背後にある基本的なロジックは、

ListToBinaryTree(LinkedList list, int start, int end) {

   mid -> start + (end - start) / 2;
   left -> ListToBinaryTree(list, start, mid-1);
   right -> ListToBinaryTree(list, mid+1, end);

}

2) ボトムアップアプローチ:

このアプローチでは、最初に子要素を作成し、次に親要素を作成します。

この背後にある基本的なロジックは、

ListToBinaryTree(ListNode *& list, int start, int end) {

  mid -> start + (end - start) / 2;
  leftChild -> ListToBinaryTree(list, start, mid-1);
  parent -> new BinaryTree(list -> data);
  parent -> left = leftChild;
  list = list -> next;
  parent -> right = ListToBinaryTree(list, mid+1, end);

}

これが役立つことを願っています。

于 2013-11-08T09:40:34.180 に答える