PAT备错本

更新：1115 -

• [1115 Counting Nodes in a BST：LIU]

  • build函数内，为root声明变量地址root =new node();，不需要node* root =new node();，这样是重新声明另一个变量。

    node* build(node* &root,int v) {
        if(root==NULL) {
            root =new node();//声明节点变量
            root->data=v;
            root->lchild=root->rchild=NULL;
        } else if(v<=root->data) { //左子树
            root->lchild=build(root->lchild,v);
        } else { //右子树
            root->rchild=build(root->rchild,v);
        }
    
        return root;
    }
    

    //main函数
    node* root=NULL;
    for(int i=0; i<N; i++) {
        scanf("%d",&v);
        root=build(root,v);
    }
    

• [1115 Counting Nodes in a BST：我的做法]

  • create()先创建根节点，之后循环插入其他节点时，注意data[]下标是从1开始的。我错写成从0开始，结果在root=25的左孩子又插入了一边25。

    //插入节点
    void insert(node* &root,int d) {
        if(root==NULL) {//若某个节点没有左、右孩子，则将data作为它的孩子
            root=newNode(d);
            return;
        }
        if(d<=root->dt) { //去左子树
            insert(root->lchild,d);
        } else//去右子树
            insert(root->rchild,d);
    
    }
    //构造BST
    node* create(int data[],int n) {//data节点数据，n节点个数
        node* root=newNode(data[0]);//创建根节点
    //  cout<<"root.data="<<root->dt<<endl;
        if(root==NULL) {
            cout<<"root是空的"<<endl;
        }
    
        for(int i=1; i<n; i++) {//根节点已经创建了，从1开始！ 
            insert(root,data[i]);
        }
    
        return root;
    }