data-structures - リンクされたリスト構造を 2 つの変更を加えたバイナリ ツリー構造に変換する

Question

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

Answer 1

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

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

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

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

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

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

1. nextポインターをポインターにleft変更する
2. rightポインターを追加する

Answer 2

「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);

}

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