本文概述
“左-子-右-兄弟表示”是n元树的一种不同的表示形式，这里不是保存对每个子节点的引用，一个节点只保存两个引用，第一个是对它的第一个子节点的引用，另一个是对它紧邻的下一个兄弟节点的引用。这种新的转换不仅消除了对节点拥有的子节点数量的预先了解，而且还将引用的数量限制为最多两个，从而使其更容易编码。
At each node, link children of same parent from left to right.
Parent should be linked with only first child.例子：
Left Child Right Sibling tree representation
10
|
2 -> 3 -> 4 -> 5
| |
6 7 -> 8 -> 9先决条件：
树的左儿童右同级表示
下面是实现。
C ++
//CPP program to create a tree with left child
//right sibling representation.
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node *next;
struct Node *child;
};
//Creating new Node
Node* newNode( int data)
{
Node *newNode = new Node;
newNode->next = newNode->child = NULL;
newNode->data = data;
return newNode;
}
//Adds a sibling to a list with starting with n
Node *addSibling(Node *n, int data)
{
if (n == NULL)
return NULL;
while (n->next)
n = n->next;
return (n->next = newNode(data));
}
//Add child Node to a Node
Node *addChild(Node * n, int data)
{
if (n == NULL)
return NULL;
//Check if child list is not empty.
if (n->child)
return addSibling(n->child, data);
else
return (n->child = newNode(data));
}
//Traverses tree in depth first order
void traverseTree(Node * root)
{
if (root == NULL)
return ;
while (root)
{
cout <<" " <<root->data;
if (root->child)
traverseTree(root->child);
root = root->next;
}
}
//Driver code
int main()
{
/* Let us create below tree
* 10
* / / \ \
* 2 3 4 5
* | /| \
* 6 7 8 9 */
//Left child right sibling
/* 10
* |
* 2 -> 3 -> 4 -> 5
* | |
* 6 7 -> 8 -> 9 */
Node *root = newNode(10);
Node *n1 = addChild(root, 2);
Node *n2 = addChild(root, 3);
Node *n3 = addChild(root, 4);
Node *n4 = addChild(n3, 6);
Node *n5 = addChild(root, 5);
Node *n6 = addChild(n5, 7);
Node *n7 = addChild(n5, 8);
Node *n8 = addChild(n5, 9);
traverseTree(root);
return 0;
}Java
//CPP program to create a tree with left child
//right sibling representation.
class GFG {
static class NodeTemp
{
int data;
NodeTemp next, child;
public NodeTemp( int data)
{
this .data = data;
next = child = null ;
}
}
//Adds a sibling to a list with starting with n
static public NodeTemp addSibling(NodeTemp node, int data)
{
if (node == null )
return null ;
while (node.next != null )
node = node.next;
return (node.next = new NodeTemp(data));
}
//Add child Node to a Node
static public NodeTemp addChild(NodeTemp node, int data)
{
if (node == null )
return null ;
//Check if child is not empty.
if (node.child != null )
return (addSibling(node.child, data));
else
return (node.child = new NodeTemp(data));
}
//Traverses tree in depth first order
static public void traverseTree(NodeTemp root)
{
if (root == null )
return ;
while (root != null )
{
System.out.print(root.data + " " );
if (root.child != null )
traverseTree(root.child);
root = root.next;
}
}
//Driver code
public static void main(String args[])
{
/* Let us create below tree
* 10
* / / \ \
* 2 3 4 5
* | /| \
* 6 7 8 9 */
//Left child right sibling
/* 10
* |
* 2 -> 3 -> 4 -> 5
* | |
* 6 7 -> 8 -> 9 */
NodeTemp root = new NodeTemp( 10 );
NodeTemp n1 = addChild(root, 2 );
NodeTemp n2 = addChild(root, 3 );
NodeTemp n3 = addChild(root, 4 );
NodeTemp n4 = addChild(n3, 6 );
NodeTemp n5 = addChild(root, 5 );
NodeTemp n6 = addChild(n5, 7 );
NodeTemp n7 = addChild(n5, 8 );
NodeTemp n8 = addChild(n5, 9 );
traverseTree(root);
}
}
//This code is contributed by M.V.S.Surya Teja.Python3
# Python3 program to create a tree with
# left child right sibling representation.
# Creating new Node
class newNode:
def __init__( self , data):
self . Next = self .child = None
self .data = data
# Adds a sibling to a list with
# starting with n
def addSibling(n, data):
if (n = = None ):
return None
while (n. Next ):
n = n. Next
n. Next = newNode(data)
return n. Next
# Add child Node to a Node
def addChild(n, data):
if (n = = None ):
return None
# Check if child list is not empty.
if (n.child):
return addSibling(n.child, data)
else :
n.child = newNode(data)
return n.child
# Traverses tree in depth first order
def traverseTree(root):
if (root = = None ):
return
while (root):
print (root.data, end = " " )
if (root.child):
traverseTree(root.child)
root = root. Next
# Driver code
if __name__ = = '__main__' :
# Let us create below tree
# 10
# //\ \
# 2 3 4 5
# | /| \
# 6 7 8 9
# Left child right sibling
# 10
# |
# 2 -> 3 -> 4 -> 5
# | |
# 6 7 -> 8 -> 9
root = newNode( 10 )
n1 = addChild(root, 2 )
n2 = addChild(root, 3 )
n3 = addChild(root, 4 )
n4 = addChild(n3, 6 )
n5 = addChild(root, 5 )
n6 = addChild(n5, 7 )
n7 = addChild(n5, 8 )
n8 = addChild(n5, 9 )
traverseTree(root)
# This code is contributed by pranchalKC#
//C# program to create a tree with left
//child right sibling representation.
using System;
class GFG
{
public class NodeTemp
{
public int data;
public NodeTemp next, child;
public NodeTemp( int data)
{
this .data = data;
next = child = null ;
}
}
//Adds a sibling to a list with
//starting with n
public static NodeTemp addSibling(NodeTemp node, int data)
{
if (node == null )
{
return null ;
}
while (node.next != null )
{
node = node.next;
}
return (node.next = new NodeTemp(data));
}
//Add child Node to a Node
public static NodeTemp addChild(NodeTemp node, int data)
{
if (node == null )
{
return null ;
}
//Check if child is not empty.
if (node.child != null )
{
return (addSibling(node.child, data));
}
else
{
return (node.child = new NodeTemp(data));
}
}
//Traverses tree in depth first order
public static void traverseTree(NodeTemp root)
{
if (root == null )
{
return ;
}
while (root != null )
{
Console.Write(root.data + " " );
if (root.child != null )
{
traverseTree(root.child);
}
root = root.next;
}
}
//Driver code
public static void Main( string [] args)
{
/* Let us create below tree
* 10
* //\ \
* 2 3 4 5
* | /| \
* 6 7 8 9 */
//Left child right sibling
/* 10
* |
* 2 -> 3 -> 4 -> 5
* | |
* 6 7 -> 8 -> 9 */
NodeTemp root = new NodeTemp(10);
NodeTemp n1 = addChild(root, 2);
NodeTemp n2 = addChild(root, 3);
NodeTemp n3 = addChild(root, 4);
NodeTemp n4 = addChild(n3, 6);
NodeTemp n5 = addChild(root, 5);
NodeTemp n6 = addChild(n5, 7);
NodeTemp n7 = addChild(n5, 8);
NodeTemp n8 = addChild(n5, 9);
traverseTree(root);
}
}
//This code is contributed by Shrikant13输出如下：
10 2 3 4 6 5 7 8 9级别顺序遍历：上面的代码讨论了深度优先遍历。我们还可以进行此类表示的级别顺序遍历。
C ++
//CPP program to create a tree with left child
//right sibling representation.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
struct Node* child;
};
//Creating new Node
Node* newNode( int data)
{
Node* newNode = new Node;
newNode->next = newNode->child = NULL;
newNode->data = data;
return newNode;
}
//Adds a sibling to a list with starting with n
Node* addSibling(Node* n, int data)
{
if (n == NULL)
return NULL;
while (n->next)
n = n->next;
return (n->next = newNode(data));
}
//Add child Node to a Node
Node* addChild(Node* n, int data)
{
if (n == NULL)
return NULL;
//Check if child list is not empty.
if (n->child)
return addSibling(n->child, data);
else
return (n->child = newNode(data));
}
//Traverses tree in level order
void traverseTree(Node* root)
{
//Corner cases
if (root == NULL)
return ;
cout <<root->data <<" " ;
if (root->child == NULL)
return ;
//Create a queue and enque root
queue<Node*> q;
Node* curr = root->child;
q.push(curr);
while (!q.empty()) {
//Take out an item from the queue
curr = q.front();
q.pop();
//Print next level of taken out item and enque
//next level's children
while (curr != NULL) {
cout <<curr->data <<" " ;
if (curr->child != NULL) {
q.push(curr->child);
}
curr = curr->next;
}
}
}
//Driver code
int main()
{
Node* root = newNode(10);
Node* n1 = addChild(root, 2);
Node* n2 = addChild(root, 3);
Node* n3 = addChild(root, 4);
Node* n4 = addChild(n3, 6);
Node* n5 = addChild(root, 5);
Node* n6 = addChild(n5, 7);
Node* n7 = addChild(n5, 8);
Node* n8 = addChild(n5, 9);
traverseTree(root);
return 0;
}输出如下：
10 2 3 4 5 6 7 8 9本文作者：萨基·提瓦里。如果你喜欢lsbin(我们知道你愿意！)并且想贡献力量, 你还可以使用功臣网或将你的文章邮寄至tribution@lsbin.org。查看你的文章出现在lsbin主页上, 并帮助其他Geeks。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
![从字法上最小长度N的排列，使得对于正好为K个索引，a[i] a[i]+1](https://www.lsbin.com/wp-content/themes/begin%20lts/img/loading.png)
