二分探索木は二分木構造に従って編成されます。このようなツリーは、各ノードがオブジェクトであるリンク リスト構造で表すことができます。データに加えて、ノードにはフィールド left、right、および p も含まれます。これらはそれぞれ、ノードの左子および右子を指します。ノードが存在しない場合、ノードは NULL になります。
これは空のツリー、または次のプロパティを持つバイナリ ツリーです。
1) 左のサブツリーが空でない場合、左のサブツリー上のすべてのノードの値はそのルート ノードの値より小さくなります。
(2) 右のサブツリーが空でない場合、右のサブツリー上のすべてのノードの値はそのルート ノードの値より大きくなります。
(3) 左側と右側のサブツリーもそれぞれ二分探索ツリーです。
明らかに上記のプロパティが満たされているため、二分探索ツリーを順番に走査することは、小さいものから大きいものへ順番に走査することを意味します。これがソート ツリーと呼ばれる理由です。自分自身のニーズ。
二分探索ツリーのいくつかの一般的な操作: 検索、削除、挿入。
HDU 3791:
問題の説明
2 つのシーケンスが同じ二分探索ツリー シーケンスであるかどうかを判断します。
入力
数値 n から開始する (1<=n<=20) は、判定する必要がある数値が n 個あり、n= 0 で入力が終了することを意味します。
次の行はシーケンスであり、シーケンスの長さは 10 未満であり、数字 (0 ～ 9) が含まれています。このシーケンスに基づいて二分探索ツリーを構築できます。
次の n 行には n 個のシーケンスがあり、各シーケンスの形式は最初のシーケンスと同じです。これら 2 つのシーケンスが同じ二分探索木を形成できるかどうかを判断してください。
出力
配列が同じ場合はYESを出力、そうでない場合はNOを出力
サンプル入力
2
567432
543267
576342
0
サンプル出力
はい
いいえ
説明: 番号を順番に挿入した後、バイナリ ツリー事前順序トラバーサルを使用して、2 つのバイナリ ツリーが同じかどうかを判断します。
Javaコード
次のようにコードをコピーします。
java.util.Scannerをインポートします。
パブリッククラスMain{
public static void main(String args[]){
スキャナー in=新しいスキャナー(System.in);
BinarySearchTree<Character> root=null;
while(in.hasNext()){
int t=in.nextInt();
if(t==0) ブレーク;
root=new BinarySearchTree<Character>();
文字列結果=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<Character>();
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 extends Comparable<T>> {//二分探索ツリー ノード
BinaryNode<T> 左;
BinaryNode<T> 右;
T要素;
public BinaryNode(T theElement){
this(theElement, null, null);
}
public BinaryNode(T theElement, BinaryNode lt, BinaryNode rt){
要素 = theElement;
左 = <
右 = RT;
}
public T getElement(){
this.要素を返します。
}
public BinaryNode<T> getLeft(){
this.left を返します。
}
public BinaryNode<T> getRight(){
this.right を返します。
}
public String toString(){
要素 + "" を返します。
}
}
class BinarySearchTree< T extends Comparable<T>>{//二分探索ツリー
private BinaryNode<T> root;//ルート ノード
public BinarySearchTree(){//コンストラクター
ルート = null;
}
public BinarySearchTree(BinaryNode< T> t){//コンストラクター
ルート = t;
}
public void makeEmpty(){
ルート = null;
}
パブリックブール値 isEmpty(){
ルート == null を返します。
}
public BinaryNode<T> getRoot(){
ルートを返します。
}
public T find(T x){
find(x, root).element を返します。
}
public void insert(T x){
ルート = 挿入(x, ルート);
}
public void 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 を返します。
}
それ以外{
find(x, t.right) を返します。
}
}
private BinaryNode< T> insert(T x, BinaryNode< T> t){//挿入操作
if(t==null){
t = 新しい 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()を返します;
}
}
