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

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

本文概述

“左-子-右-兄弟表示”是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 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 )
     {
         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。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: