완전 이진트리와 Thread이진트리를 생성하고 순회하는 프로그램

소개

A+받은 레포트이며 적절한 문제분석과 소스코드, 주석, 실행화면등이 들어 있습니다.

하나의 노드 집합으로 각각 완전 이진트리와 Thread이진트리를 생성하고 순회하는 프로그램을 만드는것. 트리는 생성과 삽입, 삭제가 가능하고 parent field를 가진 트리는 후위순회를 하고 Thread이진트리는 중위순회를 하는 프로그램을 만드는 것이다. 부가사항으로 트리의 모양이 출력되어야 한다.

컴파일 실행환경

visuall c++

본문내용

#1 문제개요
하나의 노드 집합으로 각각 완전 이진트리와 Thread이진트리를 생성하고 순회하는 프로그램을 만드는것. 트리는 생성과 삽입, 삭제가 가능하고 parent field를 가진 트리는 후위순회를 하고 Thread이진트리는 중위순회를 하는 프로그램을 만드는 것이다. 부가사항으로 트리의 모양이 출력되어야 한다.



#2 알고리즘
■ parent field를 갖는 완전 이진트리
□ 생성: 트리노드 클래스에는 왼쪽 자식, 오른쪽 자식, 부모, next멤버변수가 있으며 생성을 하기 위해서는 next가 가르치는 곳이 왼쪽자식, 오른쪽 자식을 삽입하는 부모노드가 되며 make라는 멤버변수는 새로 생성한 노드가 되도록 하여서 next를 계속적으로 레벨순위방식으로 연결하게 하였다.

□ 출력: 노드의 개수에 따라서 레벨별로 구분하여 출력할 수 있게 하였다.

□ 삭제: 완전이진트리는 마지막노드를 삭제함으로 마지막노드를 찾아서 그 노드를 삭제하였다. 삭제한 노드의 부모의 오른쪽과 왼쪽 노드는 다시 0으로 만들었다.

□ 후위순회: 트리 각각의 모양을 제어문을 통하여 순회하도록 하였다.


■ 쓰레드를 갖는 완전 이진트리
□ 생 성: 쓰레드트리노드 클래스에는 왼쪽 자식, 오른쪽 자식, 왼쪽 쓰레드, 오른쪽 쓰레드, next멤버변수가 있으며 생성을 하기 위해서는 next가 가르치는 곳이 왼쪽자식과 오른쪽 자식을 삽입하는 부모노드가 되며 생성한 노드의 왼쪽 쓰레드와 오른쪽 쓰레드는 True값을 가지며 각각의 경우에 따라 쓰레드가 True일때 가리키는 곳이 달라진다.

□ 출 력: 노드의 개수에 따라서 레벨별로 구분하여 출력할 수 있게 하였다.

□ 삭 제: 완전이진트리는 마지막노드를 삭제함으로 마지막노드를 찾아서 그 노드를 삭제하였다. 삭제한 노드의 부모의 왼쪼 쓰레드와 오른쪽 쓰레드는 경우에 따라서 True 값을 가지도록 하였다.

□ 중위순회: 트리의 오른쪽 쓰레드를 따라서 순회하기만 하면 중위순회를 할 수 있도록 하였다.

참고자료

· 없음