[자료구조] 트리를 구성한 후 원하는 노드의 위치를 알려주는 프로그램(큐와 스택 이용)

소개

[자료구조] 트리의 각 노드를 레벨오더 순으로 입력받아 트리를 구성하고 원하는 위치에 해당하는 노드를 알려주기

-파일을 통해 트리의 정보를 입력받아 레벨오더 순으로 큐를 사용하여 트리를 구성하고
원하는 위치에 해당하는 노드를 인오더검색을 통해 파일에 출력하는 프로그램입니다.

본 프로그램 실행 시 화면출력내용이 특별히 없어서 실행화면은 아니지만
트리가 실제로 구성되는 구조를 그림에 넣었습니다.

컴파일 실행환경

Microsoft visual c++ 6.0

참고자료

· - 문제 원문입니다.-
· 1. We are trying to lay out a binary tree in a lattice according to following rules. Note that the root node in the figure below is located in the first row and the tenth column.
· (i) If the levels of any two nodes are the same, they are located in the same row.
· The root node is always located in the first row.
· (ii) Only one node can be located in one column.
· (iii) The left subtree of a node is located in the left columns of the node, and the right subtree of a node is located in the right columns of the node.
· (iv) Each column between the leftmost node and the rightmost node has a node. Assume that the leftmost node is located in the first column.
· Each node in a binary tree that is given as an input has unique row and column number. Write a C++ program that takes a binary tree and a column number as an input and display the node number as an output.
· Input Format (Standard Input)
· (i) One or more test cases are provided. The first line of each case has the number of nodes, N, in a binary tree, and the column number, C, where a selected node is located. (0<N<100). Assume a root node has a node number 1. From the second line, each line has an information on a node which contains the number of left child and right child of the node. If there is no left or right child, the child node number will become -1. The information of each node is given with an order from the node number 1 to N. The last line of the input is 0 to indicate it is the end of the input.
· Output Format (Standard Output)
· For each test case, print out the number of the node that is located in the selected column C. The result of each case should be separated by the new line character 'n'.
· Input example
· 19 6
· 2 3
· 4 5
· 6 7
· 8 -1
· 9 10
· 11 12
· 13 -1
· -1 -1
· 14 15
· -1 -1
· 16 -1
· -1 -1
· 17 -1
· -1 -1
· 18 -1
· -1 -1
· -1 19
· -1 -1
· -1 -1
· 7 4
· 2 3
· 5 6
· 4 -1
· -1 -1
· 7 -1
· -1 -1
· -1 -1
· 0
· Output example
· 18
· 6