시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
이 기사에서는 이진 트리 데이터 구조에 대해 읽을 것입니다. 나무 모든 노드에 루트 노드를 제외한 상위 노드가있는 계층 적 데이터 구조입니다. 자식이없는 노드를 잎이라고합니다.
차례
나무가 필요하십니까?
1. 트리는 계층 구조의 형태로 데이터를 저장해야 할 때 사용됩니다. 예 :-파일 시스템.
2. BST와 같은 트리는 연결된 목록보다 빠른 O (logN) 복잡성으로 액세스를 제공합니다.
3. 트리에는 정의 된 크기가 없으며 임의의 수의 노드를 트리 데이터 구조에 추가 할 수 있습니다.
이진 트리
이진 트리 데이터 구조는 계층 적 데이터 구조입니다. 자식이 두 개 이하인 트리를 이진 트리라고합니다. Tts 두 자녀는 일반적으로 왼쪽 및 오른쪽 자녀로 알려져 있습니다.
이진 트리는 세 가지 구성 요소로 구성됩니다.
- 노드의 가치
- 왼쪽 하위 트리를 가리키는 포인터
- 오른쪽 하위 트리를 가리키는 포인터
| 왼쪽 자식에 대한 포인터 | 가치관 | 오른쪽 자식에 대한 포인터 |
루트가 가리키는 경우 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
*/
}
}
이진 트리 데이터 구조의 속성
- 이진 트리 높이 H = H + 1의 최소 노드 수입니다.
- 이진 트리 높이 H = 2의 최대 노드 수H + 1 - 1
- 이진 트리의 총 리프 노드 수 = 자식이 2 개인 총 노드 수 + 1
- 이진 트리의 모든 수준 'L'에서 최대 노드 수 = 2L
개요
1. 이진 트리는 노드 당 최대 XNUMX 개의 자식이있는 트리입니다.
2. 자식이없는 노드를 리프라고하고 시작 노드를 루트 노드라고합니다.
3. 트리는 액세스, 삽입, 삭제 작업을 어레이보다 빠르게 제공합니다.
