이진 검색 트리는 이진 트리 구조에 따라 구성됩니다. 이러한 트리는 연결된 목록 구조로 표현될 수 있으며, 여기서 각 노드는 객체입니다. 데이터 외에도 노드에는 각각 노드의 왼쪽 아들과 오른쪽 아들을 가리키는 왼쪽, 오른쪽 및 p 필드도 포함됩니다. 노드가 존재하지 않으면 NULL입니다.
이는 빈 트리이거나 다음 속성을 가진 이진 트리입니다.
1) 왼쪽 하위 트리가 비어 있지 않으면 왼쪽 하위 트리의 모든 노드 값은 루트 노드 값보다 작습니다.
(2) 오른쪽 하위 트리가 비어 있지 않으면 오른쪽 하위 트리에 있는 모든 노드의 값이 해당 루트 노드의 값보다 큽니다.
(3) 왼쪽과 오른쪽 하위 트리도 각각 이진 검색 트리입니다.
분명히 위의 속성이 충족되면 이진 검색 트리를 중순으로 순회한다는 것은 작은 것부터 큰 것의 순서로 순회하는 것을 의미합니다. 이것이 정렬 트리라고 불리는 이유입니다. 물론 위의 보다 작음과 보다 큼은 사용자의 요구에 따라 변경될 수 있습니다. 자신의 필요.
이진 검색 트리의 몇 가지 일반적인 작업: 검색, 삭제 및 삽입.
HDU 3791:
문제 설명
두 시퀀스가 동일한 이진 검색 트리 시퀀스인지 확인
입력
숫자 n으로 시작하고, (1<=n<=20)은 판단해야 할 숫자가 n개 있다는 뜻이며, n= 0일 때 입력이 종료됩니다.
다음 줄은 시퀀스입니다. 시퀀스의 길이는 10보다 작고 숫자(0~9)를 포함합니다. 이 시퀀스를 기반으로 이진 검색 트리를 구성할 수 있습니다.
다음 n개 라인에는 n개의 시퀀스가 있습니다. 각 시퀀스의 형식은 첫 번째 시퀀스와 동일합니다. 이 두 시퀀스가 동일한 이진 검색 트리를 형성할 수 있는지 확인하세요.
산출
시퀀스가 동일하면 YES를 출력하고, 그렇지 않으면 NO를 출력합니다.
샘플 입력
2
567432
543267
576342
0
샘플 출력
예
아니요
설명: 숫자를 순서대로 삽입한 후 이진 트리 선주문 순회를 사용하여 두 이진 트리가 동일한지 확인합니다.
자바 코드
다음과 같이 코드 코드를 복사합니다 .
java.util.Scanner 가져오기;
공개 클래스 메인{
공개 정적 무효 메인(문자열 인수[]){
스캐너 입력=새 스캐너(System.in);
BinarySearchTree<Character> 루트=null;
동안(in.hasNext()){
int t=in.nextInt();
if(t==0) 중단;
root=new BinarySearchTree<문자>();
문자열 결과=null;
문자열 결과1=null;
문자열 s=in.next();
for(int i=0;i<s.length();i++){
root.insert(s.charAt(i));
}
결과=root.printTree(root.getRoot());
for(int i=0;i<t;i++){
root=new BinarySearchTree<문자>();
s=in.next();
for(int j=0;j<s.length();j++){
root.insert(s.charAt(j));
}
result1=root.printTree(root.getRoot());
if(result.equals(result1)) System.out.println("YES");
else System.out.println("NO");
}
}
}
}
class BinaryNode< T 확장 Comparable<T>> {//이진 검색 트리 노드
BinaryNode<T> 왼쪽;
BinaryNode<T> 오른쪽;
T 요소;
공개 BinaryNode(T theElement){
this(theElement, null, null);
}
공개 BinaryNode(T theElement, BinaryNode lt, BinaryNode rt){
요소 = 요소;
왼쪽 = <
오른쪽 = rt;
}
공개 T getElement(){
this.element를 반환합니다.
}
공개 BinaryNode<T> getLeft(){
return this.left;
}
공개 BinaryNode<T> getRight(){
이것을 돌려주세요.맞습니다;
}
공개 문자열 toString(){
반환 요소 + "";
}
}
class BinarySearchTree< T는 Comparable<T>>{//이진 검색 트리를 확장합니다.
private BinaryNode<T> 루트;//루트 노드
공개 BinarySearchTree(){//생성자
루트 = null;
}
공개 BinarySearchTree(BinaryNode< T> t){//생성자
루트 = 티;
}
공공 무효 makeEmpty(){
루트 = null;
}
공개 부울 isEmpty(){
루트 == null을 반환합니다.
}
공개 BinaryNode<T> getRoot(){
루트를 반환;
}
공개 T find(T x){
return find(x, 루트).요소;
}
공개 무효 삽입(T x){
루트 = 삽입(x, 루트);
}
공공 무효 printTree(){
printTree(루트);
}
private BinaryNode< T> find(T x, BinaryNode< T> t){//찾기 작업
if(t==null){
null을 반환;
}
if(x.compareTo(t.element) < 0){
return find(x, t.left);
}
else if(x.compareTo(t.element) == 0){
t를 반환;
}
또 다른{
return find(x, t.right);
}
}
private BinaryNode< T> insert(T x, BinaryNode< T> t){//삽입 작업
if(t==null){
t = new BinaryNode<T>(x, null, null);
}
else if(x.compareTo(t.element) < 0){
t.left = insert(x, t.left);
}
else if(x.compareTo(t.element) > 0){
t.right = insert(x, t.right);
}
또 다른;
t를 반환;
}
개인 StringBuffer sb=new StringBuffer();
public String printTree(BinaryNode< T> t){//이진 검색 트리의 선주문 순회
if(t != null){
sb.append(t.element);
printTree(t.left);
printTree(t.right);
}
sb.toString()을 반환합니다.
}
}
