Độ sâu các nút của cây tìm kiếm nhị phân
Tichpx dạy về Cấu trúc dữ liệu cây tìm kiếm nhị phân quản lý ở mỗi nút là một số nguyên
Thao tác bổ sung một giá trị vào cây được thực hiện như sau:
Nếu trong cây có rồi thì không bổ sung
Nếu trong cây chưa có thì bổ sung bằng cách duyệt từ gốc nếu nhỏ hơn nút đang xét thì bổ sung sang trái, nếu lớn hơn thì bổ sung sang phải cứ như thế đến nút trống thì chèn vào
Độ sâu của một nút là số bước đi từ gốc đến nó, tất nhiên độ sâu của nút gốc sẽ là 0
Nhiệm vụ của bạn là thêm từ từ các phần tử của một dãy vào một cây tìm kiếm nhị phân sau khi thêm xong toàn bộ các phần tử bạn hãy duyệt cây theo trung thứ tự để xuất ra các nút tăng dần từ nhỏ đến lớn mỗi nút và độ sâu của nút đó
Input
Dòng đầu là số nguyên dương n \((1<=n<=10^4)\) là số phần tử của dãy
Dòng tiếp theo là n số nguyên dương \(a_!, a_2, ... a_n\) có giá trị không vượt quá \(10^4\)
Output
Xuất ra từng dòng là giá trị từng nút từ bé đến lớn và độ sâu tương ứng của nút đó
Ví dụ
Input
10
34 66 17 50 71 17 94 25 50 68Output
17 1
25 2
34 0
50 2
66 1
68 3
71 2
94 3
Comments
bài cây này mà update lên không cho dùng cây thì chắc cx đc đấy nhỉ :)