二叉搜索树问题

一 原问题描述

二叉搜索树 - HDU 3791 - Virtual Judgehttps://vjudge.net/problem/HDU-3791

二 输入和输出

1 输入

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。

接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。

接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

2 输出

如果序列相同则输出YES，否则输出NO

三 输入和输出样例

1 输入样例

2

567432

543267

576342

0

2 输出样例

YES

NO

三 分析

一棵树的中序遍历和先序遍历可以唯一确定一棵二叉树。所以可以先构造一棵二叉搜索树，此时中序遍历一样，如果先序遍历一样，则是同一棵二叉搜索树。

四 算法设计

1 使用二叉搜索树，先将每个数字都存进二叉搜索树，得到先序遍历。

2 将后面每一行的每个数字都存进二叉搜索树中，得到先序遍历，比较其是否相等，如果相等，则输出"YES"，否则输出"NO"。

五 代码

package hdu3791;

import java.util.Scanner;

public class HDU3791 {
    static int cnt;
    static String a; // 输入字符串
    static char b[] = new char[15]; // 原始序列先序序列
    static char c[] = new char[15]; // 其他序列的先序序列
    static Node root;

    static Node insert(Node root, int num) { //将x插入到二叉搜索树t中
        if (root == null) {
            // 树为空树的情况
            return new Node(num);
        }
        // 一个临时节点指向根节点，用于返回值
        Node tmp = root;
        Node pre = root;

        while (root != null && root.num != num) {
            // 保存父节点
            pre = root;
            if (num > root.num) {
                root = root.rc;
            } else {
                root = root.lc;
            }
        }
        // 通过父节点添加
        if (num > pre.num) {
            pre.rc = new Node(num);
        } else {
            pre.lc = new Node(num);
        }
        return tmp;
    }

    static void preorder(Node t, char b[]) {//中序遍历
        if (t != null) {
            b[cnt++] = (char) (t.num + '0');
            preorder(t.lc, b);
            preorder(t.rc, b);
        }
    }

    public static void main(String[] args) {
        int n;
        Scanner scanner = new Scanner(System.in);
        while (true) {
            n = scanner.nextInt();
            if (n == 0) {
                return;
            }

            cnt = 0;
            root = null;
            a = scanner.next();
            for (int i = 0; i < a.length(); i++)
                root = insert(root, a.charAt(i) - '0');
            preorder(root, b);
            b[cnt] = '\0';
            while (n-- > 0) {
                cnt = 0;
                root = null;
                a = scanner.next();
                for (int i = 0; i < a.length(); i++)
                    root = insert(root, a.charAt(i) - '0');
                preorder(root, c);
                c[cnt] = '\0';
                String sb = new String(b);
                String sc = new String(c);
                if (sb.equals(sc))
                    System.out.println("YES");
                else
                    System.out.println("NO");
            }
        }
    }
}

class Node {
    int num;
    Node lc;
    Node rc;

    Node(int num) {
        this.num = num;
    }
}

六 测试