[發(fā)明專利]節(jié)點編碼方法和裝置以及確定節(jié)點從屬關(guān)系的方法

在審

• 申請?zhí)枺?/td>: 202010129614.5
• 申請日: 2020-02-28
• 公開（公告）號: CN111353277A
• 公開（公告）日: 2020-06-30
• 發(fā)明（設(shè)計）人: 汪榆
• 申請（專利權(quán)）人: 北京京東振世信息技術(shù)有限公司
• 主分類號: G06F40/126
• 分類號: G06F40/126;G06F40/146;G06F16/903;G06Q10/08
• 代理公司: 中原信達知識產(chǎn)權(quán)代理有限責(zé)任公司 11219
• 代理人: 張效榮;王志遠

1.一種節(jié)點編碼方法，用于對形成樹形結(jié)構(gòu)的多個節(jié)點編碼；其特征在于，所述方法包括：

確定所述多個節(jié)點中根節(jié)點的編碼；

對于所述多個節(jié)點中的其它任一節(jié)點，將該節(jié)點的父節(jié)點的編碼與所述任一節(jié)點的順序碼組合為所述任一節(jié)點的編碼；其中，所述多個節(jié)點的順序碼被一致地設(shè)置為奇數(shù)或被一致地設(shè)置為偶數(shù)；在任一節(jié)點具有多個子節(jié)點時，所述多個子節(jié)點的順序碼為連續(xù)的奇數(shù)或偶數(shù)；

在向所述樹形結(jié)構(gòu)插入新節(jié)點時，如果插入后的新節(jié)點左右側(cè)都具有兄弟節(jié)點，則構(gòu)建虛擬節(jié)點，并將虛擬節(jié)點的編碼與新節(jié)點的順序碼組合為新節(jié)點的編碼；其中，虛擬節(jié)點編碼中的順序碼為所述兄弟節(jié)點順序碼的平均值，虛擬節(jié)點編碼中的其它部分與所述兄弟節(jié)點相同，新節(jié)點的順序碼與所述多個節(jié)點保持相同奇偶性。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述方法還包括：

在向所述樹形結(jié)構(gòu)插入新節(jié)點時，如果插入后的新節(jié)點不具有兄弟節(jié)點，則將該新節(jié)點的父節(jié)點的編碼與該新節(jié)點的順序碼組合為該新節(jié)點的編碼；其中，該新節(jié)點的順序碼與所述多個節(jié)點保持相同奇偶性。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，在所述多個節(jié)點中的任一節(jié)點具有多個子節(jié)點時，所述多個子節(jié)點的順序碼從左到右依次增加；以及，所述方法還包括：

在向所述樹形結(jié)構(gòu)插入新節(jié)點時：如果插入后的新節(jié)點具有左側(cè)兄弟節(jié)點但不具有右側(cè)兄弟節(jié)點，則將所述左側(cè)節(jié)點編碼中的順序碼加二形成該新節(jié)點的編碼；如果插入后的新節(jié)點具有右側(cè)兄弟節(jié)點但不具有左側(cè)兄弟節(jié)點，則將所述右側(cè)節(jié)點編碼中的順序碼減二形成該新節(jié)點的編碼。

4.根據(jù)權(quán)利要求3所述的方法，其特征在于，所述方法還包括：在向所述樹形結(jié)構(gòu)插入新節(jié)點時：

如果插入后的新節(jié)點在左側(cè)具有作為兄弟節(jié)點的第一類型節(jié)點、且右側(cè)不具有作為兄弟節(jié)點的第一類型節(jié)點，則將該新節(jié)點左側(cè)的第一類型節(jié)點的編碼中的順序碼加二形成該新節(jié)點的編碼；其中，第一類型節(jié)點的編碼由虛擬節(jié)點的編碼與第一類型節(jié)點的順序碼組合形成；

如果插入后的新節(jié)點在右側(cè)具有作為兄弟節(jié)點的第一類型節(jié)點、且左側(cè)不具有作為兄弟節(jié)點的第一類型節(jié)點，則將該新節(jié)點右側(cè)的第一類型節(jié)點的編碼中的順序碼減二形成該新節(jié)點的編碼。

5.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述方法還包括：

在向所述樹形結(jié)構(gòu)插入新節(jié)點時，如果插入后的新節(jié)點左右側(cè)都具有作為兄弟節(jié)點的第一類型節(jié)點，則構(gòu)建虛擬節(jié)點，并將該虛擬節(jié)點的編碼與該新節(jié)點的順序碼組合為該新節(jié)點的編碼；其中，

該虛擬節(jié)點編碼中的順序碼為該第一類型節(jié)點順序碼的平均值，該虛擬節(jié)點編碼中的其它部分與該第一類型節(jié)點相同，該新節(jié)點的順序碼與所述多個節(jié)點保持相同奇偶性。

6.根據(jù)權(quán)利要求1-5任一所述的方法，其特征在于，

將節(jié)點編碼與順序碼組合包括：將順序碼添加在節(jié)點編碼之后并使用分隔符隔開；

所述節(jié)點包括物品及物品集合、快遞及快遞集合、或者可擴展標(biāo)記語言XML文檔樹中的節(jié)點。

7.一種依據(jù)權(quán)利要求1-6任一所述方法得到的節(jié)點編碼確定節(jié)點從屬關(guān)系的方法，其中，所述多個節(jié)點的順序碼都為奇數(shù)；除根節(jié)點之外的任一節(jié)點的編碼由被分隔符隔開的碼元組成；其特征在于，所述方法包括：

對于任一節(jié)點，在該節(jié)點編碼的最右端碼元和次右端碼元均為奇數(shù)時，將該節(jié)點確定為目標(biāo)節(jié)點的子節(jié)點；其中，目標(biāo)節(jié)點的編碼是該任一節(jié)點的編碼去除最右端碼元剩余的部分；

對于任意多個節(jié)點，在該多個節(jié)點的編碼中具有相同前綴且該相同前綴的最右端碼元為奇數(shù)時，確定該多個節(jié)點從屬于以該相同前綴作為編碼的節(jié)點。