BST inorder traversal을 구현하는 방법은 무엇입니까?

Question

사실 내가 알고 싶은 것은 BST에 대한 순회 트래킹 알고리즘을 구현하는 방법이 아니라 BST에 삽입, 삭제 및 선주문 순회 알고리즘을 사용하여 구현하는 것입니다.
삽입, 삭제 및 선주문 순회를위한 표준 BST 알고리즘에 대한 구현이 있다고 가정 할 수 있습니다.

Answer 1

흠 ... 우리는 루트에 +와 왼쪽 노드에 1 개, 오른쪽 노드에 2 개가 있다고 가정 해 보겠습니다. 선주문은 + 1 2이고 순서는 1 + 2이 될 것입니다. 차이점은 1과 2가 바뀌었기 때문에 삽입과 삭제가 있으면 왼쪽 노드 값으로 각 루트 노드 값을 재귀 적으로 바꿀 수 있고 pre -order가 돌려주는 트리를 횡단하면 (자), inorder traversal가 발생합니다.

내가 갈 길이 멀지는 모르지만 도움이되기를 바랍니다.

Answer 2

나는 해결책을 찾았다 고 생각합니다. :)

우리는 선행 트래버스, 삽입 및 삭제 방법을 가지고 있습니다.

우리는 BST가 주어진다고 가정합니다.

우리는 선주문 순회 방법에 주어진 BST를 제공합니다. 사전 주문 순회는 항상 부모 노드로 이동하기 때문에 루트의 왼쪽 하위 트리가 null이 될 때까지 각 루트를 삭제하고 삽입합니다 (루트가 처음 만나는 부모이기 때문에).

이제 노드가 없어 질 때까지 루트를 삭제하기 시작합니다. 삭제 된 노드를 배열이나 원하는 곳에 배치하십시오. 정렬 된 노드 집합을 가져옵니다. (즉, 노드가 정렬 된 순서로 삭제됩니다. 가장 작은 것으로 첫 번째 등등 ...)