二叉排序树的基本操作 （C++代码）递归建立BST

解题思路:
重点都注释了

温馨提示：

判断自己的BST建立得对不对，只需要进行中序遍历，会得到一个从小到大的有序序列。


参考代码:

#include<cstdio>

#include<malloc.h>

typedef struct Node{

    int val;

    struct Node* left;

    struct Node* right;

}*TreeNode;

struct Node* newNode(int val){//这个函数用于生成一个值为val的节点

    TreeNode temp=(TreeNode)malloc(sizeof(struct Node));

    temp->val=val;

    temp->left=temp->right=NULL;//记得初始化

    return temp;

}

void buildBST(TreeNode& root,int val){//递归建立BST，&一定要有

    if(root==NULL){

        root=newNode(val);

        return;

    }

    if(root->val==val)//BST定义就是节点不能重复，所以遇到值相同的节点只需要建立一个就行了

        return;

    if(root->val<val){

        buildBST(root->right,val);

        return;

    }else

    buildBST(root->left,val);

}

TreeNode build(int nodeNum){

    TreeNode root=NULL;

    for(int i=0;i<nodeNum;i++){

        int val;

        scanf("%d",&val);

        buildBST(root,val);

    }

    return root;

}

void inorderTraversal(TreeNode root){

    if(root){

        inorderTraversal(root->left);

        printf("%d ",root->val);

        inorderTraversal(root->right);

    }

}

void search(TreeNode root,int num){//查找

    for(int i=0;i<num;i++){

        int obj;

        scanf("%d",&obj);

        TreeNode temp=root;

        while(temp!=NULL){

            if(temp->val==obj)

                break;

            if(temp->val>obj){

                temp=temp->left;

                continue;

            }

            if(temp->val<obj){

                temp=temp->right;

                continue;

            }

        }

        if(temp!=NULL)

            printf("1 ");

        else

            printf("0 ");

        }

}

int main(){

    int num,searchNum;

    scanf("%d%d",&num,&searchNum);

    TreeNode root=build(num);

    search(root,searchNum);

    return 0;

}