0

次の構造を持つノードが与えられた場合

class Node {
int data,
Node* P1,
Node* p2;
}

ノードが循環二重リンク リストまたはバイナリ ツリーを表すかどうかを判断する必要があります。私の意見では、指定されたノードを一方向にトラバースし始める必要があります

node = givenNode;
while(node->P1 != null && node->P1 != givenNode)
{
  node = node->p1
}

if(node == givenNode) // It means Circular DLL
else if(node == null)  // It means Tree

そして、これを検出するには O(n) 時間がかかります。

これよりも良いアプローチがあれば提案してください。

4

1 に答える 1

4

このコードを使用して、二重リンクリストかどうかを確認できることをお勧めします。

node = givenNode;
if(givenNode->P1 == null || givenNode->P2 == null)
 // It can not be double link list (circular)
else if(givenNode->p1->p2 == givenNode || givenNode->p2->p1 == givenNode)
{
//It is a double linked list
}
else
{
It is not a double linked list
}

そして、O(1) の複雑さがあります

于 2012-09-24T10:42:13.093 に答える