二叉搜索树BST的特色

• 左<根<右
• 中序序列有序

二叉搜索树构造

1. 树为空，新结点作为根
2. 树不空，新结点与树根比大小
   • 大往右走，
   • 小往左走
3. 新结点插入空位

例题

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

struct TreeNode{
    int data;
    TreeNode * leftChild;
    TreeNode * rightChild;
};
struct QueueNode{
    TreeNode *parent;
    bool isLeftIn;
};

void insert_BST(TreeNode* &root,int data){
    TreeNode * new_node = new TreeNode;
    new_node->data = data;
    new_node->leftChild = NULL;
    new_node->rightChild = NULL;
    if (root ==NULL){
        root = new_node;
        printf("-1\n");
    } else{
        TreeNode * c_parent = root;
        TreeNode * current;
        while (true){
            if (data<c_parent->data){
                current = c_parent->leftChild;
                if (current == NULL){
                    c_parent->leftChild = new_node;
                    printf("%d\n",c_parent->data);
                    break;
                }else{
                    c_parent=current;
                }
            }
            if (data>c_parent->data){
                current = c_parent->rightChild;
                if (current == NULL){
                    c_parent->rightChild = new_node;
                    printf("%d\n",c_parent->data);
                    break;
                }else{
                    c_parent=current;
                }
            }
        }
    }
}

int main() {
    TreeNode *root=NULL;
    int arry[200];
    int n;
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&arry[i]);
    }
    for (int i = 0; i < n; ++i) {
        insert_BST(root,arry[i]);
    }
    return 0;
}

BST判定

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

struct TreeNode{
    char data;
    TreeNode * leftChild;
    TreeNode * rightChild;
};

void insert_BST(TreeNode* &root,int data){
    TreeNode * new_node = new TreeNode;
    new_node->data = data;
    new_node->leftChild = NULL;
    new_node->rightChild = NULL;
    if (root ==NULL){
        root = new_node;
    } else{
        TreeNode * c_parent = root;
        TreeNode * current;
        while (true){
            if (data<c_parent->data){
                current = c_parent->leftChild;
                if (current == NULL){
                    c_parent->leftChild = new_node;
                    break;
                }else{
                    c_parent=current;
                }
            }
            if (data>c_parent->data){
                current = c_parent->rightChild;
                if (current == NULL){
                    c_parent->rightChild = new_node;
                    break;
                }else{
                    c_parent=current;
                }
            }
        }
    }
}
string midOrder(TreeNode* root){
    if (root==NULL){
        return "";
    }
    return midOrder(root->leftChild)+root->data+ midOrder(root->rightChild);
}
string preOrder(TreeNode* root){
    if (root==NULL){
        return "";
    }
    return root->data+preOrder(root->leftChild)+ preOrder(root->rightChild);
}

int main() {
    int n;
    while(scanf("%d",&n)!=EOF){
        if (n==0){
            break;
        }
        char str1[100];
        scanf("%s",str1);
        TreeNode *root1 = NULL;
        for (int i = 0; str1[i]!='\0' ; ++i) {
            insert_BST(root1,str1[i]);
        }
        string preOrder1 = preOrder(root1);
        string midOrder1 = midOrder(root1);
//        printf("%s %s",preOrder1.c_str(),midOrder1.c_str());

        char str2[100];
        for (int i = 0; i < n; ++i) {
            scanf("%s",str2);
            TreeNode*root2=NULL;
            for (int j = 0; str2[j]!='\0'; ++j) {
                insert_BST(root2,str2[j]);
            }
            string preOrder2 = preOrder(root2);
            string midOrder2 = midOrder(root2);
            if (preOrder1==preOrder2&&midOrder1==midOrder2){
                printf("YES\n");
            }else{
                printf("NO\n");
            };
        }
    }

    return 0;
}