# 算法设计：从三元树创建双向链表

2021年5月14日15:44:33 发表评论 898 次浏览

## 本文概述

1. 三叉树的左指针应充当双向链表的上一个指针。
2. 三叉树的中间指针不应指向任何东西。
3. 三叉树的右指针应充当双向链表的下一个指针。
4. 三叉树的每个节点都在其子树之前插入到双向链表中, 对于任何节点, 将首先插入其左子节点, 然后插入中子节点和右子节点(如果有)。

## C ++

``````//C++ program to create a doubly linked list out
//of given a ternary tree.
#include <bits/stdc++.h>
using namespace std;

/* A ternary tree */
struct Node
{
int data;
struct Node *left, *middle, *right;
};

/* Helper function that allocates a new node with the
given data and assign NULL to left, middle and right
pointers.*/
Node* newNode( int data)
{
Node* node = new Node;
node->data = data;
node->left = node->middle = node->right = NULL;
return node;
}

/* Utility function that constructs doubly linked list
by inserting current node at the end of the doubly
linked list by using a tail pointer */
void push(Node** tail_ref, Node* node)
{
//initilize tail pointer
if (*tail_ref == NULL)
{
*tail_ref = node;

//set left, middle and right child to point
//to NULL
node->left = node->middle = node->right = NULL;

return ;
}

//insert node in the end using tail pointer
(*tail_ref)->right = node;

//set prev of node
node->left = (*tail_ref);

//set middle and right child to point to NULL
node->right = node->middle = NULL;

//now tail pointer will point to inserted node
(*tail_ref) = node;
}

/* Create a doubly linked list out of given a ternary tree.
by traversing the tree in preoder fashion. */
{
//Base case
if (root == NULL)
return NULL;

//create a static tail pointer
static Node* tail = NULL;

//store left, middle and right nodes
//for future calls.
Node* left = root->left;
Node* middle = root->middle;
Node* right = root->right;

//head will be root of the ternary tree

//push current node in the end of DLL
push(&tail, root);

//recurse for left, middle and right child
}

//Utility function for printing double linked list.
{
printf ( "Created Double Linked list is:\n" );
{
printf ( "%d " , head->data);
}
}

//Driver program to test above functions
int main()
{
//Construting ternary tree as shown in above figure
Node* root = newNode(30);

root->left = newNode(5);
root->middle = newNode(11);
root->right = newNode(63);

root->left->left = newNode(1);
root->left->middle = newNode(4);
root->left->right = newNode(8);

root->middle->left = newNode(6);
root->middle->middle = newNode(7);
root->middle->right = newNode(15);

root->right->left = newNode(31);
root->right->middle = newNode(55);
root->right->right = newNode(65);

return 0;
}``````

## Java

``````//Java program to create a doubly linked list
//from a given ternary tree.

//Custom node class.
class newNode
{
int data;
newNode left, middle, right;
public newNode( int data)
{
this .data = data;
left = middle = right = null ;
}
}

class GFG {

static newNode tail;

//function to push the node to the tail.
public static void push(newNode node)
{
//to put the node at the end of
tail.right = node;

//to point to the previous node.
node.left = tail;

//middle pointer should point to
//nothing so null. initiate right
//pointer to null.
node.middle = node.right = null ;

//update the tail position.
tail = node;
}

/* Create a doubly linked list out of given a ternary tree.
by traversing the tree in preoder fashion. */
public static void ternaryTree(newNode node, newNode head)
{
if (node == null )
return ;
newNode left = node.left;
newNode middle = node.middle;
newNode right = node.right;
if (tail != node)

//already root is in the tail so dont push
//the node when it was root.In the first
//case both node and tail have root in them.
push(node);

//First the left child is to be taken.
//Then middle and then right child.
}

//function to initiate the list process.
public static newNode startTree(newNode root)
{
//Initiate the head and tail with root.
tail = root;

//since the head, root are passed
//with reference the changes in
//root will be reflected in head.
}

//Utility function for printing double linked list.
{
System.out.print( "Created Double Linked list is:\n" );
{
}
}

//Driver program to test above functions
public static void main(String args[])
{

//Construting ternary tree as shown
//in above figure
newNode root = new newNode( 30 );
root.left = new newNode( 5 );
root.middle = new newNode( 11 );
root.right = new newNode( 63 );
root.left.left = new newNode( 1 );
root.left.middle = new newNode( 4 );
root.left.right = new newNode( 8 );
root.middle.left = new newNode( 6 );
root.middle.middle = new newNode( 7 );
root.middle.right = new newNode( 15 );
root.right.left = new newNode( 31 );
root.right.middle = new newNode( 55 );
root.right.right = new newNode( 65 );

//The function which initiates the list
}
}

//This code is contributed by M.V.S.Surya Teja.``````

## C#

``````//C# program to create a doubly linked
//list from a given ternary tree.
using System;

//Custom node class.
public class newNode
{
public int data;
public newNode left, middle, right;
public newNode( int data)
{
this .data = data;
left = middle = right = null ;
}
}

class GFG
{

public static newNode tail;

//function to push the node to the tail.
public static void push(newNode node)
{
//to put the node at the end of
tail.right = node;

//to point to the previous node.
node.left = tail;

//middle pointer should point to
//nothing so null. initiate right
//pointer to null.
node.middle = node.right = null ;

//update the tail position.
tail = node;
}

/* Create a doubly linked list out
of given a ternary tree. by traversing
the tree in preoder fashion. */
public static void ternaryTree(newNode node, newNode head)
{
if (node == null )
{
return ;
}
newNode left = node.left;
newNode middle = node.middle;
newNode right = node.right;
if (tail != node)
{

//already root is in the tail so dont push
//the node when it was root.In the first
//case both node and tail have root in them.
push(node);
}

//First the left child is to be taken.
//Then middle and then right child.
}

//function to initiate the list process.
public static newNode startTree(newNode root)
{
//Initiate the head and tail with root.
tail = root;

//since the head, root are passed
//with reference the changes in
//root will be reflected in head.
}

//Utility function for printing
{
Console.Write( "Created Double Linked list is:\n" );
{
}
}

//Driver Code
public static void Main( string [] args)
{

//Construting ternary tree as shown
//in above figure
newNode root = new newNode(30);
root.left = new newNode(5);
root.middle = new newNode(11);
root.right = new newNode(63);
root.left.left = new newNode(1);
root.left.middle = new newNode(4);
root.left.right = new newNode(8);
root.middle.left = new newNode(6);
root.middle.middle = new newNode(7);
root.middle.right = new newNode(15);
root.right.left = new newNode(31);
root.right.middle = new newNode(55);
root.right.right = new newNode(65);

//The function which initiates the list
``````Created Double Linked list is: