Left-child right-sibling binary tree (original) (raw)
En informatique, un arbre « double chaîne » ou Doubly chained tree peut s'entendre de deux manières : * Au niveau technique : utilisation deux liens (pointeurs) seulement (voir les arbres dits left-child right-sibling binary tree) * Au niveau conceptuel : un ensemble de listes double chaînes organisées dans une structure hiérarchique (arbre), ce qui implique au moins l'usage d'un troisième lien pour gérer la hiérarchie. Est abordée ci-dessous la notion d'arbre double chaîne au niveau conceptuel, pour les double-chaînes techniques.
| Property | Value | |||
|---|---|---|---|---|
| dbo:abstract | Every multi-way or k-ary tree structure studied in computer science admits a representation as a binary tree, which goes by various names including child-sibling representation, left-child, right-sibling binary tree, doubly chained tree or filial-heir chain. In a binary tree that represents a multi-way tree T, each node corresponds to a node in T and has two pointers: one to the node's first child, and one to its next sibling in T. The children of a node thus form a singly-linked list. To find a node n's k'th child, one needs to traverse this list: procedure kth-child(n, k): child ← n.child while k ≠ 0 and child ≠ nil: child ← child.next-sibling k ← k − 1 return child // may return nil The process of converting from a k-ary tree to an LC-RS binary tree is sometimes called the Knuth transform. To form a binary tree from an arbitrary k-ary tree by this method, the root of the original tree is made the root of the binary tree. Then, starting with the root, each node's leftmost child in the original tree is made its left child in the binary tree, and its nearest sibling to the right in the original tree is made its right child in the binary tree. Doubly chained trees were described by Edward H. Sussenguth in 1963. Processing a k-ary tree to LC-RS binary tree, every node is linked and aligned with the left child, and the next nearest is a sibling. For example, we have a ternary tree below: 1 /|\ / | \ / | \ 2 3 4 / \ | 5 6 7 / \ 8 9 We can re-write it by putting the left child node to one level below its parents and by putting the sibling next to the child at the same level – it will be linear (same line). 1 / / / 2---3---4 / / 5---6 7 / 8---9 We can transform this tree to a binary tree by turning each sibling 45° clockwise. 1 / 2 / \ 5 3 \ \ 6 4 / 7 / 8 \ 9 (en) En informatique, un arbre « double chaîne » ou Doubly chained tree peut s'entendre de deux manières : * Au niveau technique : utilisation deux liens (pointeurs) seulement (voir les arbres dits left-child right-sibling binary tree) * Au niveau conceptuel : un ensemble de listes double chaînes organisées dans une structure hiérarchique (arbre), ce qui implique au moins l'usage d'un troisième lien pour gérer la hiérarchie. Est abordée ci-dessous la notion d'arbre double chaîne au niveau conceptuel, pour les double-chaînes techniques. (fr) 二重連鎖木（にじゅうれんさぎ、英: doubly chained tree）や左-子，右-兄弟表現（英: left-child, right-sibling representation）や子-兄弟表現（英: child-sibling representation）や filial-heir chain とは、多分木を、直接子ノードのポインタの集合で管理するのではなく、子ノード1つと兄弟ノード1つのポインタで管理する方法。つまり多分木を二分木に変換する。1963年に Edward H. Sussenguth が発表した。 ノード n の k 番目の子供を取得するには、以下のように行う。ノードは child と next-sibling を保持している。 procedure kth-child(n, k): child ← n.child while k ≠ 0 and child ≠ nil: child ← child.next-sibling k ← k − 1 return child // nil を返す場合もある (ja) |
| dbo:thumbnail | wiki-commons:Special:FilePath/N-ary_to_binary.svg?width=300 | |||
| dbo:wikiPageID | 11261383 (xsd:integer) | |||
| dbo:wikiPageLength | 5885 (xsd:nonNegativeInteger) | |||
| dbo:wikiPageRevisionID | 1076479069 (xsd:integer) | |||
| dbo:wikiPageWikiLink | dbr:Binary_tree dbr:Edward_H._Sussenguth dbr:Computer_science dbr:Pointer_(computer_programming) dbr:Weak_heap dbr:K-ary_tree dbc:Binary_trees dbr:Donald_Knuth dbr:Phylogenetic_tree dbr:Fibonacci_heap dbr:Pairing_heap dbr:Singly-linked_list dbr:Multi-way_tree dbr:File:Pointer_implementation_of_a_trie.svg dbr:File:N-ary_to_binary.svg | |||
| dbp:wikiPageUsesTemplate | dbt:CS-Trees dbt:Mono dbt:Mvar dbt:Reflist dbt:Snd | |||
| dcterms:subject | dbc:Binary_trees | |||
| rdf:type | yago:WikicatBinaryTrees yago:LivingThing100004258 yago:Object100002684 yago:Organism100004475 yago:PhysicalEntity100001930 yago:Plant100017222 yago:WoodyPlant113103136 yago:Tree113104059 yago:VascularPlant113083586 yago:Whole100003553 | |||
| rdfs:comment | En informatique, un arbre « double chaîne » ou Doubly chained tree peut s'entendre de deux manières : * Au niveau technique : utilisation deux liens (pointeurs) seulement (voir les arbres dits left-child right-sibling binary tree) * Au niveau conceptuel : un ensemble de listes double chaînes organisées dans une structure hiérarchique (arbre), ce qui implique au moins l'usage d'un troisième lien pour gérer la hiérarchie. Est abordée ci-dessous la notion d'arbre double chaîne au niveau conceptuel, pour les double-chaînes techniques. (fr) 二重連鎖木（にじゅうれんさぎ、英: doubly chained tree）や左-子，右-兄弟表現（英: left-child, right-sibling representation）や子-兄弟表現（英: child-sibling representation）や filial-heir chain とは、多分木を、直接子ノードのポインタの集合で管理するのではなく、子ノード1つと兄弟ノード1つのポインタで管理する方法。つまり多分木を二分木に変換する。1963年に Edward H. Sussenguth が発表した。 ノード n の k 番目の子供を取得するには、以下のように行う。ノードは child と next-sibling を保持している。 procedure kth-child(n, k): child ← n.child while k ≠ 0 and child ≠ nil: child ← child.next-sibling k ← k − 1 return child // nil を返す場合もある (ja) Every multi-way or k-ary tree structure studied in computer science admits a representation as a binary tree, which goes by various names including child-sibling representation, left-child, right-sibling binary tree, doubly chained tree or filial-heir chain. In a binary tree that represents a multi-way tree T, each node corresponds to a node in T and has two pointers: one to the node's first child, and one to its next sibling in T. The children of a node thus form a singly-linked list. To find a node n's k'th child, one needs to traverse this list: (en) | |||
| rdfs:label | Doubly chained tree (fr) Left-child right-sibling binary tree (en) 二重連鎖木 (ja) | |||
| owl:sameAs | freebase:Left-child right-sibling binary tree wikidata:Left-child right-sibling binary tree dbpedia-fa:Left-child right-sibling binary tree dbpedia-fr:Left-child right-sibling binary tree dbpedia-ja:Left-child right-sibling binary tree https://global.dbpedia.org/id/ASnQ yago-res:Left-child right-sibling binary tree | |||
| prov:wasDerivedFrom | wikipedia-en:Left-child_right-sibling_binary_tree?oldid=1076479069&ns=0 | |||
| foaf:depiction | wiki-commons:Special:FilePath/N-ary_to_binary.svg wiki-commons:Special:FilePath/Pointer_implementation_of_a_trie.svg | |||
| foaf:isPrimaryTopicOf | wikipedia-en:Left-child_right-sibling_binary_tree | |||
| is dbo:wikiPageRedirects of | dbr:Filial-heir_chain dbr:LC-RS_Tree dbr:LC-RS_tree dbr:LCRS_Tree dbr:LCRS_tree dbr:First-child-next-sibling dbr:First_child-next_sibling_binary_tree dbr:Doubly-chained_tree dbr:Doubly_chained_tree dbr:Left_child-right_sibling_binary_tree dbr:Left_child_right_sibling dbr:Knuth_transform | |||
| is dbo:wikiPageWikiLink of | dbr:List_of_data_structures dbr:M-ary_tree dbr:Binary_tree dbr:Weak_heap dbr:Filial-heir_chain dbr:Tree_structure dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:LC-RS_Tree dbr:LC-RS_tree dbr:LCRS_Tree dbr:LCRS_tree dbr:First-child-next-sibling dbr:First_child-next_sibling_binary_tree dbr:Doubly-chained_tree dbr:Doubly_chained_tree dbr:Left_child-right_sibling_binary_tree dbr:Left_child_right_sibling dbr:Knuth_transform | |||
| is foaf:primaryTopic of | wikipedia-en:Left-child_right-sibling_binary_tree |
