이진 트리 데이터 구조

난이도 쉽게
자주 묻는 질문 디보이 팩트 셋 인포시스 MAQ 신탁
이진 트리 데이터 구조 이론 나무조회수 73

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

이 기사에서는 이진 트리 데이터 구조에 대해 읽을 것입니다. 나무 모든 노드에 루트 노드를 제외한 상위 노드가있는 계층 적 데이터 구조입니다. 자식이없는 노드를 잎이라고합니다.

나무가 필요하십니까?

1. 트리는 계층 구조의 형태로 데이터를 저장해야 할 때 사용됩니다. 예 :-파일 시스템.

2. BST와 같은 트리는 연결된 목록보다 빠른 O (logN) 복잡성으로 액세스를 제공합니다.

3. 트리에는 정의 된 크기가 없으며 임의의 수의 노드를 트리 데이터 구조에 추가 할 수 있습니다.

이진 트리

이진 트리 데이터 구조는 계층 적 데이터 구조입니다. 자식이 두 개 이하인 트리를 이진 트리라고합니다. Tts 두 자녀는 일반적으로 왼쪽 및 오른쪽 자녀로 알려져 있습니다.

이진 트리는 세 가지 구성 요소로 구성됩니다.

  1. 노드의 가치
  2. 왼쪽 하위 트리를 가리키는 포인터
  3. 오른쪽 하위 트리를 가리키는 포인터

 

왼쪽 자식에 대한 포인터 가치관  오른쪽 자식에 대한 포인터

루트가 가리키는 경우 NULL 그러면 그것은 빈 나무입니다.

이진 트리 데이터 구조를위한 노드

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

 

이진 트리 데이터 구조

이진 트리에서 사용되는 용어

  • 뿌리: It는 트리의 루트 노드를 가리키는 노드 포인터 변수입니다. 루트가 널을 포함하면 트리는 비어 있습니다.
  • 잎: XNUMX도를 갖는 노드. 외부 노드라고도합니다.
  • 내부 노드 : 하나 이상의 자식이있는 노드입니다.
  • 학위 : 노드의 총 자식 수를 등급이라고합니다.
  • 나무의 정도 : 트리의 등급은 모든 노드의 최대 등급입니다.
  • 수평: 루트에서 주어진 노드 -1까지의 총 노드 수입니다.
  • 노드의 높이 : 루트에서 주어진 노드까지의 총 노드 수입니다.

여기서 트리 노드의 정수 값은 모든 데이터 유형 ex로 대체 될 수 있습니다. 문자열, 문자, 배열 등. 이것은 트리의 모습입니다.

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 = 2의 최대 노드 수H + 1 - 1
  3. 이진 트리의 총 리프 노드 수 = 자식이 2 개인 총 노드 수 + 1
  4. 이진 트리의 모든 수준 'L'에서 최대 노드 수 = 2L

개요

1. 이진 트리는 노드 당 최대 XNUMX 개의 자식이있는 트리입니다.

2. 자식이없는 노드를 리프라고하고 시작 노드를 루트 노드라고합니다.

3. 트리는 액세스, 삽입, 삭제 작업을 어레이보다 빠르게 제공합니다.

참조

균열 시스템 설계 인터뷰
Translate »