KeyType maxnode(BSTNode *p) KeyType minnode(BSTNode *p)

`maxnode` 函数可以用于查找二叉搜索树中的最大键值节点，其实现方法为：

KeyType maxnode(BSTNode* p) {
    if (!p) {
        return NULL;
    }
    while (p->right) {
        p = p->right;
    }
    return p->key;
}

`minnode` 函数可以用于查找二叉搜索树中的最小键值节点，其实现方法为：

KeyType minnode(BSTNode* p) {
    if (!p) {
        return NULL;
    }
    while (p->left) {
        p = p->left;
    }
    return p->key;
}

这两个函数都是基于二叉搜索树的性质，即左子树中的所有节点的键值都小于根节点的键值，右子树中的所有节点的键值都大于根节点的键值。因此，对于最大键值节点，我们需要一直往右子树中遍历，直到遇到没有右子节点的节点；对于最小键值节点，我们需要一直往左子树中遍历，直到遇到没有左子节点的节点。

相关问题

KeyType maxnode(BSTNode *p) KeyType minnode(BSTNode *p)

这两个函数分别用于在二叉搜索树中查找最大值和最小值节点的键值。

maxnode函数的实现如下：

KeyType maxnode(BSTNode *p)
{
    if (p == nullptr) {
        return NULL;
    }
    while (p->right != nullptr) {
        p = p->right;
    }
    return p->key;
}

该函数从根节点开始向右子树遍历，直到找到最右侧的叶子节点，即为最大值节点。

minnode函数的实现类似：

KeyType minnode(BSTNode *p)
{
    if (p == nullptr) {
        return NULL;
    }
    while (p->left != nullptr) {
        p = p->left;
    }
    return p->key;
}

该函数从根节点开始向左子树遍历，直到找到最左侧的叶子节点，即为最小值节点。

修改#include<iostream> #include<algorithm> using namespace std; class Node { public: int val; Node* next; Node() { this->next=NULL; } }; class list { public: Node *head; list() //构造函数 { // head=new Node(); // head->next=NULL; } list nextL (Node*p) //以下一个节点为开始的新链表 { list l; l.head->val=p->val; l.head->next=p->next; return l; } }; Node* createList(int n) //创建长度为n的链表（尾插法） { if(n==0) return NULL; Node*p=new Node; cin>>p->val; p->next=createList(n-1); return p; } void Question7(); int maxNode(list l); int minNode(list l); int main() { Question7(); } void Question7() { list l; cout<<"输入长度为10的链表的值："<<endl; Node*p=createList(10); //创建链表 l.head=p; cout<<"最大值"<<maxNode(l)<<endl; cout<<"最小值"<<minNode(l)<<endl; } int maxNode(list l) { Node*p=l.head; if(p->next==NULL) //走到最后返回这个点的值 return p->val; return max(p->val,maxNode(l.nextL(p->next))); //返回这个点及其往后的最大值 } int minNode(list l) { Node*p=l.head; if(p->next==NULL) //走到最后返回这个点的值 return p->val; return min(p->val,minNode(l.nextL(p->next))); //返回这个点及其往后的最小值 }

这是修改后的代码，主要是增加了list类的成员函数nextL用于创建下一个以某个节点为开始的新链表，并且可以在l.head未初始化的情况下修改它的值：

#include<iostream>
#include<algorithm>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node() {
        this->next=NULL;
    }
};

class list {
public:
    Node *head;
    list() {
        head=new Node();
        // head->next=NULL;
    }
    list nextL (Node*p) {
        list l;
        l.head=p;
        return l;
    }
};

Node* createList(int n) {
    if(n==0) return NULL;
    Node*p=new Node;
    cin>>p->val;
    p->next=createList(n-1);
    return p;
}

void Question7();
int maxNode(list l);
int minNode(list l);

int main() {
    Question7();
}

void Question7() {
    list l;
    cout<<"输入长度为10的链表的值："<<endl;
    Node*p=createList(10);
    l.head=p;
    cout<<"最大值："<<maxNode(l)<<endl;
    cout<<"最小值："<<minNode(l)<<endl;
}

int maxNode(list l) {
    Node*p=l.head;
    if(p->next==NULL)
        return p->val;
    return max(p->val,maxNode(l.nextL(p->next).head));
}

int minNode(list l) {
    Node*p=l.head;
    if(p->next==NULL)
        return p->val;
    return min(p->val,minNode(l.nextL(p->next).head));
}

这个程序创建了一个链表，然后使用递归的方式查找链表中的最大值和最小值。在list类中，nextL函数返回以某个节点为开始的新链表。在查找最大值和最小值时，如果已经到达链表的末尾，则返回当前节点的值。否则，递归调用nextL函数并传入下一个节点，继续查找下一个节点的值，最后返回当前节点和后面的所有节点的最大值或最小值。