수색…
비고
나무는 노드 가장자리 그래프의 하위 범주 또는 하위 유형입니다. 그것들은 많은 다른 알고리즘 구조에 적용되는 많은 다른 알고리즘 구조의 모델로서 보급되기 때문에 컴퓨터 과학에서 보편적으로 사용됩니다
소개
나무 는 좀 더 일반적인 노드 - 에지 그래프 데이터 구조의 하위 유형입니다.
나무가 되려면 그래프가 다음 두 가지 요구 사항을 충족해야합니다.
- 그것은 비순환 적이다. 사이클 (또는 "루프")이 없습니다.
- 그것은 연결되어 있습니다. 그래프의 주어진 노드에 대해 모든 노드에 도달 할 수 있습니다. 모든 노드는 그래프의 한 경로를 통해 도달 할 수 있습니다.
트리 데이터 구조는 컴퓨터 과학에서 매우 일반적입니다. 나무는 일반적인 이진 나무, 빨강 검정 나무, B 나무, AB 나무, 23 나무, 힙 및 시도와 같은 다양한 알고리즘 데이터 구조를 모델링하는 데 사용됩니다.
다음과 같은 방법으로 트리를 Rooted Tree
라고 부르는 것이 일반적입니다.
choosing 1 cell to be called `Root`
painting the `Root` at the top
creating lower layer for each cell in the graph depending on their distance from the root -the bigger the distance, the lower the cells (example above)
나무에 대한 일반적인 기호 : T
전형적인 anary 트리 표현
일반적으로 우리는 이진 트리 (노드 당 정확히 두 개의 자식이있는 것)와 같은 anary 트리 (노드 당 잠재적으로 무한대의 자식이있는 트리)를 나타냅니다. "다음"자녀는 형제로 간주됩니다. 트리가 바이너리 인 경우이 표현은 추가 노드를 만듭니다.
우리는 형제를 반복하고 아이들을 되풀이합니다. 대부분의 나무는 상대적으로 얕기 때문에 어린이는 많이 있지만 계층 구조는 몇 가지 수준 밖에 없으므로 효율적인 코드가 생성됩니다. 인간 계보는 예외입니다 (많은 조상 수준, 한 수준 당 소수의 어린이).
필요한 경우 백 포인터를 유지하여 트리를 오름차순으로 유지할 수 있습니다. 이것들은 유지하기가 더 어렵습니다.
루트를 호출하는 함수와 여분의 매개 변수를 가진 재귀 함수 (이 경우에는 트리 깊이)를 갖는 것이 일반적입니다.
struct node
{
struct node *next;
struct node *child;
std::string data;
}
void printtree_r(struct node *node, int depth)
{
int i;
while(node)
{
if(node->child)
{
for(i=0;i<depth*3;i++)
printf(" ");
printf("{\n"):
printtree_r(node->child, depth +1);
for(i=0;i<depth*3;i++)
printf(" ");
printf("{\n"):
for(i=0;i<depth*3;i++)
printf(" ");
printf("%s\n", node->data.c_str());
node = node->next;
}
}
}
void printtree(node *root)
{
printree_r(root, 0);
}
두 이진수가 같거나 같은지 확인하려면
- 예를 들어 입력이 다음과 같은 경우 :
예 : 1
에이)
비)
출력은 true 여야합니다.
예 : 2
입력이 다음과 같은 경우 :
에이)
비)
출력은 false 여야합니다.
동일을위한 의사 코드 :
boolean sameTree(node root1, node root2){
if(root1 == NULL && root2 == NULL)
return true;
if(root1 == NULL || root2 == NULL)
return false;
if(root1->data == root2->data
&& sameTree(root1->left,root2->left)
&& sameTree(root1->right, root2->right))
return true;
}