트리 초록 데이터 유형

Question

데이터 구조 및 알고리즘이라는 단위를하고 있습니다. 우리는 방금 시작했고 교수는 대수적 의미론과 공리 등의 기초를 가르쳐주었습니다. 지금까지 나는 방금 어레이 형태의 나무를 사용했습니다. 사전 주문 트리의 서명을 트리 (값, 트리, 트리)로 사용하지 않으면 값은 노드의 값이 값이며 왼쪽 노드는 첫 번째 트리이고 오른쪽 노드는 두 번째 트리입니다.

이제 내 나무를 나무 (값, 나무, 나무) 또는 nil로 정의 했으므로 addnode (값, 트리)의 대수를 정의하는 방법을 알 수 없습니다.

그것은 각 레벨마다 점점 더 복잡해지고, 한 번 이후 한 번 이후 한 레벨을 스캔 할 것이라고 생각할 수는 없습니다. 대수는 우리가 나무를 내려 가면서 점점 더 많은 if eles로 분기됩니다. 내가 제대로하고 있습니까? 당신은 나를 올바른 방향으로 가리킬 수 있습니까? 아니면 나무 (값, 나무, 나무)로 나무를 구현할 수 없습니까?

그것은 내 튜토리얼의 일부이지만 (추가 질문에서는 가치가 없습니다), 나는 즉각적인 대답을 찾고 있지 않습니다. 나는 주제를 좋아하고 더 배우고 싶습니다.

편집 1 : Wikipedia를 확인했는데 명확한 답변을 위해 교과서를 사용하고 싶지 않습니다. 제 접근 방식이 옳은지 또는 트리를 나무 (가치, 나무, 나무). 나는 당신이 목록 형태의 트리 adt를 대표 할 수 있다는 것을 알고 있습니다. 그러나 나는 그것에 대해 정말로 생각하고 싶었습니다. 그것이 이해되기를 바랍니다. 감사합니다.

편집 2 : 음, 인터넷을 통해 설명하기가 어렵습니다. "트리"라는 새로운 데이터 구조를 정의한다고 가정 해 봅시다. 나는 내가 원하는 방식으로 정의 할 수 있으며, 균형 잡힌 이진 트리처럼 행동해야합니다 (하지만 부모와 자녀의 가치는 중요하지 않습니다). 나무로 정의합니다. 나무 (가치, 나무, 나무) 또는 nil 프로그래밍 코드가 아닙니다. , 그것은 내가 그것을 정의하는 방식입니다. 나무는 값 + 2 개의 다른 나무 나 나무는 nil입니다. 이제 추가 노드 (값, 트리)는 균형을 유지하면서 트리에 노드를 추가합니다. 그것은 프로그래밍 코드가 아니라 대수적 의미론 일뿐입니다. 제대로 설명 할 수 있는지 모르겠습니다. 그러나 대기열이나 스택을 사용하여 달성 할 수있는 솔루션을 얻었지만, 이는 정의해야 할 또 다른 ADT입니다.

편집 3 : 문제가 실제로 예상보다 어려워지는 많은 것들을 가정 한 것 같습니다. 우선, 내가 준 작은 설명에서 Gamecat의 대답은 완벽했습니다. 그러나 나는 의견에 동의합니다. 다른 광고를 포함시키는 것은 완벽하게 유효합니다. 실제로, 우리가 INT를 사용하는 것을 만들 때, 우리는 해당 구조에 ADT를 사용하고 있습니다. 나는 각 ADT가 독특해야한다고 생각했다. 어쨌든, 답변 해 주셔서 감사합니다!

Answer 1

트리에 노드를 추가하려면 재귀 기능을 사용할 수 있습니다.

나는 나무가 주문되었다고 가정한다. 그래서 당신은 다음과 같은 것을 얻어야합니다.

AddNode(value, tree)

if tree is empty, create a new tree with value as node and no subtrees.
if value lesser than the treenode, call AddNode on the left branch.
else call AddNode on the right branch. (if duplicates are allowed).

하위 트리가 변경되면 업데이트하십시오!

이것을 재귀 함수로 변환 할 수 있습니다.

if tree is empty, return a new tree with value as node and no subtrees.
if value is lesser than treenode, and there is no left subtree, create a new left subtree with value as node and no subtrees.
if value is lesser that treenode, and there is a left subtree, try again with the left subtree.
if value is greater or equal than treenode, and there is no right subtree, create a new right subtree with value as node and no subtrees.
if value is greater or equal than treenode, and there is a right subtree, try again with the right subtree.

나무의 균형을 유지 해야하는 경우. 저장은 균형 무게를 얻습니다 (-1, 0 또는 1 일 수 있음). "무거운"사이트에 노드를 추가 해야하는 경우이를 개편해야합니다. 예를 들어 왼쪽에 오른쪽보다 하나가 하나 더 있고 왼쪽에 노드 하나를 추가 해야하는 경우. 왼쪽 하위 트리에서 가장 높은 값으로 노드를 가져 와서 현재 상단으로 홍보해야합니다. 이전 상단은 오른쪽 하위 트리에 추가됩니다. 하위 트리의 균형을 유지하십시오.

예 : 노드 추가 0,1,2,3,4

Add(0)           0

Add(1)           0
                  \
                   1

Add(2)           0 (2)  =>      1 (2) =>  1
                  \            /         / \
                   1          0         0   2

Add(3)           1
                / \
               0   2
                    \ 
                     3

Add(4)           1 (4)     => 2 (4)  =>      2
                / \          / \            / \
               0   2        1   3          1   3
                    \      /              /     \
                     3    0              0       4

Answer 2

이것은 너무 모호하기 때문에 어려운 질문입니다. 나는 당신이 당신의 코스 자료의 일부로 교과서 나 무언가를 가지고 있다고 가정합니다. 그럼에도 불구하고, 당신이 문제가있는 많은 것들이 Wikipedia 항목 이진 나무에.

이 페이지에서는 다양한 나무 통과 방법과 나무를 나타내는 방법을 설명합니다.