C++实现二叉树 |21xrx.com

C++实现二叉树

2023-06-30 18:10:17 深夜i 7 0

C++ 二叉树实现

二叉树是一种常用的数据结构，它是由节点所组成的树状结构。每个节点最多有两个子节点，其中左子节点的值小于当前节点的值，右子节点的值大于当前节点的值。这种特性使得二叉树在搜索、排序等算法中有着很好的应用。下面介绍如何用C++实现一个二叉树。

先定义节点结构体：

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

这里采用了一个结构体，包含了节点的值和左右子节点指针。val表示节点的值，left和right分别指向左子节点和右子节点。这里使用了一个构造函数，在初始化节点时可以给节点的值做一个赋值。

下面定义二叉树的类：

class BinaryTree {
public:
  void insert(int value);
  bool search(int value);
  void remove(int value);
  void print();
private:
  TreeNode *root;
  void insertNode(TreeNode *&node, int value);
  bool searchNode(TreeNode *&node, int value);
  void removeNode(TreeNode *&node, int value);
  void printTree(TreeNode *&node);
};

其中，insert、search、remove和print方法分别是二叉树的插入、查找、删除和打印操作。root是根节点指针，*TreeNode是定义的节点结构体。insertNode、searchNode、removeNode和printTree是实际操作节点的方法。其中，insertNode用于插入节点，searchNode用于查找节点，removeNode用于删除节点，printTree用于打印节点。

下面分别实现这四个方法：

插入节点：

void BinaryTree::insert(int value) {
  insertNode(root, value);
}
void BinaryTree::insertNode(TreeNode *&node, int value) {
  if (node == nullptr) {
    node = new TreeNode(value);
    return;
  }
  if (value < node->val) {
    insertNode(node->left, value);
  } else if (value > node->val) {
    insertNode(node->right, value);
  }
}

这里采用了递归的方式插入节点。如果节点为空，则直接生成新节点，否则根据节点值大小判断是插入到左子树还是右子树。

查找节点：

bool BinaryTree::search(int value) {
  return searchNode(root, value);
}
bool BinaryTree::searchNode(TreeNode *&node, int value) {
  if (node == nullptr)
    return false;
  
  if (node->val == value)
    return true;
   else if (value < node->val) {
    return searchNode(node->left, value);
  } else {
    return searchNode(node->right, value);
  }
}

同样，采用递归的方式查找节点。如果节点为空，说明没有找到，返回false。否则根据节点值大小判断继续在左子树还是右子树查找。

删除节点：

void BinaryTree::remove(int value) {
  removeNode(root, value);
}
void BinaryTree::removeNode(TreeNode *&node, int value) {
  if (node == nullptr)
    return;
  
  if (value < node->val) {
    removeNode(node->left, value);
  } else if (value > node->val) {
    removeNode(node->right, value);
  } else {
    if (node->left == nullptr && node->right == nullptr)
      node = nullptr;
     else if (node->left == nullptr)
      node = node->right;
     else if (node->right == nullptr)
      node = node->left;
     else {
      TreeNode *temp = node->right;
      while (temp->left != nullptr)
        temp = temp->left;
      
      node->val = temp->val;
      removeNode(node->right, temp->val);
    }
  }
}

删除节点需要考虑多种情况，包括节点为叶节点、节点只有左子树或右子树、节点同时有左右子树等。首先选择要删除的节点，然后根据其左右子树情况进行删除。如果是叶节点，直接置为空；如果只有左子树或右子树，指向子树即可；如果同时有左右子树，则找到右子树中最小的节点，将其值替换要删除的节点的值，再在右子树中删除这个节点。

打印二叉树：

void BinaryTree::print() {
  printTree(root);
}
void BinaryTree::printTree(TreeNode *&node) {
  if (node == nullptr)
    return;
  
  printTree(node->left);
  std::cout << node->val << " ";
  printTree(node->right);
}

这里采用中序遍历的方式打印二叉树节点，先打印左子树，再打印当前节点，最后打印右子树。

最后，可以使用下面的代码创建一个二叉树，并进行相关操作：

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.print();
  std::cout << std::endl;
  std::cout << "Search 6: " << tree.search(6) << std::endl;
  std::cout << "Search 9: " << tree.search(9) << std::endl;
  tree.remove(3);
  tree.print();
  std::cout << std::endl;
  return 0;
}

这里创建了一个二叉树，插入了一些节点，并进行了一些操作。其中，输出结果为：

2 3 4 5 6 7 8 Search 6: 1 Search 9: 0 2 4 5 6 7 8

这说明二叉树实现成功。

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

下一篇: C++中String类的所有成员函数详解

评论区

相似文章