论坛 › C\C++交流 › 二叉排序树中的问题，半个小时愣是没明白怎么错了

游啊游 发表于 2016-5-27 21:22:37

二叉排序树中的问题，半个小时愣是没明白怎么错了

//二叉排序树
#include<iostream>
#define MaxSize 20
using namespace std;
struct BiNode
{
        int data;
        BiNode *lchild,*rchild;
};
class BST
{
public:
        BST(int a[],int n);
        ~BST(){}
        void insertBST(BiNode *root,BiNode *s);
        void deleteBST(BiNode *root,BiNode *s);
        void Delete(BiNode *s);//删除结点
        void preOrder(BiNode *root);//前序遍历函数
        BiNode* getRoot(){return root;}
private:
        BiNode *root;
};
void BST::insertBST(BiNode *root,BiNode *s)
{
        if(NULL == root) root=s;
        else if(s->data<root->data)
                insertBST(root->lchild,s);
        else
                insertBST(root->rchild,s);
}
BST::BST(int a[],int n)
{
        for(int i=0;i<n;i++)
        {
                BiNode *s=new BiNode;
                s->data=a;
                s->lchild=s->rchild=NULL;
                insertBST(root,s);
        }
}
void BST::deleteBST(BiNode *root,BiNode *s)
{
        if(!root)
                return;
        else
        {
                if(root->data==s->data)
                        Delete(s);
                else if(s->data<root->data)
                        deleteBST(root->lchild,s);
                else
                        deleteBST(root->rchild,s);
        }
}
void BST::Delete(BiNode *s)
{
        BiNode *p,*q;
        if(s->rchild == NULL) //右子树为空的结点
        {
                p=s;
                s=s->lchild;
                delete(p);
        }
        if(s->lchild == NULL) //左子树为空的结点
        {
                p=s;
                s=s->rchild;
                delete(p);
        }
        if(s->lchild!=NULL && s->rchild!=NULL)   //左右子树均不为空,前驱替换该结点
        {
                p=s;
                q=s->lchild;
                while(q!=NULL)
                {
                        p=q;
                        q=q->rchild;
                }
                s->data=q->data;
                if(p==s) p->rchild=q->lchild;
                else
                        p->rchild=q->lchild;
                delete(q);
        }
}
void BST::preOrder(BiNode *root)
{
        if(!root)
                return;
        else
        {
                cout<<root->data<<" ";
                preOrder(root->lchild);
                preOrder(root->rchild);
        }
}
void main()
{
        int a,c;
        cout<<"结点个数:(不大于"<<MaxSize<<"个)"<<endl;
        int n;
        cin>>n;
        cout<<"输入结点"<<endl;
        for(int i=0;i<n;i++)
                cin>>a;
        BST bst(a,n);
        BiNode *r=bst.getRoot();
        while(1)
        {
                cout<<"1.插入结点2.删除结点"<<endl;
                cout<<"3.遍历                "<<endl;
                cin>>c;
                switch(c)
                {
                case 1:{
                           BiNode *nNode=new BiNode;
                           cout<<"输入结点"<<endl;
                           int temp;
                           cin>>temp;
                           nNode->data=temp;
                           bst.insertBST(r,nNode);
                           break;
                           }
                case 2:{
                           BiNode *Node=new BiNode;
                           cout<<"输入结点"<<endl;
                           int temp2;
                           cin>>temp2;
                           Node->data=temp2;
                           bst.deleteBST(r,Node);
                           break;
                           }
                case 3:bst.preOrder(r);
                           break;
                }
        }
}

问题出在创建二叉排序树时

游啊游 发表于 2016-5-28 19:35:36

有没有人啊

游啊游 发表于 2016-5-29 11:22:35

已解决

Code_mzh 发表于 2018-3-29 18:32:26

哪错了呢，没找到啊，求助。。。。

查看完整版本: 二叉排序树中的问题，半个小时愣是没明白怎么错了