c++ 二叉树基本操作

二叉树是一种常用的树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。在二叉树中，有一些基本的操作可以帮助我们对二叉树进行各种操作。

首先是创建二叉树的操作。我们可以通过手动输入节点的值来创建一个二叉树。根据输入的值，我们可以根据特定规则将节点连接起来，形成一个完整的二叉树。

其次是遍历二叉树的操作。遍历分为前序遍历、中序遍历和后序遍历。前序遍历是先访问根节点，然后遍历左子树和右子树；中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树；后序遍历是先遍历左子树和右子树，最后访问根节点。

再次是查找二叉树中的节点的操作。对于给定的值，我们可以从根节点开始遍历整个二叉树，查找对应值的节点。如果找到了该节点，则返回该节点，否则返回空。

最后是插入和删除节点的操作。对于插入节点的操作，我们可以根据特定规则找到要插入的位置，在该位置创建一个新节点。对于删除节点的操作，我们先找到要删除的节点，然后根据节点的情况进行不同的处理，可以将其替换为其子节点或者重新连接节点。

综上所述，二叉树的基本操作主要包括创建、遍历、查找、插入和删除节点。这些操作可以帮助我们对二叉树进行灵活而高效的操作。

相关问题

c++编写二叉树的基本操作

二叉树的基本操作包括创建、插入、删除、查找、遍历等，下面是C++代码示例：

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

// 定义二叉树节点的结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 创建二叉树
TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) {
        return nullptr;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

// 插入节点
void insertNode(TreeNode* root, int val) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        if (cur->left == nullptr) {
            cur->left = new TreeNode(val);
            return;
        }
        if (cur->right == nullptr) {
            cur->right = new TreeNode(val);
            return;
        }
        q.push(cur->left);
        q.push(cur->right);
    }
}

// 删除节点
TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == nullptr) {
        return nullptr;
    }
    if (root->val == val) {
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        }
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        TreeNode* minNode = root->right;
        while (minNode->left != nullptr) {
            minNode = minNode->left;
        }
        root->val = minNode->val;
        root->right = deleteNode(root->right, minNode->val);
    } else if (root->val > val) {
        root->left = deleteNode(root->left, val);
    } else {
        root->right = deleteNode(root->right, val);
    }
    return root;
}

// 查找节点
TreeNode* searchNode(TreeNode* root, int val) {
    if (root == nullptr || root->val == val) {
        return root;
    }
    if (root->val > val) {
        return searchNode(root->left, val);
    } else {
        return searchNode(root->right, val);
    }
}

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

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

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

int main() {
    // 创建二叉树
    TreeNode* root = createTree();

    // 插入节点
    insertNode(root, 10);

    // 删除节点
    root = deleteNode(root, 5);

    // 查找节点
    TreeNode* node = searchNode(root, 3);
    cout << "search node: " << node->val << endl;

    // 遍历二叉树
    cout << "preorder: ";
    preOrder(root);
    cout << endl;

    cout << "inorder: ";
    inOrder(root);
    cout << endl;

    cout << "postorder: ";
    postOrder(root);
    cout << endl;

    return 0;
}

以上代码包含了二叉树的创建、插入、删除、查找以及前序、中序、后序遍历等基本操作。

二叉树的基本操作c++

二叉树的基本操作包括：创建二叉树、遍历二叉树、插入节点、删除节点等，以下是C++代码示例：

#include <iostream>
using namespace std;

// 二叉树节点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 创建二叉树
TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) {  // 遇到-1表示该节点不存在，返回NULL
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

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

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

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

// 插入节点
TreeNode* insert(TreeNode* root, int val) {
    if (root == NULL) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    }
    else {
        root->right = insert(root->right, val);
    }
    return root;
}

// 删除节点
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) {
        return NULL;
    }
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    }
    else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    }
    else {
        if (root->left == NULL && root->right == NULL) {  // 叶子节点
            delete root;
            return NULL;
        }
        if (root->left == NULL) {  // 只有右子树
            TreeNode* tmp = root->right;
            delete root;
            return tmp;
        }
        if (root->right == NULL) {  // 只有左子树
            TreeNode* tmp = root->left;
            delete root;
            return tmp;
        }
        // 有两个子节点，找到右子树中的最小节点
        TreeNode* tmp = root->right;
        while (tmp->left != NULL) {
            tmp = tmp->left;
        }
        root->val = tmp->val;
        root->right = deleteNode(root->right, tmp->val);
    }
    return root;
}

int main() {
    // 创建二叉树
    TreeNode* root = createTree();

    // 遍历二叉树
    cout << "Preorder: ";
    preorder(root);
    cout << endl;

    cout << "Inorder: ";
    inorder(root);
    cout << endl;

    cout << "Postorder: ";
    postorder(root);
    cout << endl;

    // 插入节点
    root = insert(root, 5);

    // 删除节点
    root = deleteNode(root, 3);
    
    // 遍历二叉树
    cout << "Preorder: ";
    preorder(root);
    cout << endl;

    cout << "Inorder: ";
    inorder(root);
    cout << endl;

    cout << "Postorder: ";
    postorder(root);
    cout << endl;

    return 0;
}