# 算法：创建一个具有左-子-右-兄弟表示的树

2021年5月11日14:31:06 发表评论 941 次浏览

## 本文概述

“左-子-右-兄弟表示”是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
{
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)
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);
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 )
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
if (n = = None ):
return None

while (n. Next ):
n = n. Next
n. Next = newNode(data)
return n. Next

# Add child Node to a Node
if (n = = None ):
return None

# Check if child list is not empty.
if (n.child):
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 )
traverseTree(root)

# This code is contributed by pranchalK``````

## C#

``````//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 )
{
}
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);

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
{
if (n == NULL)
return NULL;

while (n->next)
n = n->next;

return (n->next = newNode(data));
}

//Add child Node to a Node
{
if (n == NULL)
return NULL;

//Check if child list is not empty.
if (n->child)
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);
``10 2 3 4 5 6 7 8 9``