Учитывая двоичное дерево, где каждый узел имеет следующую структуру, напишите функцию для заполнения следующего указателя для всех узлов. Следующий указатель для каждого узла должен быть установлен для указания преемника inorder.
struct node
{
int data;
struct node* left;
struct node* right;
struct node* next;
}
|
Изначально все следующие указатели имеют значения NULL. Ваша функция должна заполнить следующие указатели, чтобы они указывали на преемника inorder.
Решение (использовать обратный обход Inorder)
Пройдите заданное дерево в обратном порядке и следите за ранее посещенным узлом. Когда узел посещается, назначьте ранее посещенный узел как следующий.
C ++
#include<bits/stdc++.h>
using namespace std;
class node
{
public :
int data;
node *left;
node *right;
node *next;
};
void populateNext(node* p)
{
static node *next = NULL;
if (p)
{
populateNext(p->right);
p->next = next;
next = p;
populateNext(p->left);
}
}
node* newnode( int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
Node->next = NULL;
return (Node);
}
int main()
{
node *root = newnode(10);
root->left = newnode(8);
root->right = newnode(12);
root->left->left = newnode(3);
populateNext(root);
node *ptr = root->left->left;
while (ptr)
{
cout << "Next of " << ptr->data << " is "
<< (ptr->next? ptr->next->data: -1)
<< endl;
ptr = ptr->next;
}
return 0;
}
|
С
#include <stdio.h> #include <stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
struct node *next;
};
void populateNext( struct node* p)
{
static struct node *next = NULL;
if (p)
{
populateNext(p->right);
p->next = next;
next = p;
populateNext(p->left);
}
}
struct node* newnode( int data)
{
struct node* node = ( struct node*)
malloc ( sizeof ( struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->next = NULL;
return (node);
}
int main()
{
struct node *root = newnode(10);
root->left = newnode(8);
root->right = newnode(12);
root->left->left = newnode(3);
populateNext(root);
struct node *ptr = root->left->left;
while (ptr)
{
printf ( "Next of %d is %d \n" , ptr->data, ptr->next? ptr->next->data: -1);
ptr = ptr->next;
}
return 0;
}
|
Джава
class Node
{
int data;
Node left, right, next;
Node( int item)
{
data = item;
left = right = next = null ;
}
}
class BinaryTree
{
Node root;
static Node next = null ;
void populateNext(Node node)
{
if (node != null )
{
populateNext(node.right);
node.next = next;
next = node;
populateNext(node.left);
}
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node( 10 );
tree.root.left = new Node( 8 );
tree.root.right = new Node( 12 );
tree.root.left.left = new Node( 3 );
tree.populateNext(tree.root);
Node ptr = tree.root.left.left;
while (ptr != null )
{
int print = ptr.next != null ? ptr.next.data : - 1 ;
System.out.println( "Next of " + ptr.data + " is: " + print);
ptr = ptr.next;
}
}
}
|
python3
class Node:
def __init__( self , data):
self .data = data
self .left = None
self .right = None
self . next = None
next = None
def populateNext(p):
global next
if (p ! = None ):
populateNext(p.right)
p. next = next
next = p
populateNext(p.left)
def newnode(data):
node = Node( 0 )
node.data = data
node.left = None
node.right = None
node. next = None
return (node)
root = newnode( 10 )
root.left = newnode( 8 )
root.right = newnode( 12 )
root.left.left = newnode( 3 )
p = populateNext(root)
ptr = root.left.left
while (ptr ! = None ):
out = 0
if (ptr. next ! = None ):
out = ptr. next .data
else :
out = - 1
print ( "Next of" , ptr.data, "is" , out)
ptr = ptr. next
|
C #
using System;
class BinaryTree
{
class Node
{
public int data;
public Node left, right, next;
public Node( int item)
{
data = item;
left = right = next = null ;
}
}
Node root;
static Node next = null ;
void populateNext(Node node)
{
if (node != null )
{
populateNext(node.right);
node.next = next;
next = node;
populateNext(node.left);
}
}
static public void Main(String []args )
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(12);
tree.root.left.left = new Node(3);
tree.populateNext(tree.root);
Node ptr = tree.root.left.left;
while (ptr != null )
{
int print = ptr.next != null ? ptr.next.data : -1;
Console.WriteLine( "Next of " + ptr.data + " is: " + print);
ptr = ptr.next;
}
}
}
|
Выход:
Next of 3 is 8
Next of 8 is 10
Next of 10 is 12
Next of 12 is -1
Мы можем избежать использования статической переменной, передавая параметр next в качестве параметра.
C ++
void populateNext(node *root)
{
node *next = NULL;
populateNextRecur(root, &next);
}
void populateNextRecur(node* p, node **next_ref)
{
if (p)
{
populateNextRecur(p->right, next_ref);
p->next = *next_ref;
*next_ref = p;
populateNextRecur(p->left, next_ref);
}
}
|
С
void populateNext( struct node *root)
{
struct node *next = NULL;
populateNextRecur(root, &next);
}
void populateNextRecur( struct node* p, struct node **next_ref)
{
if (p)
{
populateNextRecur(p->right, next_ref);
p->next = *next_ref;
*next_ref = p;
populateNextRecur(p->left, next_ref);
}
}
|
Джава
void populateNext(Node node) {
populateNextRecur(node, next);
}
void populateNextRecur(Node p, Node next_ref) {
if (p != null ) {
populateNextRecur(p.right, next_ref);
p.next = next_ref;
next_ref = p;
populateNextRecur(p.left, next_ref);
}
}
|
C #
void populateNext(Node node)
{
populateNextRecur(node, next);
}
void populateNextRecur(Node p, Node next_ref)
{
if (p != null )
{
populateNextRecur(p.right, next_ref);
p.next = next_ref;
next_ref = p;
populateNextRecur(p.left, next_ref);
}
}
|
Сложность времени: O (n)
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
Заполнить преемник Inorder для всех узлов
0.00 (0%) 0 votes