二叉搜索樹實戰演練：從原理到 HDU 3791 題解完整指南

二叉搜索樹（BST）核心概念

二叉搜索樹是一種特殊的二叉樹結構，每個節點包含數據域以及指向左子節點、右子節點和父節點的指針（left、right、p）。其定義遵循三大核心性質：

1. 若左子樹不為空，則左子樹上所有節點的值均小於根節點的值；
2. 若右子樹不為空，則右子樹上所有節點的值均大於根節點的值；
3. 左右子樹分別也是二叉搜索樹。

基於這些性質，二叉搜索樹的中序遍歷天然產生遞增序列，故又稱「排序樹」。常用操作包括查找、插入與刪除。

經典題目：HDU 3791 - 判斷兩序列是否構成同一 BST

問題描述

輸入一個整數 n (1 ≤ n ≤ 20)，表示有 n 組待判斷序列；n=0 結束輸入。接著給出一個基準序列（長度 < 10，數字 0-9 不重複），據此構造一棵 BST。隨後 n 行每行一個序列，格式相同，需判斷該序列插入後形成的 BST 是否與基準樹完全相同。相同輸出 YES，否則 NO。

樣例輸入/輸出

Sample Input
2
567432
543267
576342
0

Sample Output
YES
NO

解題思路

按順序將數字插入 BST，再對兩棵樹進行先序遍歷，比較遍歷序列是否一致即可。先序遍歷能唯一確定樹的結構，因此是判斷樹同構的有效手段。

Java 完整實現

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int t = in.nextInt();
            if (t == 0) break;

            // 建立基準樹
            BinarySearchTree<Character> baseTree = new BinarySearchTree<>();
            String baseSeq = in.next();
            for (int i = 0; i < baseSeq.length(); i++) {
                baseTree.insert(baseSeq.charAt(i));
            }
            String basePreOrder = baseTree.printTree(baseTree.getRoot());

            // 逐組判斷
            for (int i = 0; i < t; i++) {
                BinarySearchTree<Character> cmpTree = new BinarySearchTree<>();
                String seq = in.next();
                for (int j = 0; j < seq.length(); j++) {
                    cmpTree.insert(seq.charAt(j));
                }
                String cmpPreOrder = cmpTree.printTree(cmpTree.getRoot());
                System.out.println(basePreOrder.equals(cmpPreOrder) ? "YES" : "NO");
            }
        }
    }
}

class BinaryNode<T extends Comparable<T>> {
    BinaryNode<T> left, right;
    T element;

    public BinaryNode(T theElement) { this(theElement, null, null); }
    public BinaryNode(T theElement, BinaryNode<T> lt, BinaryNode<T> rt) {
        element = theElement; left = lt; right = rt;
    }
    public T getElement() { return element; }
    public BinaryNode<T> getLeft() { return left; }
    public BinaryNode<T> getRight() { return right; }
    @Override public String toString() { return element + ""; }
}

class BinarySearchTree<T extends Comparable<T>> {
    private BinaryNode<T> root;
    private StringBuffer sb = new StringBuffer();

    public BinarySearchTree() { root = null; }
    public BinaryNode<T> getRoot() { return root; }

    public void insert(T x) { root = insert(x, root); }

    private BinaryNode<T> insert(T x, BinaryNode<T> t) {
        if (t == null) return new BinaryNode<>(x, null, null);
        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);
        return t;
    }

    public String printTree(BinaryNode<T> t) {
        sb.setLength(0); // 重置緩衝區
        preOrder(t);
        return sb.toString();
    }

    private void preOrder(BinaryNode<T> t) {
        if (t != null) {
            sb.append(t.element);
            preOrder(t.left);
            preOrder(t.right);
        }
    }
}

關鍵點總結

• 利用泛型 Comparable 實現通用比較邏輯；
• 先序遍歷序列作為樹結構的「指紋」進行比較；
• 每組測試數據獨立構建新樹，避免狀態污染。

掌握此題，可深化對 BST 構造、遍歷與樹同構判斷的理解，為解決更複雜的樹類問題打下基礎。