4

目的: 二分木の同じレベルで隣接するすべてのノードを接続する関数を作成します。指定された Binary Tree ノードの構造は次のようになります。

struct node{
  int data;
  struct node* left;
  struct node* right;
  struct node* nextRight;  
}

最初は、すべての nextRight ポインターがガベージ値を指しています。関数は、これらのポインターを各ノードの次の右を指すように設定する必要があります。

解決：

void connectRecur(struct node* p);
struct node *getNextRight(struct node *p);

// Sets the nextRight of root and calls connectRecur() for other nodes
void connect (struct node *p)
{
    // Set the nextRight for root
    p->nextRight = NULL;

    // Set the next right for rest of the nodes (other than root)
    connectRecur(p);
}

/* Set next right of all descendents of p. This function makes sure that
nextRight of nodes ar level i is set before level i+1 nodes. */
void connectRecur(struct node* p)
{
    // Base case
    if (!p)
       return;

    /* Before setting nextRight of left and right children, set nextRight
    of children of other nodes at same level (because we can access 
    children of other nodes using p's nextRight only) */
    if (p->nextRight != NULL)
       connectRecur(p->nextRight);

    /* Set the nextRight pointer for p's left child */
    if (p->left)
    {
       if (p->right)
       {
           p->left->nextRight = p->right;
           p->right->nextRight = getNextRight(p);
       }
       else
           p->left->nextRight = getNextRight(p);

       /* Recursively call for next level nodes.  Note that we call only
       for left child. The call for left child will call for right child */
       connectRecur(p->left);
    }

    /* If left child is NULL then first node of next level will either be
      p->right or getNextRight(p) */
    else if (p->right)
    {
        p->right->nextRight = getNextRight(p);
        connectRecur(p->right);
    }
    else
       connectRecur(getNextRight(p));
}

/* This function returns the leftmost child of nodes at the same level as p.
   This function is used to getNExt right of p's right child
   If right child of p is NULL then this can also be used for the left child */
struct node *getNextRight(struct node *p)
{
    struct node *temp = p->nextRight;

    /* Traverse nodes at p's level and find and return
       the first node's first child */
    while(temp != NULL)
    {
        if(temp->left != NULL)
            return temp->left;
        if(temp->right != NULL)
            return temp->right;
        temp = temp->nextRight;
    }

    // If all the nodes at p's level are leaf nodes then return NULL
    return NULL;
}

この解の時間計算量はどれくらいになるでしょうか?

4

3 に答える 3

1

getNextRight のため、O(n^2) です。

最も簡単に確認できるのは、完全な二分木があると考えることです。葉の数は O(n/2) なので O(n) です。リーフごとに getNextRight を呼び出す必要があります。

最初の getNextRight は、右側の最後のリーフ用です。while ループを通過する必要はありません。

次に、右側の最後から 2 番目のリーフに対して getNextRight を呼び出します。while ループを 1 回通過します。

次の葉では、while ループを 2 回通過します。など... O(n^2) である O(1 + 2 + 3 + ... + n/2) が得られます。

また、スペースの複雑さは実際には一定ではありません。再帰によりツリーのバランスがとれている場合は O(log n) です。log n サイズのスタックがあるかもしれません。ツリーのバランスが取れていないと、さらに悪化します。

于 2013-10-19T12:01:33.497 に答える
0

私には、ルートノードからレベルごとにノードを接続しているように見えます。

親がすでに接続されているため、どのレベルでも、親を介して次のブランチにアクセスするだけです。したがって、各ノードに最大で 1 回 (または子を介して 2 回) しかアクセスしていません。

したがって、私には、時間の複雑さの順序は O(n) のように見えます。ここで、n はツリー内の要素の総数です。

于 2013-10-19T11:08:22.340 に答える