Сохтори дутарафаи дарахт


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад DBOI Factset Infosys MAQ Oracle
Дарахти дуӣ Сохтори маълумот Теория Дарахт

Дар ин мақола, мо дар бораи сохтори маълумотҳои дутарафаи дарахт мехонем. Дарахтҳо инҳо сохторҳои иерархии маълумот мебошанд, ки дар онҳо ҳар як гиреҳ ба истиснои гиреҳи решавӣ гиреҳи волидайн дорад. Гиреҳҳое, ки фарзанд надоранд, барг номида мешаванд.

Ба дарахтон ниёз доред?

1. Дарахтон вақте истифода мешаванд, ки ба мо лозим аст маълумотро дар шакли баъзе иерархия нигоҳ дорем. Мисол: - Системаҳои файлӣ.

2. Дарахтон, ба монанди BST, дастрасиро дар мураккабии O (logN) таъмин мекунанд, ки нисбат ба рӯйхат - пайванд тезтар аст.

3. Дарахтон андозаи муайяне надоранд ва ҳар як миқдор гиреҳро ба сохтори маълумоти дарахт илова кардан мумкин аст.

Дарахти дуӣ

Сохтори дутарафаи дарахт сохтори иерархии маълумот аст. Дарахте, ки ҳадди аксар ду фарзанд дорад, дарахти дуӣ номида мешавад. Tts ду кӯдакон одатан ҳамчун фарзандони чап ва рост шинохта мешаванд.

Дарахти дуӣ аз се ҷузъ иборат аст:

  1. Арзиши гиреҳ
  2. Нишондиҳанда ба зери дарахти чап
  3. Нишондиҳанда ба зери дарахти рост

 

Нишон ба кӯдаки чап арзиши  Нишондиҳанда ба кӯдаки рост

Агар реша ишора карда бошад ночиз пас он дарахти холист.

Гиреҳ барои Сохтори Маълумоти дутарафаи дарахт

struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};

 

Сохтори дутарафаи дарахт

Истилоҳоте, ки дар дарахти дуӣ истифода мешаванд

  • Рут: It - тағирёбандаи нишоннамои гиреҳ барои ишора ба гиреҳи решаи дарахт. вақте ки реша нул дорад, дарахт холӣ аст.
  • Барг: гиреҳе, ки дараҷаи сифр дорад. Онро гиреҳи беруна низ меноманд.
  • Гиреҳи дохилӣ: Гиреҳ бо ҳадди аққал як кӯдак.
  • Дараҷа: Шумораи умумии кӯдакони гиреҳ ҳамчун дараҷаи он маълум аст.
  • Дараҷаи дарахт: дараҷаи дарахт дараҷаи максималии ҳамаи гиреҳҳо мебошад.
  • Сатҳи: Ин шумораи умумии гиреҳҳо аз реша то гиреҳи додашуда -1 мебошад.
  • Баландии гиреҳ: Ин шумораи умумии гиреҳҳо аз реша то гиреҳи додашуда мебошад

Дар инҷо арзиши бутуни дар гиреҳи дарахтбударо бо ягон намуди маълумот ex иваз кардан мумкин аст. сатр, char, массив ва ғ. Ин гуна дарахт ба назар мерасад

TREE 
              1 <-- root node 
             / \ 
            2   3 <-- leaf node 
          / 
         4 <- leaf node

Кодекси C ++ барои Сохтори Маълумоти дутарафаи дарахт

//C++ Code


#include<bits/stdc++.h>
using namespace std ;


struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};


/* CreateNode() creates a new node with the given data with NULL left and right pointers. */


TreeNode* CreateNode(int data)
{
// Allocate memory for new node
TreeNode* NewNode = new TreeNode ;


// Assign data to this node
NewNode->data = data;


// Initialize left and right children as NULL
NewNode->left = NULL;
NewNode->right = NULL;


return(NewNode);


}




int main()
{
/*create root with data value 1*/
struct TreeNode *root = CreateNode(1);


/* following is the tree after above statement


                    1
                  /   \
               NULL   NULL
*/


root->left = CreateNode(2);
root->right = CreateNode(3);




/* 2 and 3 become left and right children of 1
                             1
                          /     \
                        2         3
                    /      \    /    \
                  NULL    NULL NULL   NULL
*/




root->left->left = CreateNode(4);




/* 4 becomes left child of 2
                                      1
                                  /       \
                                 2          3
                              /    \     /     \
                             4   NULL   NULL   NULL
                           /   \
                        NULL   NULL
*/
return 0 ;
}

Рамзи Java барои Сохтори Маълумоти Дуӣ дарахт

/* Class containing left and right child of current 
node and key value*/
class Node 
{ 
	int key; 
	Node left, right; 

	public Node(int item) 
	{ 
		key = item; 
		left = right = null; 
	} 
} 

// A Java program to introduce Binary Tree 
class BinaryTree 
{ 
	// Root of Binary Tree 
	Node root; 

	// Constructors 
	BinaryTree(int key) 
	{ 
		root = new Node(key); 
	} 

	BinaryTree() 
	{ 
		root = null; 
	} 

	public static void main(String[] args) 
	{ 
		BinaryTree tree = new BinaryTree(); 

		/*create root*/
		tree.root = new Node(1); 

		/* following is the tree after above statement 

			1 
			/ \ 
		null null	 */

		tree.root.left = new Node(2); 
		tree.root.right = new Node(3); 

		/* 2 and 3 become left and right children of 1 
			1 
			/ \ 
			2	 3 
		/ \ / \ 
		null null null null */


		tree.root.left.left = new Node(4); 
		/* 4 becomes left child of 2 
					1 
				/	 \ 
			2		 3 
			/ \	 / \ 
			4 null null null 
		/ \ 
		null null 
		*/
	} 
} 

Хусусиятҳои сохтори маълумотҳои дутарафаи дарахт

  1. Шумораи ҳадди аққали гиреҳҳо дар дарахти дуӣ баландии H = H + 1.
  2. Шумораи максималии гиреҳҳо дарахти дуӣ дар баландии H = 2H + 1 - 1
  3. Шумораи умумии гиреҳҳои барги дарахти дуӣ = Шумораи умумии гиреҳҳо бо 2 фарзанд + 1
  4. Шумораи максималии гиреҳҳо дар ҳама сатҳҳои 'L' дарахти дуӣ = 2L

САВОЛҲО

1. Дарахти дуӣ ин дарахтест, ки дар як гиреҳ ҳадди аксар ду фарзанд дорад.

2. Гиреҳе, ки фарзанд надорад, барг ва гиреҳи оғоз гиреҳи реша номида мешавад.

3. Дарахт амалиётро фароҳам меорад: дастрасӣ, дохилкунӣ, несткунӣ нисбат ба массив.

Адабиёт