광고

트리를 나타내는 노드에 연결하여 가장자리입니다. 이진 트리 또는 이진 검색 트리에 대해 구체적으로 설명합니다.

이진 트리는 데이터 저장 목적으로 사용되는 특수 데이터 구조입니다. 이진 트리에는 각 노드가 최대 두 개의 자식을 가질 수있는 특별한 조건이 있습니다., 이진 나무는 장점을 모두의 주문한 배열과 연결된 목록으로 검색이 빠른으로 정렬된 배열하고 삭제하거나 삽입 작업은 빠른 속으로 연결된 목록입니다.

중요 용어

다음은 트리와 관련하여 중요한 용어입니다.

  • Path-Path 는 트리의 가장자리를 따라 노드의 시퀀스를 나타냅니다.

  • 루트−트리 상단의 노드를 루트라고합니다. 트리 당 하나의 루트와 루트 노드에서 임의의 노드로의 경로가 하나뿐입니다.,

  • 부모 노드 루트 노드를 제외하고는 하나의 가장자리 위로하라는 노드 부모입니다.

  • 자식−아래 가장자리로 연결된 주어진 노드 아래의 노드를 자식 노드라고합니다.

  • Leaf-자식 노드가없는 노드를 리프 노드라고합니다.

  • Subtree-Subtree 는 노드의 자손을 나타냅니다.

  • 방문-방문은 컨트롤이 노드에있을 때 노드의 값을 확인하는 것을 의미합니다.

  • Traversing-Traversing 은 특정 순서로 노드를 통과하는 것을 의미합니다.,

  • 레벨-노드의 레벨은 노드의 생성을 나타냅니다. 루트 노드가 레벨 0 에 있으면 그 다음 자식 노드는 레벨 1 에 있고 손자는 레벨 2 에 있습니다.

  • keys-Key 는 노드에 대해 검색 작업을 수행할 노드의 값을 나타냅니다.

이진 검색 트리 표현

이진 검색 트리는 특별한 동작을 나타냅니다. 노드의 왼쪽 아이가 보다 작은 값을 부모의 가치와 노드의 오른쪽 아이가 큰 값을 가지고 있어야합이 부모보다 값입니다.,

노드 객체를 사용하여 트리를 구현하고 참조를 통해 연결하려고합니다.

트리 노드

트리 노드를 작성하는 코드는 아래에 주어진 것과 유사합니다. 데이터 부분과 왼쪽 및 오른쪽 자식 노드에 대한 참조가 있습니다.

struct node { int data; struct node *leftChild; struct node *rightChild;};

트리에서 모든 노드는 공통 구조를 공유합니다.

BST 기본적인 운영

기본 작업에 대해 수행할 수 있는 이진 검색 나무 데이터 구조,다음과 같습니다−

  • 삽입하−요소를 삽입합니다 나무에서 만들 나무입니다.,

  • Search-트리에서 요소를 검색합니다.

  • 선주문 순회-선주문 방식으로 트리를 순회합니다.

  • Inorder Traversal-트리를 in-order 방식으로 트래버스합니다.

  • Postorder Traversal−사후 주문 방식으로 트리를 통과합니다.

이 장에서 트리 구조를 생성(삽입)하고 트리의 데이터 항목을 검색하는 방법을 배웁니다. 우리는 앞으로 장에서 나무 횡단 방법에 대해 배울 것입니다.

삽입 작업

맨 처음 삽입하면 트리가 생성됩니다., 그런 다음 요소를 삽입 할 때마다 먼저 적절한 위치를 찾습니다. 검색을 시작하는 루트 노드에서 다음 경우,데이터보다 작은 키 값 검색,빈에 위치 왼쪽 하위트리고 삽입하는 데이터입니다. 그렇지 않으면 오른쪽 하위 트리에서 빈 위치를 검색하고 데이터를 삽입하십시오.,

알고리즘

If root is NULL then create root nodereturnIf root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert dataend If

구현

의 구현 삽입 기능은 다음과 같아야 합니다−

검색 조작

때마다 요소를 검색,검색을 시작하는 루트 노드에서 다음 경우,데이터보다 작은 키 값을 검색하는 요소에서 왼쪽 하위 트리를 구성합니다. 그렇지 않으면 오른쪽 하위 트리에서 요소를 검색하십시오. 각 노드에 대해 동일한 알고리즘을 따르십시오.

알고리즘

If root.data is equal to search.data return rootelse while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if

이 알고리즘의 구현은 다음과 같아야합니다.,

이진 검색 트리 데이터 구조의 구현에 대해 알고 싶다면 여기를 클릭하십시오.

광고