कैसे ठीक से एक गहराई में एक पेड़ की शाखाओं लेबल करने के लिए पहले खोज

Question

मैं इस तरह एक संरचना के साथ एक पेड़ है:

 __2__3__4 
    / \__5__6 
0__1___7/__8__9 
    \\ 
    \\__10__11__12 
    \__ __ __ 
     13 14 15 

नोड 1 चार बच्चे हैं (2,7,10,13), नोड्स 2 और 7 में दो बच्चे हैं (दोनों बच्चे के रूप में नोड 5 साझा करते हैं)। मुझे क्या करना कोशिश कर रहा हूँ एक CTE कि माता पिता नोड, नोड, जड़ से दूर दूरी, और शाखा (या कांटा) युक्त रिकॉर्ड उपलब्ध कराने में अपनी निहित पैदा करते हैं।

IF (OBJECT_ID('tempdb..#Discovered') IS NOT NULL) 
BEGIN 
    DROP TABLE #Discovered 
END 

CREATE TABLE #Discovered 
(
    ID int PRIMARY KEY NOT NULL, 
    Predecessor int NULL, 
    OrderDiscovered int 
); 

INSERT INTO #Discovered (ID, Predecessor, OrderDiscovered) 
VALUES (@nodeId, NULL, 0); 

    --loop through node connections table in a breadth first manner 
