C++二叉树的基本操作解析 |21xrx.com

C++二叉树的基本操作解析

2023-07-02 21:00:07 深夜i -- --

C++ 二叉树基本操作解析

C++中二叉树是最常用的数据结构之一，其操作包括创建、插入、删除、遍历、查找等。本文将对C++二叉树的基本操作进行解析，帮助读者更好地理解和应用这些操作。

二叉树是一种树形结构，它的每个节点都有一个值，左右子节点都是二叉树。创建一个二叉树，需要首先定义一个节点结构体，包括节点值、指向左右子节点的指针等。


struct Node {
  int val;
  Node* leftChild;
  Node* rightChild;
};

在创建二叉树时，我们需要一个根节点，并不断插入新节点。我们可以使用递归来实现插入操作。具体来说，对于当前节点，如果插入的值比当前节点小，则将其插入到左子树中，否则插入到右子树中。如果当前节点为空，则表示新节点是根节点。


void insert(Node* &root, int val) {
  if (root == NULL)
    root = new Node;
    root->val = val;
    root->leftChild = root->rightChild = NULL;
   else if (val < root->val) {
    insert(root->leftChild, val);
  } else if (val > root->val) {
    insert(root->rightChild, val);
  }
}

接着，我们可以实现二叉树的查找操作。查找一个节点，需要从根节点开始，对比当前节点的值与目标值的大小，然后选择左子树或右子树继续查找。如果找到目标节点，则返回该节点，否则返回NULL。


Node* search(Node* root, int val) {
  if (root == NULL || root->val == val)
    return root;
   else if (val < root->val) {
    return search(root->leftChild, val);
  } else {
    return search(root->rightChild, val);
  }
}

二叉树的删除操作相对比较复杂，需要考虑多种情况。如果要删除的节点没有子节点，直接将其删除即可；如果有一个子节点，将其子节点提上来替代；如果有两个子节点，需要找到其右子树中最小的节点，将其值赋给目标节点，并删除右子树中的这个最小节点。


void remove(Node* &root, int val) {
  if (root == NULL)
    return;
   else if (val < root->val) {
    remove(root->leftChild, val);
  } else if (val > root->val) {
    remove(root->rightChild, val);
  } else if (root->leftChild == NULL && root->rightChild == NULL)
    delete root;
    root=NULL;
   else if (root->leftChild == NULL) {
    Node* temp = root;
    root = root->rightChild;
    delete temp;
  } else if (root->rightChild == NULL) {
    Node* temp = root;
    root = root->leftChild;
    delete temp;
  } else {
    Node* temp = root->rightChild;
    while (temp->leftChild != NULL)
      temp = temp->leftChild;
    
    root->val = temp->val;
    remove(root->rightChild, temp->val);
  }
}

最后，我们可以实现二叉树的遍历操作，包括前序遍历、中序遍历和后序遍历。遍历操作可以使用递归实现，具体来说，前序遍历先访问根节点，然后依次访问左右子树；中序遍历先访问左子树，然后访问根节点，最后访问右子树；后序遍历先访问左右子树，最后访问根节点。


void preorderTraversal(Node* root) {
  if (root == NULL)
    return;
  
  cout << root->val << " ";
  preorderTraversal(root->leftChild);
  preorderTraversal(root->rightChild);
}
void inorderTraversal(Node* root) {
  if (root == NULL)
    return;
  
  inorderTraversal(root->leftChild);
  cout << root->val << " ";
  inorderTraversal(root->rightChild);
}
void postorderTraversal(Node* root) {
  if (root == NULL)
    return;
  
  postorderTraversal(root->leftChild);
  postorderTraversal(root->rightChild);
  cout << root->val << " ";
}

以上就是C++二叉树的基本操作解析，通过这些操作，我们可以方便地创建、插入、删除、查找和遍历二叉树，并用于各种实际场景中。

上一篇: idea打包java可执行jar包

下一篇: C++中实现函数相互调用的方法

评论区

()

相似文章