二叉查找树

实验题目:

二叉查找树

[实验目的]

验证二叉查找树相关算法。二叉查找树是一棵可为空的二叉树,若非空则其所有结点之关键 词互异,且中根遍历形成按关键词递增序排列的结点序列。二叉查找树中的任一结点P,它的 左子树中结点的关键词都小于P的关键词,而右子树中结点的关键词都大于P的关键词,并且 结点P的左右子树也都是二叉查找树。

[实验内容及要求]

1. 依次输入int型数数值序列,每输入一给定数值K ,如果K不在二叉查找树中,则在树的 适当位置插入包含K的一个新结点,并输出此二叉查找树的中根遍历序列。

2. 如果K在二叉查找树中,则输出其所在层数,以及此二叉查找树的中根遍历序列。

函数部分:

typedef struct bstree{
    int data;
    struct bstree* left;
    struct bstree* right;
}bst,*pbst;

int str2int(string str){
    int data_int=0;
    if(str[0]=='-'){
        for(int i=1;i<str.length();i++)
        {
            data_int*=10;
            data_int+=(int(str[i])-48);//string 转 int
        }
        return -data_int;
    }else{
        for(int i=0;i<str.length();i++)
        {
            data_int*=10;
            data_int+=(int(str[i])-48);//string 转 int
        }
    }
    return data_int;
}

void Root_traversal(pbst head){    //中根遍历
    if(head==NULL)
        return;
    Root_traversal(head->left);
    cout<<head->data<<' ';
    Root_traversal(head->right);
}

pbst Insert(pbst t,int data,int &stage){    //插入节点
    if (t == NULL)
    {
        t = (pbst)malloc(sizeof(bst));
        t->left = t->right = NULL;
        t->data = data;
        return t;
    }
 
    if (data < t->data){
        stage++;
        t->left = Insert(t->left, data,stage);
    }
    else if(data > t->data){
        stage++;
        t->right = Insert(t->right, data,stage);
    }
    cout<<"element "<<data<<" is in stage "<<stage<<endl;
    return t;
}
 
pbst Createbstree(vector<int>data){    //创建树
    int stage=0;
    pbst head=NULL;
    for (int i = 0; i < data.size(); i++){
        stage=0;
        head = Insert(head, data[i],stage);
        Root_traversal(head);
        cout<<endl;
    }
    return head;
}

 

调用部分:

string d;
vector<int>data;
cout<<"please input data(to stop input *):";
cin>>d;
while(d[0]!='*'){
    data.push_back(str2int(d));
    cout<<"please input data(to stop input *):";
    cin>>d;
}
pbst head=Createbstree(data);
Root_traversal(head);

 

点赞

发表评论