C++二叉树代码编写 |21xrx.com

C++二叉树代码编写

2023-06-29 18:09:44 深夜i -- --

C++ 二叉树代码编写数据结构

C++是一种常用的编程语言，可用于实现各种数据结构，包括二叉树。二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点。在C++中，可以使用类的方式来实现二叉树。

首先，我们需要定义节点的结构。一个节点应该包括节点值和指向其左右子节点的指针。这可以通过如下代码实现：


class TreeNode {
public:
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

然后，我们需要定义一个二叉树类。这个类应该包括根节点指针和实现插入，查找，删除操作的方法。这可以通过如下代码实现：


class BinarySearchTree {
public:
  TreeNode* root;
  BinarySearchTree() : root(nullptr) {}
  void insert(int val) {
    if (!root) {
      root = new TreeNode(val);
      return;
    }
    insert_at_node(root, val);
  }
  void remove(int val) {
    root = remove_at_node(root, val);
  }
  bool find(int val) {
    return find_at_node(root, val);
  }
private:
  void insert_at_node(TreeNode* node, int val) {
    if (node->val > val) {
      if (!node->left) {
        node->left = new TreeNode(val);
        return;
      }
      insert_at_node(node->left, val);
    }
    else {
      if (!node->right) {
        node->right = new TreeNode(val);
        return;
      }
      insert_at_node(node->right, val);
    }
  }
  TreeNode* remove_at_node(TreeNode* node, int val) {
    if (!node)
      return nullptr;
    
    if (node->val > val) {
      node->left = remove_at_node(node->left, val);
      return node;
    }
    else if (node->val < val) {
      node->right = remove_at_node(node->right, val);
      return node;
    }
    else {
      if (!node->left && !node->right)
        delete node;
        return nullptr;
      
      else if (node->left && !node->right) {
        TreeNode* temp = node->left;
        delete node;
        return temp;
      }
      else if (!node->left && node->right) {
        TreeNode* temp = node->right;
        delete node;
        return temp;
      }
      else {
        TreeNode* replacement = node->right;
        while (replacement->left)
          replacement = replacement->left;
        
        node->val = replacement->val;
        node->right = remove_at_node(node->right, replacement->val);
        return node;
      }
    }
  }
  bool find_at_node(TreeNode* node, int val) {
    if (!node)
      return false;
    
    if (node->val == val)
      return true;
    
    else if (node->val > val) {
      return find_at_node(node->left, val);
    }
    else {
      return find_at_node(node->right, val);
    }
  }
};

最后，我们可以使用上述类来实现二叉树操作。例如，下面的代码展示了如何创建一个二叉树对象，并使用insert、find和remove操作：


int main() {
  BinarySearchTree bst;
  bst.insert(5);
  bst.insert(3);
  bst.insert(7);
  bst.insert(1);
  if (bst.find(3))
    cout << "3 found in the tree" << endl;
  
  bst.remove(3);
  if (!bst.find(3))
    cout << "3 removed from the tree" << endl;
  
  return 0;
}

以上就是使用C++编写的二叉树代码示例。二叉树是一种重要的数据结构，在计算机科学、算法和算法设计方面都有着重要的应用。掌握C++编写二叉树的基本方法可以让我们更好地使用这种数据结构，进而实现更加高效的算法。

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

下一篇: C++如何在输入两个数之间加入空格？

评论区

()

相似文章