头歌 数据结构 实验七（三）——二叉排序树

前言：

各位大哥行行好，抄作业时麻烦换几个变量名，有查重系统的，我做博客的初心是分享我所学的东西，分享这之间的过程，和我的心得体会，让你们写不来时可以看看我的写法，学习我的思路，博主人已经麻了。

第1关：二叉排序树应用一

tips：

这道题有个需要注意的地方：BiTreeNode insertBiSortTree(BiTreeNode root, int key)，该函数的参数是个形参，不会对原本的实参进行改变，只是创建一个和实参一模一样的节点而已，所以我们需要在递归前将函数的返回结果赋值出去，不然的话，传进来的root如果是空的，最后还是空的，不会因为root=p而改变实参root。**

源码：

BiTreeNode* insertBiSortTree(BiTreeNode* root, int key)
// 功能：实现向升序二叉排序树插入元素
// 输入：待插入元素key
// 返回：升序二叉排序树根节点
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(root==NULL){
        BiTreeNode *p=new BiTreeNode;
        p->data=key;
        p->left=NULL;p->right=NULL;
        root=p;
    }
    else if(key<root->data){
        root->left=insertBiSortTree(root->left,key);
    }else if(key>root->data){
        root->right=insertBiSortTree(root->right,key);
    }
    return root;
    /********** End **********/
}

BiTreeNode* creatBiSortTree(int* arr, int n)
// 功能：实现创建升序二叉排序树
// 输入：无序整数数列arr，数列个数n
// 返回：升序二叉排序树根节点
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    BiTreeNode *root=new BiTreeNode;
    root=NULL;
    for(int i=0;i<n;i++){
        root=insertBiSortTree(root,arr[i]);
    }
    return root;
    /********** End **********/
}

第2关：二叉排序树应用二

tips：

有心的人应该会发现第一关的mian.cpp文件中有InOrder函数的写法，只要搬过来就行了，还是很简单的。

源码：

int* InOrder(BiTreeNode* root, int* arr, int &i)
// 功能：实现升序二叉排序树的中序遍历
// 参数：二叉树根节点root，整数数列arr，起始下标i=0
// 返回：中序遍历数列arr
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(root==NULL){
        return arr;
    }
    InOrder(root->left,arr,i);
    arr[i++]=root->data;
    InOrder(root->right,arr,i);
    return arr;
    /********** End **********/
}

bool isOrder(int* arr, int n)
// 功能：判断数列arr是否升序
// 参数：数列arr，数列个数n
// 返回：若升序返回true，否则返回false
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    for(int i=0;i<n-1;i++){
        if(arr[i]>arr[i+1]){
            return false;
        }
    }
    return true;
    /********** End **********/
}