用c++实现以下两个代码：一、 1.编写二叉排序树的基本操作函数。 (1)SearchNode(TREE *tree, int key, TREE **pkpt,TREE ** kpt):查找结点函数 (2)InsertNode(TREE **tree,int key):二叉排序树插入函数。 (3)DeleteNode(TREE **tree,int key):二叉排序树删除函数。 2.调用上述函数实现下列操作: (1)初始化一棵二叉树; (2)调用插入函数建立一棵二叉排序树; (3)调用查找函数在二叉树中查找指定的结点; (4)调用删除函数删除指定的结点,并动态显示删除结果。 二、3.已知以二叉链表为存储结构,试编写按中序遍历搜索并打印二叉树的算法。 [程序设计思路]采用一个栈,先将二叉树根结点入栈,若它有左子树,便将左子树根结点入栈,直到左子树为空,然后依次退栈并输出结点值;若输出的结点有右子树,便将右子树根结点入栈,如此循环入栈退栈,直到栈为空。

一、二叉排序树的基本操作函数

#include<iostream>
using namespace std;

struct TREE {
    int key;
    TREE *left, *right;
};

// 查找结点函数
void SearchNode(TREE *tree, int key, TREE **pkpt, TREE **kpt) {
    *pkpt = NULL; // pkpt为指向被查找结点的父结点指针
    *kpt = tree; // kpt为指向被查找结点的指针
    while (*kpt != NULL && (*kpt)->key != key) {
        *pkpt = *kpt;
        if (key < (*kpt)->key) {
            *kpt = (*kpt)->left;
        }
        else {
            *kpt = (*kpt)->right;
        }
    }
}

// 二叉排序树插入函数
void InsertNode(TREE **tree, int key) {
    TREE *pkpt, *kpt, *newnode;
    SearchNode(*tree, key, &pkpt, &kpt);
    if (kpt != NULL) {
        cout << "要插入的结点已存在！" << endl;
        return;
    }
    newnode = new TREE;
    newnode->key = key;
    newnode->left = newnode->right = NULL;
    if (pkpt == NULL) {
        *tree = newnode;
    }
    else if (key < pkpt->key) {
        pkpt->left = newnode;
    }
    else {
        pkpt->right = newnode;
    }
}

// 二叉排序树删除函数
void DeleteNode(TREE **tree, int key) {
    TREE *pkpt, *kpt, *spkpt, *skpt, *tmp, *tmpkpt;
    SearchNode(*tree, key, &pkpt, &kpt);
    if (kpt == NULL) {
        cout << "要删除的结点不存在！" << endl;
        return;
    }
    if (kpt->left == NULL && kpt->right == NULL) {
        if (pkpt == NULL) {
            *tree = NULL;
        }
        else if (kpt == pkpt->left) {
            pkpt->left = NULL;
        }
        else {
            pkpt->right = NULL;
        }
        delete kpt;
    }
    else if (kpt->left == NULL) {
        if (pkpt == NULL) {
            *tree = kpt->right;
        }
        else if (kpt == pkpt->left) {
            pkpt->left = kpt->right;
        }
        else {
            pkpt->right = kpt->right;
        }
        delete kpt;
    }
    else if (kpt->right == NULL) {
        if (pkpt == NULL) {
            *tree = kpt->left;
        }
        else if (kpt == pkpt->left) {
            pkpt->left = kpt->left;
        }
        else {
            pkpt->right = kpt->left;
        }
        delete kpt;
    }
    else {
        spkpt = kpt;
        skpt = kpt->left;
        while (skpt->right != NULL) {
            spkpt = skpt;
            skpt = skpt->right;
        }
        tmpkpt = skpt;
        tmp = new TREE;
        tmp->key = skpt->key;
        tmp->left = kpt->left;
        tmp->right = kpt->right;
        if (spkpt == kpt) {
            kpt->left = skpt->left;
        }
        else {
            spkpt->right = skpt->left;
        }
        delete tmpkpt;
        if (pkpt == NULL) {
            *tree = tmp;
        }
        else if (kpt == pkpt->left) {
            pkpt->left = tmp;
        }
        else {
            pkpt->right = tmp;
        }
        delete kpt;
    }
}

int main() {
    TREE *tree = NULL; // 初始化一棵二叉树
    int n, key;
    cout << "请输入二叉树的结点个数：";
    cin >> n;
    cout << "请输入" << n << "个结点的关键字：";
    for (int i = 0; i < n; i++) {
        cin >> key;
        InsertNode(&tree, key); // 调用插入函数建立一棵二叉排序树
    }
    cout << "请输入要查找的结点的关键字：";
    cin >> key;
    TREE *pkpt, *kpt;
    SearchNode(tree, key, &pkpt, &kpt); // 调用查找函数在二叉树中查找指定的结点
    if (kpt == NULL) {
        cout << "未找到指定的结点！" << endl;
    }
    else {
        cout << "已找到指定的结点！" << endl;
    }
    cout << "请输入要删除的结点的关键字：";
    cin >> key;
    DeleteNode(&tree, key); // 调用删除函数删除指定的结点，并动态显示删除结果
    cout << "删除后的二叉排序树的中序遍历结果为：";
    InOrder(tree);
    cout << endl;
    return 0;
}

二、按中序遍历搜索并打印二叉树的算法

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

struct TREE {
    int data;
    TREE *left, *right;
};

// 按中序遍历搜索并打印二叉树
void InOrder(TREE *tree) {
    stack<TREE*> s;
    TREE *p = tree;
    while (p != NULL || !s.empty()) {
        if (p != NULL) {
            s.push(p);
            p = p->left;
        }
        else {
            p = s.top();
            s.pop();
            cout << p->data << " ";
            p = p->right;
        }
    }
}

int main() {
    TREE *tree = new TREE{ 4, new TREE{2, new TREE{1, NULL, NULL}, new TREE{3, NULL, NULL}}, new TREE{5, NULL, NULL} };
    InOrder(tree);
    cout << endl;
    return 0;
}