21xrx.com
2024-12-22 22:40:01 Sunday
登录
文章检索 我的文章 写文章
C++实现二叉树：代码示例
2023-07-05 06:37:37 深夜i     --     --
C++ 二叉树 代码示例

二叉树是一种广泛应用于计算机科学中的数据结构，它的应用场景包括搜索、排序、平衡树、哈夫曼编码等诸多方面。在C++中实现二叉树的过程相对简单，下面我们来一起看看代码示例。

首先，我们需要定义二叉树节点的结构体，其包含左右子树指针以及节点值等信息：

struct TreeNode {

  TreeNode* left;

  TreeNode* right;

  int val;

  TreeNode() : left(nullptr), right(nullptr), val(0) {}

  TreeNode(int v) : left(nullptr), right(nullptr), val(v) {}

};

接着，我们可以定义二叉树的类，其中包含根节点指针以及各种操作函数，例如节点插入、删除、查找等操作，代码如下：

class BinaryTree {

private:

  TreeNode* root; // 根节点指针

  TreeNode* _insert(TreeNode* node, int val) { // 插入节点

    if (node == nullptr) return new TreeNode(val); // 空节点则新建节点

    if (val < node->val) node->left = _insert(node->left, val); // 若小于节点值，则插入左子树

    else node->right = _insert(node->right, val); // 否则插入右子树

    return node; // 返回节点指针

  }

  TreeNode* _remove(TreeNode* node, int val) { // 删除节点

    if (node == nullptr) return nullptr; // 没找到节点则返回空指针

    if (val < node->val) node->left = _remove(node->left, val); // 若小于节点值，则在左子树中查找并删除

    else if (val > node->val) node->right = _remove(node->right, val); // 若大于节点值，则在右子树中查找并删除

    else { // 找到节点

      if (node->left == nullptr && node->right == nullptr) // 若为叶子节点

        delete node; // 直接删除

        node = nullptr;

      else if (node->left == nullptr) { // 若只有右子树

        TreeNode* tmp = node;

        node = node->right;

        delete tmp;

        tmp = nullptr;

      }

      else if (node->right == nullptr) { // 若只有左子树

        TreeNode* tmp = node;

        node = node->left;

        delete tmp;

        tmp = nullptr;

      }

      else { // 有左右子树

        TreeNode* tmp = node->right;

        while (tmp->left != nullptr) tmp = tmp->left; // 找到右子树中值最小的节点

        node->val = tmp->val; // 将待删节点值赋为右子树中值最小的节点值

        node->right = _remove(node->right, tmp->val); // 在右子树中删除值最小的节点

      }

    }

    return node; // 返回节点指针

  }

  TreeNode* _find(TreeNode* node, int val) { // 查找节点

    if (node == nullptr) return nullptr; // 没有找到节点则返回空指针

    if (node->val == val) return node; // 找到节点，返回节点指针

    if (val < node->val) return _find(node->left, val); // 往左子树继续查找

    else return _find(node->right, val); // 往右子树继续查找

  }

public:

  BinaryTree() : root(nullptr) {}

  void insert(int val) { root = _insert(root, val); } // 插入节点操作

  void remove(int val) { root = _remove(root, val); } // 删除节点操作

  bool find(int val) { return _find(root, val) != nullptr; } // 查找节点操作

};

最后，我们在主函数中可以创建二叉树对象，并进行一些测试操作，例如：

int main() {

  BinaryTree tree;

  tree.insert(5); // 插入节点

  tree.insert(3);

  tree.insert(7);

  tree.insert(2);

  tree.insert(4);

  tree.insert(6);

  tree.insert(8);

  tree.remove(7); // 删除节点

  cout << (tree.find(7) ? "Found" : "Not Found") << endl; // 查找节点

  cout << (tree.find(4) ? "Found" : "Not Found") << endl;

  return 0;

}

以上就是C++实现二叉树的代码示例，我们可以通过运行程序来观察二叉树的创建、修改、查找等操作。使用二叉树可以有效地提高各种算法的效率，因此值得我们在编程过程中多加掌握和实践。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复