求解一个算法问题，用二叉树求数组的子数组中最大值

Question

Answer 1

// Q713525.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <iostream>
using namespace std;

void print(void * a);
int cmp(void * a, void * b);
int getkey(void * a);

// 代码参考了 https://blog.csdn.net/weixin_35909255/article/details/55001177

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

template<class T>
class sortBinTree;

template<class T>
class sortBinTreeNode
{
    friend class sortBinTree<T>;
//private:
public:
    sortBinTreeNode<T> *left;
    sortBinTreeNode<T> *right;
    T data;
public:
    sortBinTreeNode():left(NULL),right(NULL){}
    sortBinTreeNode(T d):data(d),left(NULL),right(NULL){}
    T getData(){return data;}
};
template<class T>
class sortBinTree
{
public:
    sortBinTreeNode<T> *root;
public:
    sortBinTree(sortBinTreeNode<T> *ptr = NULL):root(ptr){}
public:
    //注意这个插入函数一定要有返回值，否则相当于没插进去
    int insert_val(T &x){return insert_val(root,x);}
    T max(){return max(root);}
    T min(){return min(root);}
    //这里的sort就相当于中序遍历。因为排序树中序遍历就是从小到大的。
    void sort(){sort(root);}
    int remove(T key){return remove(root,key);}
    sortBinTreeNode<T>* find(T x){return find(root,x);}
//protected:
public:
    sortBinTreeNode<T>* find(sortBinTreeNode<T> *t,T key)
    {
        if(t == NULL)
            return NULL;
        else if(getkey(&(t->data)) == getkey(&key))
            return t;
        else if(cmp(&(t->data), &key) > 0)
            return find(t->left,key);
        else
            return find(t->right,key);
    }
    //删除排序树的结点的主要思想：
    //如果要删的这个结点是叶子结点的话就直接删除，
    //否则的话找到其左子树中的最大的那个结点，把它放在要删的那个位置，然后删掉那个左子树中最大的结点
    //或者找到其右子树中的最小的那个结点，把它放在要删的那个位置，然后删掉那个右子树中最小的结点
    int remove(sortBinTreeNode<T> *&t,T key)
    {
        if(t == NULL)
            return FALSE;
        if(key < t->data)
            remove(t->left,key);
        else if(key > t->data)
            remove(t->right,key);
        else
        {
            sortBinTreeNode<T> *p = NULL;
            if(t->left != NULL && t->right != NULL)
            {
                p = t->left;
                while(p->right != NULL)
                    p = p->right;
                t->data = p->data;
                remove(t->left,p->data);
            }
            else
            {
                p = t;
                if(t->left == NULL)
                    t = t->right;
                else
                    t = t->left;
                delete p;
                return TRUE;
            }
        }
    }
    void sort(sortBinTreeNode<T> *p)
    {
        if(p != NULL)
        {
            sort(p->left);
            print(&(p->data));
            sort(p->right);
        }
    }
    T min(sortBinTreeNode<T> *p)//这个传参千万不能传引用，因为这样会改变根节点的指向的。
    {
        if(p != NULL)
        {
            while(p->left != NULL)
                p = p->left;
            return p->data;
        }
    }
    T max(sortBinTreeNode<T> *p)
    {
        if(p != NULL)
        {
            while(p->right != NULL)
                p = p->right;
            return p->data;
        }
    }

    bool solve(sortBinTreeNode<T> *pN, int p, int q)
    {
        if(pN != NULL)
        {
            if (!solve(pN->right, p, q))
            {
                if (getkey(&(pN->data)) >= p && getkey(&(pN->data)) <= q)
                {
                    print(&(pN->data));
                    return true;
                }
                else
                    return solve(pN->left, p, q);
            }
            else
                return true;
        }
        return false;
    }


    int insert_val(sortBinTreeNode<T> *&p,T &x)
    {//按照小的在左边，大的在右边构造。
        if(p == NULL)
        {
            p = new sortBinTreeNode<T>(x);
            //assert(p != NULL);
            return OK;
        }
        else if(cmp(&(p->data), &x) > 0)
        {
            insert_val(p->left,x);
        }
        else if(cmp(&(p->data), &x) < 0)
        {
            insert_val(p->right,x);
        }
        else 
            return ERROR;
    }
};

struct Emp
{
    int NO;
    int Salary;
};

int cmp(void * a, void * b)
{
    return ((Emp *)a)->Salary - ((Emp *)b)->Salary;
}

int getkey(void * a)
{
    return ((Emp *)a)->NO;
}

void print(void * a)
{
    cout << " {no=" << ((Emp *)a)->NO << ", salary=" << ((Emp *)a)->Salary << "} ";
}

int main()
{
    sortBinTree<Emp> sbt;
    sortBinTreeNode<Emp> *findval;
    int n = 8;
    Emp emp[8];
    for(int i = 0;i<n;i++)
    {
        cout << "emp no" << i << ":";
        emp[i].NO = i;
        cin >> emp[i].Salary;
        sbt.insert_val(emp[i]);
    }
    sbt.sort();
    int p = 3;
    int q = 5;
    cout << "\nresult: ";
    sbt.solve(sbt.root, p, q);

}

如果问题得到解决，请点我回答左上角的采纳，谢谢