Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.
Verilmiş a İkili ağac, soldan sağa eyni səviyyədə olan qovşaqları birləşdirin.
Ağac Node quruluşu: Ağacın bir qovşağı ağac node tipinin məlumatları (tam ədəd dəyəri), göstəriciləri (sonrakı, sol və sağ) olan 4 komponentdən ibarətdir. bir qovşaqın növbəti göstəricisi eyni səviyyədə sağ qovşağına doğru. Əgər düyün bu səviyyədə ən sağ düyündürsə, növbəti göstərici sıfır dəyərə işarə edir. sol və sağ göstəricilər sırasıyla sola və sağ uşağa işarə edir. A-nın quruluşu ağac düyün aşağıda təsvir edilmişdir:
Mündəricat
misal
Giriş:
Çıxış:
Giriş:
Çıxış:
Giriş:
Çıxış:
Izahat
- iki qovşaq bağlamaq a və b soldan sağa, bu əməliyyatı etmək üçün: a-> sonrakı = b.
- Başlanğıcda sonrakı bütün ağac qovşaqlarının göstəriciləri olaraq ayarlanır sıfır.
- Quran bir alqoritm qurun sonrakı hər bir düyünün göstəricisi sonrakı düyün (sağa) eyni səviyyədə.
- The sonrakı hər səviyyədə ən sağ qovşağın göstəricisi olaraq ayarlanır sıfır.
Həll növləri
- Səviyyə düzəlişi / Genişlik İlk Axtarış (BFS).
- Traversal əvvəlcədən sifariş edin
- daimi yer - rekursiv
- daimi yer - iterativ
Səviyyə sifariş Traversal / BFS
Hər Nodda Növbəti Sağ Göstəricilərin doldurulması üçün yanaşma
Fikir yerinə yetirməkdir BFS verilmiş ikili ağacda, qovşaqları səviyyəli qaydada saxlayan bir sıra istifadə edirik. Növbədə, qovşaqları səviyyə nömrələri ilə birlikdə saxlayırıq. Bir dəfə, müəyyən bir səviyyədəki bütün qovşaqları saxladıq, sadəcə onları bir-bir açırıq və əvvəlcədən atılmış qovşaqları bu anda qoyulmuş node ilə birləşdiririk. sonrakı göstərici. Həm də əmin olun ki, sonrakı sağ tərəfdən (bir səviyyənin son açılan nodu) düyünü göstərməlidir sıfır.
Alqoritm
- Verilən ikili ağacda BFS yerinə yetirin. Bir ağacda BFS yerinə yetirərkən, müəyyən bir səviyyədə olan bütün qovşaqlar növbəyə basılır.
- Bütün qovşaqları eyni səviyyədə (ikili ağacda) növbədən bir-bir açın.
- Düyünləri atarkən, təyin edin sonrakı əvvəlki düyünün cari düyünə göstəricisi.
- İkili ağacın hər səviyyəsi üçün 2 və 3-cü addımları yerinə yetirin.
Yuxarıdakı alqoritm aşağıda təsvir edilmişdir:
Həyata keçirilməsi
C ++ Proqramı
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// blueprint of the tree node
class Node
{
public :
int data;
Node *left, *right, *next;
Node(int key)
{
data = key;
left = right = next = NULL;
}
};
// function that makes appropriate connections
void connect(Node *root)
{
// create queue to hold nodes at same level
queue <Node*> q;
// insert root node
q.push(root);
// used to store the current node
Node* temp = NULL;
while (!q.empty())
{
int n = q.size();
for (int i = 0; i < n; i++)
{
// previous stores last popped node from the queue
Node* prev = temp;
temp = q.front();
q.pop();
/*
when i = 0, prev is the first node of a level
so we have to skip this node.
and change next pointer from next node onwards
*/
if (i > 0)
prev->next = temp;
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
// pointing last node of a particular level to null
temp->next = NULL;
}
}
// Function to print node values of a particular level
void printLevel(Node* root)
{
if(root == NULL)
{
cout<<endl;
return;
}
cout<<root->data<<" ";
printLevel(root->next);
}
int main()
{
/* create the binary tree*/
Node *root = NULL;
root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->right = new Node(6);
connect(root);
cout<<"1st Level : ";
printLevel(root);
cout<<"2nd Level : ";
printLevel(root->left);
cout<<"3rd Level : ";
printLevel(root->left->left);
return 0;
}
1st Level : 1 2nd Level : 2 3 3rd Level : 4 5 6
Java Proqramı
import java.util.*;
import java.io.*;
class tutorialCup
{
// blueprint of the tree node
static class Node
{
int data;
Node left, right, next;
Node(int key)
{
data = key;
left = right = next = null;
}
}
// function that makes appropriate connections
static void connect(Node root)
{
// create queue to hold nodes at same level
Queue<Node> q = new LinkedList<>();
// insert root node
q.add(root);
// used to store the current node
Node temp = null;
while (!q.isEmpty())
{
int n = q.size();
for (int i = 0; i < n; i++)
{
// previous stores last popped node from the queue
Node prev = temp;
temp = q.poll();
/*
when i = 0, prev is the first node of a level
so we have to skip this node.
and change next pointer from next node onwards
*/
if (i > 0)
prev.next = temp;
if (temp.left != null)
q.add(temp.left);
if (temp.right != null)
q.add(temp.right);
}
// pointing last node of a particular level to null
temp.next = null;
}
}
// Function to print node values of a particular level
static void printLevel(Node root)
{
if(root == null)
{
System.out.println();
return;
}
System.out.print(root.data+" ");
printLevel(root.next);
}
// main Function to implement above function
public static void main (String[] args)
{
/* create the binary tree*/
Node root = null;
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(6);
connect(root);
System.out.print("1st Level : ");
printLevel(root);
System.out.print("2nd Level : ");
printLevel(root.left);
System.out.print("3rd Level : ");
printLevel(root.left.left);
}
}
1st Level : 1 2nd Level : 2 3 3rd Level : 4 5 6
Hər Nodda Növbəti Sağ İşarələrin doldurulması üçün Mürəkkəblik Təhlili
- Zaman Mürəkkəbliyi: T (n) = O (n), ağacın hər bir düyünü işlənir.
- Kosmik Mürəkkəblik: A (n) = O (n).
Traversal əvvəlcədən sifariş edin
Hər Nodda Növbəti Sağ Göstəricilərin doldurulması üçün yanaşma
Bu metod yalnız üçün işləyir tam ikili ağaclar.
Tamamilə İkili Ağaclar: A tam ikili ağac birdir ikili ağac ehtimal ki, sonuncusu xaricində hər səviyyə tamamilə doldurulur və bütün qovşaqlar mümkün qədər solda qalır. Aşağıda tam ikili ağac nümunəsidir.
Aşağıda bir nümunədir yox tam ikili ağac.
Fikir təyin etməkdir sonrakı hər bir qovşağın göstəricisi əvvəlcədən sifariş qaydasında, yəni sonrakı ana qovşaqlarının əvvəllər təyin edilmişdir sonrakı uşaq qovşaqlarının.
Verilən ağac tam bir ikili ağac olduğundan, aşağıdakı ifadələri edə bilərik:
- Bir ana düyün üçün ilə, sonrakı sol uşağının ilə nin doğru uşağı olardı ilə. yəni par-> sol-> sonrakı = par-> sağ.
- sonrakı -in sağ uşağının ilə sol uşağı olardı sonrakı of ilə. yəni par-> right-> next = par-> next-> sol.
- ağacdakı ən sağ valideynin sağ uşağı olardı sıfır. yəni par-> right-> next = null (par ən sağ tərəfdirsə).
Yuxarıda göstərilən müşahidələri etdikdən sonra ağacdakı bütün qovşaqların növbəti göstəricilərini təyin edə bilən rekursiv bir əvvəlcədən sifariş (valideynləri uşaqlardan əvvəl emal) alqoritmi tərtib edə bilərik.
Alqoritm
- Əsas vəziyyəti müəyyənləşdirin.
- Atayın sonrakı ana düyünün sol övladlarının parın sağ uşaqlarına, yəni par-> sol-> sonrakı = par-> sağ.
- Atayın sonrakı ana düyünün sağ övladlarının sol uşaqlara par-> növbəti. yəni par-> right-> next = par-> next-> sol.
- Ana düyünün sol və sağ övladları üçün 2 və 3-cü addımları təkrarən yerinə yetirin.
Yuxarıdakı alqoritm aşağıda təsvir edilmişdir:
Həyata keçirilməsi
C ++ Proqramı
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// blueprint of the tree node
class Node
{
public :
int data;
Node *left, *right, *next;
Node(int key)
{
data = key;
left = right = next = NULL;
}
};
/*a utility function to Set next pointers of all descendents of par node
and recursively perform the same for left and right child of par (Preorder traversal)*/
void utility(Node* par)
{
// define base case
if (!par)
return;
// set next pointer of par's left child
if (par->left)
par->left->next = par->right;
/* set next pointer of par's right child
as per the method discussed above */
if (par->right)
par->right->next = (par->next) ? par->next->left : NULL;
/* recursively set next of children nodes
in a preorder fashion*/
utility(par->left);
utility(par->right);
}
/* function that sets next pointers of
nodes in the tree using utility function*/
void connect(Node *root)
{
if(!root)
return;
root->next = NULL;
utility(root);
}
// Function to print node values of a particular level
void printLevel(Node* root)
{
if(root == NULL)
{
cout<<endl;
return;
}
cout<<root->data<<" ";
printLevel(root->next);
}
int main()
{
/* create the binary tree*/
Node *root = NULL;
/* for above algorithm to work properly
we have to construct a complete binary tree */
root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->left->left->left = new Node(8);
root->left->left->right = new Node(9);
connect(root);
cout<<"1st Level : ";
printLevel(root);
cout<<"2nd Level : ";
printLevel(root->left);
cout<<"3rd Level : ";
printLevel(root->left->left);
cout<<"4th Level : ";
printLevel(root->left->left->left);
return 0;
}
1st Level : 1 2nd Level : 2 3 3rd Level : 4 5 6 7 4th Level : 8 9
Java Proqramı
import java.util.*;
import java.io.*;
class tutorialCup
{
// blueprint of the tree node
static class Node
{
int data;
Node left, right, next;
Node(int key)
{
data = key;
left = right = next = null;
}
}
/*a utility function to Set next pointers of all descendents of par node
and recursively perform the same for left and right child of par (Preorder traversal)*/
static void utility(Node par)
{
// define base case
if (par == null)
return;
// set next pointer of par's left child
if (par.left != null)
par.left.next = par.right;
/* set next pointer of par's right child
as per the method discussed above */
if (par.right != null)
par.right.next = (par.next != null)? par.next.left : null;
/* recursively set next of children nodes
in a preorder fashion*/
utility(par.left);
utility(par.right);
}
/* function that sets next pointers of
nodes in the tree using utility function*/
static void connect(Node root)
{
if(root == null)
return;
root.next = null;
utility(root);
}
// Function to print node values of a particular level
static void printLevel(Node root)
{
if(root == null)
{
System.out.println();
return;
}
System.out.print(root.data+" ");
printLevel(root.next);
}
// main Function to implement above function
public static void main (String[] args)
{
/* create the binary tree*/
Node root = null;
/* for above algorithm to work properly we have to construct a complete binary tree */
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(9);
connect(root);
System.out.print("1st Level : ");
printLevel(root);
System.out.print("2nd Level : ");
printLevel(root.left);
System.out.print("3rd Level : ");
printLevel(root.left.left);
System.out.print("4th Level : ");
printLevel(root.left.left.left);
}
}
1st Level : 1 2nd Level : 2 3 3rd Level : 4 5 6 7 4th Level : 8 9
Hər Nodda Növbəti Sağ İşarələrin doldurulması üçün Mürəkkəblik Təhlili
- Zamanın mürəkkəbliyi: T (n) = O (n)
- Kosmik Mürəkkəblik: A (n) = O (1)
Rekursiv
Hər Nodda Növbəti Sağ Göstəricilərin doldurulması üçün yanaşma
Bu yanaşma əvvəlki yanaşmaya bənzəyir, ancaq koddakı bəzi kiçik dəyişikliklərlə onu hər cür ikili ağaclar üçün işlədə bilərik (tamamlansın da, olmasın).
Fikir əsasən i səviyyədəki bütün qovşaqların növbəti göstəricilərinin (i + 1) -ci səviyyə düyünlərinin önündə olmasını təmin etməkdir. Bunu nizamlı şəkildə (valideynlər uşaqlardan əvvəl) yerinə yetirməklə, ancaq bir az dəyişiklik etməklə əldə edə bilərik.
Düyünləri aşağıdakı ardıcıllıqla keçirik: (valideyn, bir valideynin sağında, sol uşağı, sağ uşağı).
Bu şəkildə, i-ci səviyyədəki bütün qovşaqlar (i + 1) -ci səviyyə düyünlərinin önünə qoyulur.
İndi məqsədimizə çatmaq üçün aşağıdakı addımları izləyə bilərik:
- Valideyn qovşağının sol övladının növbəti göstəricisini təyin etdikdə, valideynin sağ övladının olub-olmadığını yoxlayırıq.
- Doğru uşaq varsa, sadəcə təyin edirik sonrakı sol uşağın sağına. yəni par-> sol-> sonrakı = par-> sağ.
- Başqa bir vəziyyətdə, ilk düymənin ünvanını əsasən sol uşağın sağında qaytaran və sadəcə təyin edən nextRight () funksiyasından istifadə edirik. sonrakı soldan qovşağa döndü. yəni par-> left-> next = nextRight (par).
- nextRight () ana qovşaqdan istifadə edir (para) və onun sonrakı göstərici (par-> növbəti), ilk yarpaqsız (və övladının qayıdış ünvanını - solda / sağda, hansi olursa olsun) eyni səviyyədə sağa doğru düyünü axtarmaq.
- Ana düyünün sağ övladı üçün, nüvənin ünvanını sağ uşağın sağ tərəfinə eyni səviyyədə qaytarmaq və onu təyin etmək üçün sadəcə nextRight () funksiyasından istifadə edirik. sonrakı qaytarılmış ünvana işarə. yəni par-> right-> next = nextRight ().
- Eyni səviyyədə cari düyünün sağındakı qovşaq mövcud deyilsə, sadəcə qayıdırıq sıfır.
Alqoritm
- Cari düyünü ana düyün və bütün sonrakı indiki səviyyədə göstəricilər artıq təyin edilmişdir.
- Ana düyünün sol uşağını düşünün (əgər varsa):
- Doğru uşaq varsa, təyin edin sonrakı valideynin sol uşağından sağ uşağına. yəni par-> sol-> sonrakı = par-> sağ.
- Başqa bir şəkildə, eyni səviyyədə növbəti qovluğu tapın və təyin edin sonrakı sol uşağın, yəni par-> left = nextRight (par).
- Üçün yuxarıdakı 2 addımı təkrarən yerinə yetirin sonrakı sol uşağın. (yəni par-> sol-> sonrakı).
- Bu şəkildə eyni səviyyədə olan bütün qovşaqlar qurulmuşdur.
- Sol yoxdursa, ana düyünün sağ uşağını nəzərdən keçirin.
- eyni səviyyədə növbəti qovluğu tapın və təyin edin sonrakı sağ uşağın, yəni par-> right = nextRight (par).
- Üçün 2.1 və 2.2 addımlarını təkrarən yerinə yetirin sonrakı sağ uşağın. (yəni par-> sağ-> sonrakı).
- Bu şəkildə eyni səviyyədə olan bütün qovşaqlar qurulmuşdur.
- Əgər hər ikisi uşaqda yoxdursa, onda təkrarlayın sonrakı ana düyünün. (yəni par-> sonrakı).
Yuxarıdakı alqoritm aşağıda təsvir edilmişdir:
Həyata keçirilməsi
C ++ Proqramı
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// blueprint of the tree node
class Node
{
public :
int data;
Node *left, *right, *next;
Node(int key)
{
data = key;
left = right = next = NULL;
}
};
/* This function is used to get first pointer just to the right of children of par */
Node* nextRight(Node *par)
{
// start traversing nodes on the same level with par towards the right
Node* temp = par->next;
// move to right until a node with atleast one children is found
while(temp != NULL)
{
// return the first children of node to the right
if(temp->left != NULL)
return temp->left;
if(temp->right != NULL)
return temp->right;
// if node to the right has no children. Then,
// move to next node to the right on same level
temp = temp->next;
}
// If all the nodes at par level are leaf nodes then return null
return NULL;
}
// function to recursively set next of all children of parent node par
// It ensures that nodes at ith level are set before those at (i+1)th level
void utility(Node* par)
{
// base case
if (!par)
return;
/* before setting next pointers of children,
set next pointers of par and the nodes at the same level as par
*/
if (par->next != NULL)
utility(par->next);
/* Set the next pointer for par's left child */
if (par->left)
{
if (par->right)
{
par->left->next = par->right;
par->right->next = nextRight(par);
}
else
par->left->next = nextRight(par);
/* recursively call for next level nodes,
the call for left child would automatically call
all it's right child */
utility(par->left);
}
/* If left child is null then first node of next level is the right child */
else if (par->right)
{
par->right->next = nextRight(par);
utility(par->right);
}
/* if both the children of parent node are null,
then we move on to next node in the same level*/
else
utility(nextRight(par));
}
/* function that sets next pointers of
nodes in the tree using utility function*/
void connect(Node *root)
{
if(!root)
return;
root->next = NULL;
utility(root);
}
// Function to print node values of a particular level
void printLevel(Node* root)
{
if(!root)
{
cout<<endl;
return;
}
cout<<root->data<<" ";
printLevel(root->next);
}
int main()
{
/* construct the binary tree */
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(6);
root->left->left->left = new Node(7);
root->left->left->right = new Node(8);
root->right->right->right = new Node(9);
connect(root);
cout<<"1st Level : ";
printLevel(root);
cout<<"2nd Level : ";
printLevel(root->left);
cout<<"3rd Level : ";
printLevel(root->left->left);
cout<<"4th Level : ";
printLevel(root->left->left->left);
return 0;
}
1st Level : 1 2nd Level : 2 3 3rd Level : 4 5 6 4th Level : 7 8 9
Java Proqramı
import java.util.*;
import java.io.*;
class tutorialCup
{
// blueprint of the tree node
static class Node
{
int data;
Node left, right, next;
Node(int key)
{
data = key;
left = right = next = null;
}
}
/* This function is used to get first pointer just to the right of children of par */
static Node nextRight(Node par)
{
// start traversing nodes on the same level with par towards the right
Node temp = par.next;
// move to right until a node with atleast one children is found
while(temp != null)
{
// return the first children of node to the right
if(temp.left != null)
return temp.left;
if(temp.right != null)
return temp.right;
// if node to the right has no children. Then,
// move to next node to the right on same level
temp = temp.next;
}
// If all the nodes at par level are leaf nodes then return null
return null;
}
// function to recursively set next of all children of parent node par
// It ensures that nodes at ith level are set before those at (i+1)th level
static void utility(Node par)
{
// base case
if (par == null)
return;
/*
before setting next pointers of children,
set next pointers of par and the nodes at the same level as par
*/
if (par.next != null)
utility(par.next);
/* Set the next pointer for par's left child */
if (par.left != null)
{
if (par.right != null)
{
par.left.next = par.right;
par.right.next = nextRight(par);
}
else
par.left.next = nextRight(par);
/* recursively call for next level nodes,
the call for left child would automatically call
all it's right child */
utility(par.left);
}
/* If left child is null then first node of next level is the right child */
else if (par.right != null)
{
par.right.next = nextRight(par);
utility(par.right);
}
/* if both the children of parent node are null,
then we move on to next node in the same level*/
else
utility(nextRight(par));
}
/* function that sets next pointers of
nodes in the tree using utility function*/
static void connect(Node root)
{
if(root == null)
return;
root.next = null;
utility(root);
}
// Function to print node values of a particular level
static void printLevel(Node root)
{
if(root == null)
{
System.out.println();
return;
}
System.out.print(root.data+" ");
printLevel(root.next);
}
// main Function to implement above function
public static void main (String[] args)
{
/* construct the binary tree */
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.left.left.left = new Node(7);
root.left.left.right = new Node(8);
root.right.right.right = new Node(9);
connect(root);
System.out.print("1st Level : ");
printLevel(root);
System.out.print("2nd Level : ");
printLevel(root.left);
System.out.print("3rd Level : ");
printLevel(root.left.left);
System.out.print("4th Level : ");
printLevel(root.left.left.left);
}
}
1st Level : 1 2nd Level : 2 3 3rd Level : 4 5 6 4th Level : 7 8 9
Hər Nodda Növbəti Sağ İşarələrin doldurulması üçün Mürəkkəblik Təhlili
- Zamanın mürəkkəbliyi: T (n) = O (n)
- Kosmik Mürəkkəblik: A (n) = O (1)
Iterative
Hər Nodda Növbəti Sağ Göstəricilərin doldurulması üçün yanaşma
Fikir yuxarıdakı rekursiv kodu təkrarlanan bir kod halına gətirməkdir. Kod, iç içə ikiqat döngələrdən ibarətdir. Xarici döngə ağac səviyyələrindən (və ya nəsillərdən) aşağıya doğru hərəkət etmək üçün istifadə olunur və daxili döngə müəyyən bir səviyyədə bütün qovşaqları keçmək üçün istifadə olunur. Müəyyən bir səviyyədə olan bütün qovşaqlarla məşğul olduqdan sonra növbəti səviyyəyə keçirik.
Fikir əsasən i səviyyədəki bütün qovşaqların növbəti göstəricilərinin (i + 1) -ci səviyyə düyünlərinin önündə olmasını təmin etməkdir. Bunu nizamlı şəkildə (valideynlər uşaqlardan əvvəl) yerinə yetirməklə, ancaq bir az dəyişiklik etməklə əldə edə bilərik.
Düyünləri aşağıdakı ardıcıllıqla keçirik: (valideyn, bir valideynin sağında, sol uşağı, sağ uşağı).
Bu şəkildə, i-ci səviyyədəki bütün qovşaqlar (i + 1) -ci səviyyə düyünlərinin önünə qoyulur.
İndi məqsədimizə çatmaq üçün aşağıdakı addımları izləyə bilərik:
- Valideyn qovşağının sol övladının növbəti göstəricisini təyin etdikdə, valideynin sağ övladının olub olmadığını yoxlayırıq.
- Doğru uşaq varsa, sadəcə təyin edirik sonrakı sol uşağın sağına. yəni par-> sol-> sonrakı = par-> sağ.
- Başqa bir vəziyyətdə, ilk düymənin ünvanını əsasən sol uşağın sağında qaytaran və sadəcə təyin edən nextRight () funksiyasından istifadə edirik. sonrakı soldan qovşağa döndü. yəni par-> left-> next = nextRight (par).
- nextRight () ana qovşaqdan istifadə edir (para) və onun sonrakı göstərici (par-> növbəti), ilk yarpaqsız (və övladının qayıdış ünvanını - solda / sağda, hansi olursa olsun) eyni səviyyədə sağa doğru düyünü axtarmaq.
- Ana düyünün sağ övladı üçün, nüvənin ünvanını sağ uşağın sağ tərəfinə eyni səviyyədə qaytarmaq və onu təyin etmək üçün sadəcə nextRight () funksiyasından istifadə edirik. sonrakı qaytarılmış ünvana işarə. yəni par-> right-> next = nextRight ().
- Eyni səviyyədə cari düyünün sağındakı qovşaq mövcud deyilsə, sadəcə qayıdırıq sıfır.
Alqoritm
- Cari düyünü ana düyün və bütün sonrakı indiki səviyyədə göstəricilər artıq təyin edilmişdir.
- Ana düyünün sol uşağını düşünün (əgər varsa):
- Doğru uşaq varsa, təyin edin sonrakı valideynin sol uşağından sağ uşağına. yəni par-> sol-> sonrakı = par-> sağ.
- Başqa bir şəkildə, eyni səviyyədə növbəti qovluğu tapın və təyin edin sonrakı sol uşağın, yəni par-> left = nextRight (par).
- Üçün yuxarıdakı 2 addımı təkrarən yerinə yetirin sonrakı sol uşağın. (yəni par-> sol-> sonrakı).
- Bu şəkildə eyni səviyyədə olan bütün qovşaqlar qurulmuşdur.
- Sol yoxdursa, valideyn nodunun sağ uşağını nəzərdən keçirin.
- eyni səviyyədə növbəti qovluğu tapın və təyin edin sonrakı sağ uşağın, yəni par-> right = nextRight (par).
- Üçün 2.1 və 2.2 addımlarını təkrarən yerinə yetirin sonrakı sağ uşağın. (yəni par-> sağ-> sonrakı).
- Bu şəkildə eyni səviyyədə olan bütün qovşaqlar qurulmuşdur.
- Əgər hər ikisi uşaqda yoxdursa, deməli sonrakı ana düyünün. (yəni par-> sonrakı).
Yuxarıdakı alqoritm aşağıda təsvir edilmişdir:
Həyata keçirilməsi
C ++ Proqramı
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// blueprint of the tree node
class Node
{
public :
int data;
Node *left, *right, *next;
Node(int key)
{
data = key;
left = right = next = NULL;
}
};
/* This function is used to get first pointer just to the right of children of par */
Node* nextRight(Node *par)
{
// start traversing nodes on the same level with par towards the right
Node* temp = par->next;
// move to right until a node with atleast one children is found
while(temp != NULL)
{
// return the first children of node to the right
if(temp->left != NULL)
return temp->left;
if(temp->right != NULL)
return temp->right;
// if node to the right has no children. Then,
// move to next node to the right on same level
temp = temp->next;
}
// If all the nodes at par level are leaf nodes then return null
return NULL;
}
// function to Iteratively set next of all children of parent node par
// It ensures that nodes at ith level are set before those at (i+1)th level
void connect(Node *root)
{
if (!root)
return;
// set next for root
root->next = NULL;
// set next of all nodes in the current level
// after which Iterate to next level
while (root != NULL)
{
Node* par = root;
/* Connect all childrem nodes of par and
children nodes of all other nodes at
same level as par */
while (par != NULL)
{
// set the next pointer for par's left child
if (par->left)
{
if (par->right)
par->left->next = par->right;
else
par->left->next = nextRight(par);
}
// set next for par's right children
if (par->right)
par->right->next = nextRight(par);
// set next of all the nodes on the same level as children of par
par = par->next;
}
// After processing all the nodes of current Level
// move down to next level
if (root->left)
root = root->left;
else if (root->right)
root = root->right;
else
root = nextRight(root);
}
}
// Function to print node values of a particular level
void printLevel(Node* root)
{
if(!root)
{
cout<<endl;
return;
}
cout<<root->data<<" ";
printLevel(root->next);
}
int main()
{
/* construct the binary tree */
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(6);
root->left->left->left = new Node(7);
root->left->left->right = new Node(8);
root->right->right->right = new Node(9);
connect(root);
cout<<"1st Level : ";
printLevel(root);
cout<<"2nd Level : ";
printLevel(root->left);
cout<<"3rd Level : ";
printLevel(root->left->left);
cout<<"4th Level : ";
printLevel(root->left->left->left);
return 0;
}
1st Level : 1 2nd Level : 2 3 3rd Level : 4 5 6 4th Level : 7 8 9
Java Proqramı
import java.util.*;
import java.io.*;
class tutorialCup
{
// blueprint of the tree node
static class Node
{
int data;
Node left, right, next;
Node(int key)
{
data = key;
left = right = next = null;
}
}
/* This function is used to get first pointer just to the right of children of par */
static Node nextRight(Node par)
{
// start traversing nodes on the same level with par towards the right
Node temp = par.next;
// move to right until a node with atleast one children is found
while(temp != null)
{
// return the first children of node to the right
if(temp.left != null)
return temp.left;
if(temp.right != null)
return temp.right;
// if node to the right has no children. Then,
// move to next node to the right on same level
temp = temp.next;
}
// If all the nodes at par level are leaf nodes then return null
return null;
}
// function to Iteratively set next of all children of parent node par
// It ensures that nodes at ith level are set before those at (i+1)th level
static void connect(Node root)
{
if (root == null)
return;
// set next for root
root.next = null;
// set next of all nodes in the current level
// after which Iterate to next level
while (root != null)
{
Node par = root;
/* Connect all children nodes of par and
children nodes of all other nodes at
same level as par */
while (par != null)
{
// set the next pointer for par's left child
if (par.left != null)
{
if (par.right != null)
par.left.next = par.right;
else
par.left.next = nextRight(par);
}
// set next for par's right children
if (par.right != null)
par.right.next = nextRight(par);
// set next of all the nodes on the same level as children of par
par = par.next;
}
// After processing all the nodes of current Level
// move down to next level
if (root.left != null)
root = root.left;
else if (root.right != null)
root = root.right;
else
root = nextRight(root);
}
}
// Function to print node values of a particular level
static void printLevel(Node root)
{
if(root == null)
{
System.out.println();
return;
}
System.out.print(root.data+" ");
printLevel(root.next);
}
// main Function to implement above function
public static void main (String[] args)
{
/* construct the binary tree */
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.left.left.left = new Node(7);
root.left.left.right = new Node(8);
root.right.right.right = new Node(9);
connect(root);
System.out.print("1st Level : ");
printLevel(root);
System.out.print("2nd Level : ");
printLevel(root.left);
System.out.print("3rd Level : ");
printLevel(root.left.left);
System.out.print("4th Level : ");
printLevel(root.left.left.left);
}
}
1st Level : 1 2nd Level : 2 3 3rd Level : 4 5 6 4th Level : 7 8 9
Hər Nodda Növbəti Sağ İşarələrin doldurulması üçün Mürəkkəblik Təhlili
- Zamanın mürəkkəbliyi: T (n) = O (n)
- Kosmik Mürəkkəblik: A (n) = O (1)
