left-child right-sibling representation - 左孩子右兄弟表示

Bertha 。 2023-01-04 14:42 86阅读 0赞

# **left-child right-sibling representation - 左孩子右兄弟表示** #

Left-Child Right-Sibling Representation is a different representation of an `n-ary` tree where instead of holding a reference to each and every child node, a node holds just two references, first a reference to it’s first child, and the other to it’s immediate next sibling. This new transformation not only removes the need of advance knowledge of the number of children a node has, but also limits the number of references to a maximum of two, thereby making it so much easier to code.  
Left-Child Right-Sibling Representation 是 `n` 元树的另一种表示形式，一个节点不保存对每个子节点的引用，而仅保留两个引用，一个对它的第一个子节点的引用，另一个对它的下一个兄弟节点的引用。这种新的转变不仅消除了对节点拥有的子节点数量的预先了解的需要，而且还将引用数限制为最多两个，从而使编码变得如此容易。

At each node, link children of same parent from left to right. Parent should be linked with only first child.  
在每个节点上，从左到右链接同一父级的子级。父级应仅与第一个子级联系。

## 1. Left Child Right Sibling tree representation ##

10
          |  
          2 -> 3 -> 4 -> 5
          |    |  
          6    7 -> 8 -> 9

typedef struct NODE {
    	int data;
    	struct NODE *first_child;
    	struct NODE *right_sibling;
    } Node;

## References ##

[https://www.geeksforgeeks.org/creating-tree-left-child-right-sibling-representation/][https_www.geeksforgeeks.org_creating-tree-left-child-right-sibling-representation]  
**在线 IDE**  
[https://ide.geeksforgeeks.org/][https_ide.geeksforgeeks.org]

[https_www.geeksforgeeks.org_creating-tree-left-child-right-sibling-representation]: https://www.geeksforgeeks.org/creating-tree-left-child-right-sibling-representation/
[https_ide.geeksforgeeks.org]: https://ide.geeksforgeeks.org/