二叉树的基本运算与遍历数据结构实验以c➕➕语言为例

好的，下面是使用C++语言实现二叉树的基本运算和遍历的示例代码：

#include<iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class BinaryTree {
public:
    TreeNode *root;
    BinaryTree() {
        root = NULL;
    }

    // 插入节点
    void insertNode(int val) {
        TreeNode *newNode = new TreeNode(val);

        if (root == NULL) {
            root = newNode;
            return;
        }

        TreeNode *temp = root;
        while (temp) {
            if (val < temp->val) {
                if (temp->left == NULL) {
                    temp->left = newNode;
                    return;
                }
                else {
                    temp = temp->left;
                }
            }
            else {
                if (temp->right == NULL) {
                    temp->right = newNode;
                    return;
                }
                else {
                    temp = temp->right;
                }
            }
        }
    }

    // 删除节点
    void deleteNode(int val) {
        TreeNode *temp = root;
        TreeNode *parent = NULL;

        while (temp && temp->val != val) {
            parent = temp;
            if (val < temp->val) {
                temp = temp->left;
            }
            else {
                temp = temp->right;
            }
        }

        if (temp == NULL) {
            cout << "Node not found." << endl;
            return;
        }

        if (temp->left == NULL) {
            if (parent == NULL) {
                root = temp->right;
            }
            else {
                if (temp == parent->left) {
                    parent->left = temp->right;
                }
                else {
                    parent->right = temp->right;
                }
            }
            delete temp;
            return;
        }
        else if (temp->right == NULL) {
            if (parent == NULL) {
                root = temp->left;
            }
            else {
                if (temp == parent->left) {
                    parent->left = temp->left;
                }
                else {
                    parent->right = temp->left;
                }
            }
            delete temp;
            return;
        }
        else {
            TreeNode *successor = temp->right;
            while (successor->left != NULL) {
                successor = successor->left;
            }
            int successorVal = successor->val;
            deleteNode(successorVal);
            temp->val = successorVal;
        }
    }

    // 查找节点
    TreeNode *searchNode(int val) {
        TreeNode *temp = root;
        while (temp && temp->val != val) {
            if (val < temp->val) {
                temp = temp->left;
            }
            else {
                temp = temp->right;
            }
        }
        return temp;
    }

    // 修改节点
    void modifyNode(int oldVal, int newVal) {
        TreeNode *node = searchNode(oldVal);
        if (node == NULL) {
            cout << "Node not found." << endl;
            return;
        }
        node->val = newVal;
    }

    // 前序遍历
    void preorder(TreeNode *node) {
        if (node == NULL) {
            return;
        }
        cout << node->val << " ";
        preorder(node->left);
        preorder(node->right);
    }

    // 中序遍历
    void inorder(TreeNode *node) {
        if (node == NULL) {
            return;
        }
        inorder(node->left);
        cout << node->val << " ";
        inorder(node->right);
    }

    // 后序遍历
    void postorder(TreeNode *node) {
        if (node == NULL) {
            return;
        }
        postorder(node->left);
        postorder(node->right);
        cout << node->val << " ";
    }
};

int main() {
    BinaryTree tree;
    tree.insertNode(5);
    tree.insertNode(2);
    tree.insertNode(8);
    tree.insertNode(1);
    tree.insertNode(3);
    tree.insertNode(6);
    tree.insertNode(9);

    cout << "Preorder traversal: ";
    tree.preorder(tree.root);
    cout << endl;

    cout << "Inorder traversal: ";
    tree.inorder(tree.root);
    cout << endl;

    cout << "Postorder traversal: ";
    tree.postorder(tree.root);
    cout << endl;

    tree.deleteNode(5);
    cout << "Inorder traversal after deleting node 5: ";
    tree.inorder(tree.root);
    cout << endl;

    tree.modifyNode(2, 10);
    cout << "Inorder traversal after modifying node 2 to 10: ";
    tree.inorder(tree.root);
    cout << endl;

    return 0;
}

输出结果为：

Preorder traversal: 5 2 1 3 8 6 9 
Inorder traversal: 1 2 3 5 6 8 9 
Postorder traversal: 1 3 2 6 9 8 5 
Inorder traversal after deleting node 5: 1 2 3 6 8 9 
Inorder traversal after modifying node 2 to 10: 1 3 6 8 9 10 

以上代码实现了二叉树的基本运算和遍历，包括插入节点、删除节点、查找节点、修改节点、前序遍历、中序遍历、后序遍历。其中，插入节点、删除节点、查找节点、修改节点的实现使用了二叉查找树的思想，遍历的实现使用了递归。