WHILE @@ROWCOUNT > 0 
BEGIN 
    INSERT INTO #Discovered (ID, Predecessor, OrderDiscovered) 
    SELECT c.node2_id 
       ,MIN(c.node1_id) 
       ,MIN(d.OrderDiscovered) + 1 

    FROM #Discovered d JOIN node_connections c ON d.ID = c.node1_id 
    WHERE c.node2_id NOT IN (SELECT ID FROM #Discovered) 
    GROUP BY c.node2_id 
END; 

SELECT * FROM #Discovered; 

WITH BacktraceCTE(Id, Predecessor, OrderDiscovered, Path, fork) 

AS 

( 

    SELECT d.ID, d.Predecessor, d.OrderDiscovered, CAST(d.ID AS varchar(MAX)), 0 

    FROM #Discovered d 

    WHERE d.Id = @itemId 


    UNION ALL    

    -- Recursive member, select all the nodes which have the previous 

    SELECT d.ID, d.Predecessor, d.OrderDiscovered, 

     CAST(cte.Path + '->' + CAST(d.ID as varchar(10)) as varchar(MAX)), 
     fork + CONVERT (Integer, ROW_NUMBER() OVER (ORDER BY d.ID)) - 1 

    FROM #Discovered d JOIN BacktraceCTE cte ON d.Predecessor = cte.ID 

)   

SELECT Predecessor as node1_id, OrderDiscovered as hop, fork, ID as node2_id, Path FROM BacktraceCTE 
ORDER BY fork, OrderDiscovered; 

समस्या के साथ है कैसे कांटा की गणना की जाती है। हर बार जब सीटीई पिछले स्तर पर वापस आ जाता है तो इसमें केवल पंक्ति संख्या उपलब्ध होती है और उस स्तर पर कांटा संख्या क्या होती है। मैं जो हासिल करना चाहता हूं वह रिकॉर्ड है जहां हॉप और कांटा का प्रत्येक संयोजन अद्वितीय होता है।

हालांकि, इसके बाद के संस्करण कोड के साथ मैं परिणाम है कि नोड 2 कहते हैं कि 5 अंत तक किया जा रहा है हॉप 3 कांटा 1 और नोड 7 से 5 मिलेगा भी हॉप 3 कांटा 1.

यहाँ किया जा रहा अंत पेड़ है साथ कैसे शाखाओं की लेबलिंग के साथ फिर से वे दिखाई देनी चाहिए:

 __2__3__4  :0 
    / \__5__6  :1,2 
0__1___7/__8__9  :3 
    \\ 
    \\__10__11__12 :4 
    \__ __ __ 
     13 14 15 :5 

आप देख सकते हैं कांटे 1 और 2 मुझे लगता है कि सबसे अच्छा तरीका शाखा गिनती करने के लिए दो बार यह अपने आप ही पहचानकर्ता इस प्रकार देने के संरक्षण के लिए किया जाएगा हॉप और कांटा के संयोजन की विशिष्टता।

कृपया यह जानने में मेरी सहायता करें कि मुझे यह प्राप्त करने के लिए क्या करना है। मुझे लगता है कि यह सीटीई के साथ संभव होना चाहिए लेकिन शायद मैं गलत हूं और यदि मैं हूं तो मुझे यह जानना अच्छा लगेगा कि इससे निपटने के लिए बेहतर तरीका क्या होगा।

संपादित परिणाम सेट दिखाई देगा:,

पूर्ववर्ती, आईडी, आदेश की खोज की, पथ कांटा

• अशक्त, 0, 0, 0, 0

• 0, 1, 1, 0-> 1, 0

• 1, 2, 2, 0-> 1-> 2, 0

• 2, 3, 3, 0-> 1-> 2-> 3, 0

• 3, 4, 4, 0-> 1-> 2-> 3> 4, 0

• 2, 5, 3, 0-> 1-> 2-> 5, 1

• 5, 6, 4, 0-> 1-> 2-> 5> 6, 1

• 1, 7, 2, 0-> 1-> 7, 2

• 7, 5, 3, 0-> 1-> 7> 5, 2

• 5, 6, 4, 0-> 1-> 7> 5> 6, 2

• 7, 8, 3, 0-> 1-> 7> 8, 3

• 8, 9, 4, 0-> 1-> 7> 8-> 9, 3

• 1, 10, 2, 0-> 1-> 10, 4

• 10 , 11, 3, 0-> 1-> 10-> 11, 4

• 11, 12, 4, 0-> 1-> 10-> 11-> 12, 4

• 1, 13, 2, 0-> 1-> 13, 5

• 13, 14, 3, 0-> 1-> 13-> 14, 5

• 14, 15, 4, 0-> 1-> 13-> 14-> 15, 5

Answer 1

ठीक है, मैं इस जवाब फिर से फेरबदल से परहेज करने की कोशिश करेंगे। यह वर्बिनरी के सॉर्ट ऑर्डर के बारे में बहुत मजेदार सीख रहा है, पावर फ़ंक्शन ढूंढ रहा है, सीटीई एक दूसरे पर मार रहा है ...।

declare @Nodes as Table (NodeId Int Identity(0,1), Name VarChar(10)) 
declare @Relations as Table (ParentNodeId Int, ChildNodeId Int, SiblingOrder Int) 
insert into @Nodes (Name) values 
-- ('0'), ('1'), ('2'), ('3'), ('4'), ('5'), ('6'), ('7'), ('8'), 
-- ('9'), ('10'), ('11'), ('12'), ('13'), ('14'), ('15') 
    ('zero'), ('one'), ('two'), ('three'), ('four'), ('five'), ('six'), ('seven'), ('eight'), 
    ('nine'), ('ten'), ('eleven'), ('twelve'), ('thirteen'), ('fourteen'), ('fifteen') 

insert into @Relations (ParentNodeId, ChildNodeId, SiblingOrder) values 
    (0, 1, 0), 
    (1, 2, 0), (1, 7, 1), (1, 10, 2), (1, 13, 3), 
    (2, 3, 0), (2, 5, 1), 
    (3, 4, 0), 
    (5, 6, 0), 
    (7, 5, 0), (7, 8, 1), 
    (8, 9, 0), 
    (10, 11, 0), 
    (11, 12, 0), 
    (13, 14, 0), 
    (14, 15, 0) 

declare @MaxSiblings as BigInt = 100 
; with 
DiGraph (NodeId, Name, Depth, ParentNodeId, Path, ForkIndex, DepthFirstOrder) 
as (
    -- Start with the root node(s). 
    select NodeId, Name, 0, Cast(NULL as Int), Cast(Name as VarChar(1024)), 
    Cast(0 as BigInt), Cast(Right('00' + Cast(0 as VarChar(2)), 2) as VarChar(128)) 
    from @Nodes 
    where not exists (select 42 from @Relations where ChildNodeId = NodeId) 
    union all 
    -- Add children one generation at a time. 
    select R.ChildNodeId, N.Name, DG.Depth + 1, R.ParentNodeId, Cast(DG.Path + ' > ' + N.Name as VarChar(1024)), 
    DG.ForkIndex + R.SiblingOrder * Power(@MaxSiblings, DG.Depth - 1), 
    Cast(DG.DepthFirstOrder + Right('00' + Cast(R.SiblingOrder as VarChar(2)), 2) as VarChar(128)) 
    from @Relations as R inner join 
     DiGraph as DG on DG.NodeId = R.ParentNodeId inner join 
     @Nodes as N on N.NodeId = R.ChildNodeId inner join 
     @Nodes as Parent on Parent.NodeId = R.ParentNodeId 
), 

DiGraphSorted (NodeId, Name, Depth, ParentNodeId, Path, ForkIndex, DepthFirstOrder, RowNumber) 
as (select *, Row_Number() over (order by DepthFirstOrder) as 'RowNumber' from DiGraph) 

select ParentNodeId, NodeId, Depth, Path, 
    (select Count(*) from DiGraphSorted as L 
    left outer join DiGraphSorted as R on R.RowNumber = L.RowNumber - 1 where 
    R.RowNumber < DG.RowNumber and L.ForkIndex <> R.ForkIndex) as 'ForkNumber' -- , '', * 
    from DiGraphSorted as DG 
    order by RowNumber